顺序表与链表对比

共同点

顺序表和链表都用于实现 线性表，逻辑结构都是线性结构。区别主要来自存储结构不同。

存储结构对比

项目 顺序表 链表
存储方式 顺序存储 链式存储
空间要求 需要连续空间 可使用离散空间
存储密度 高，只存数据元素 低，需要额外指针域
容量变化 不方便，扩容代价高 较方便，按需申请结点
随机存取 支持 不支持

初始化与销毁

顺序表初始化通常需要预分配一大片连续空间。静态分配容量不可变；动态分配容量可变，但扩容仍可能需要移动大量元素。

链表初始化只需建立头指针或头结点，之后按需申请结点。销毁链表时需要依次释放各结点。

插入与删除

顺序表插入、删除时，主要时间开销来自移动元素，平均时间复杂度为 O(n)。

链表插入、删除时，修改指针本身是 O(1)，但若需要先查找目标位置或前驱结点，总时间通常仍为 O(n)。它的优势是找到位置后不需要移动大量元素。

查找

  • 顺序表按位查找：O(1)。
  • 链表按位查找：O(n)。
  • 顺序表和链表按值查找：通常都是 O(n)。
  • 若顺序表有序，可使用二分查找达到 O(log_2 n)。

如何选择

优先选链表：表长难以预估，频繁插入、删除，且不要求高效随机访问。

优先选顺序表：表长可预估，查询操作较多，尤其是按位访问较多，或需要较高存储密度。链表的存储密度低，因为每个结点除了数据域还要保存指针域。

开放题答题框架

先说明二者逻辑结构相同，都是线性表；再说明存储结构不同：顺序表采用顺序存储，链表采用链式存储；随后从空间分配、随机访问、插入删除、查找效率、容量变化几个角度比较；最后结合题目场景给出选择。

关联

细节可回看 顺序表的存储与实现、单链表的定义与头结点、静态链表。