顺序表和链表的区别（C语言）

前言

线性表是最基础的数据结构之一，其中顺序表与链表分别代表两种存储方式：

• 顺序表（Sequential List）：底层用数组实现，要求内存连续，典型代码以 int data[N] 或动态分配的 malloc/realloc 数组形式出现。
• 链表（Linked List）：由一系列节点（node）通过指针互相连接，每个节点包含数据域和指针域，可分为单向、双向或循环链表等多种形式。
  

一、储存空间上的不同

顺序表与链表在物理和逻辑存储布局上差异显著：

1. 顺序表 的所有元素在内存中连续分布，数组首地址已知，通过下标即可计算任意元素地址。
2. 链表 的节点由 malloc（或其他分配方法）逐个分配，物理地址不连续，节点间仅靠指针（如 next）维系逻辑顺序 。
3. 链表每个节点需额外存储指针域，若单向链表，则每个元素至少比顺序表多消耗一个机器字大小（如 4 或 8 字节）。

二、随机访问的不同

访问效率是两者最显著的对比点：

• 顺序表：支持随机访问，直接通过 data[i] 计算偏移并读取，时间复杂度 O(1)。
• 链表：不支持随机访问，访问第 i 个节点必须从头节点开始沿 next 指针逐个跳转，时间复杂度 O(N) 。

三、任意位置插入或者删除元素的不同

中间位置的增删操作体现了两者的权衡：

• 顺序表：在位置 i 处插入或删除需将下标 ≥ i 的所有元素向后（或向前）移动一格，最坏情况需移动 N–i 个元素，时间复杂度 O(N)。
• 链表：若已定位到第 i–1 个节点，仅需改变少量指针（例如 prev->next = newNode; newNode->next = curr;），插入/删除本身操作为常数时间 O(1) ；但若定位节点也需遍历，则整体为 O(N)。

四、插入（添加元素）的不同

尾部或动态扩展时的实现差异：

1. 顺序表尾插：若当前容量足够，可在末尾直接写入，时间复杂度 O(1)；若容量不足，则需调用 realloc 以几何增长（通常倍增）策略扩容，单次扩容 O(N)，但摊销后每次插入仍为 O(1)。
2. 扩容开销：realloc 可能搬移全部数据，且扩容后的空余空间在短期内未被使用会造成浪费。
3. 链表尾插：需调用 malloc 为新节点分配内存并调整末尾指针，时间复杂度 O(1)，但频繁 malloc/free 带来系统调用开销，且内存碎片可能增加。

五、应用场景不同

根据操作特性选择数据结构：

• 顺序表适用：
  • 需要频繁随机访问，如实现静态查表、快速索引等场景。
  • 元素总量事先已知或变动不大，减少扩容成本。
• 链表适用：
  • 频繁中间插入或删除，如实现任务调度队列、图的邻接表、内存块管理等。
  • 数据量动态变化大、无法预估最大规模，且对随机访问需求不高。

六、缓存利用率的不同

现代 CPU 的缓存机制对两者影响巨大：

• 顺序表：因内存连续，读取一个元素时缓存行会预取相邻数据，带来高空间局部性和高缓存命中率。
• 链表：节点零散分布，指针跳转导致频繁Cache Miss，无法有效预取，访问延迟明显增大。

总结