顺序表与链表

2026-05-09

顺序表与链表

核心定义

顺序表是用 连续存储单元 顺序保存线性表元素的结构，核心优势是 可随机访问，能直接通过下标定位第 $i$ 个元素，查找复杂度 $O(1)$ 。

链表是用指针把若干结点串联起来的线性结构，核心优势是 插入删除局部化，不必像顺序表那样大规模移动元素。若已知前驱结点，插删复杂度 $O(1)$ 。

单链表每个结点包含 数据域 和 指针域，只能从头到尾单向遍历。双链表每个结点额外增加 前驱指针，支持双向遍历。

静态链表用数组模拟链表结构，不需要动态分配内存，适合不支持指针的语言环境。

顺序表和链表的本质差异是 存储是否连续：连续存储带来访问快但也带来 扩容成本 和 移动成本；离散存储带来操作灵活但也带来 额外指针开销 和 查找成本。

若顺序表已有 1000 个元素，在第 1 个位置插入新元素，可能要移动 999 个元素（最坏移动 $n$ 个）；而链表若已找到插入位置，只需改动 2 个指针（单链表）或 4 个指针（双链表）。

顺序表的存储密度为 1（不含额外信息），链表的存储密度 小于 1（因为要存指针域）。顺序表的长度可以 动态增长（需扩容），也可以 静态固定。

线性表是 相同数据类型 的有限序列，顺序表和链表都是其存储实现。

考研题围绕 访问、插入、删除、查找、扩容 展开。顺序表按值查找平均比较 $\frac{n+1}{2}$ 次。

数据结构：定义与三要素

数据结构 = 相互之间存在一种或多种 特定关系 的数据元素的集合。（本质是”关系”，不是”性质相同”——后者只是同类数据的特征）

三要素（完整的数据结构必须同时具备）：

要素	含义	举例
逻辑结构	数据元素间的逻辑关系	集合、线性、树形、图状
存储（物理）结构	逻辑结构在计算机中的映射	顺序、链式、索引、散列
数据的运算	施加在数据上的操作	插入、删除、查找

🚫 易错：问”数据结构是什么”选 特定关系；问”完整数据结构包含哪些”必须 三要素齐全（缺一不可）。

顺序存储、随机存取与存取特性

顺序存储：逻辑相邻 ⇒ 物理地址一定连续（“连续存储设计”⇔“物理地址连续”，两者直接画等号）。相邻元素的地址差 = 元素大小 $L$ （常数）。

随机存取（Random Access）：因物理连续且元素等长，可用公式一步定位第 $i$ 个元素： $\text{LOC}(a_i) = \text{LOC}(a_1) + (i-1) \times L \quad \Rightarrow \quad O(1)$

存取特性对照（高频考点）：

存储方式	存取特性	查找第 $i$ 个元素
顺序存储	随机存取	$O(1)$ ，与 $i$ 无关
链式存储	顺序存取	$O(n)$ ，与 $i$ 成正比

🚫 因果倒置：随机存取 ≠ 随机存储。随机存取是能力（下标一步到位），顺序存储是 物理基础。链式存储 ⇒ 物理不一定连续 ⇒ 只能 顺序存取。

头指针 vs 头结点

概念	是什么	作用
头指针 head	指向链表第一个结点的指针变量	标识链表起始位置（必须存在）
头结点 Head Node	第一个数据结点前人为插入的占位躯壳（不存有效数据）	方便运算：统一操作、空表一致

增加头结点的核心目的 = 方便运算的实现：

统一操作：在第一个位置插删时，语句与中间操作完全一致（都有前驱），无需 if (p == head) 特判。
空表一致：带头结点时，无论表空与否，头指针都不为 NULL，处理更安全。

🚫 张冠李戴：找路 / 标识起点 → 头指针；方便写代码 / 不写特判 → 头结点。“指向第一个结点的指针”是头指针；“插在第一个结点前的占位结点”是头结点。

链表指针操作：先连后断与循环链表边界

单链表插入 — 先连后断法则（在 q → p 之间插 s，目标 q → s → p）：

s->next = p;   // 第一步：新结点 s 先抓住后继 p（先连）
q->next = s;   // 第二步：前驱 q 再改指向 s（后断）

口诀：“新接后继，前驱改新”。务必画图！把 ->next 翻译成”x 伸出的右手连着谁”。顺序反了会让 p 被架空（s->next = p->next 是错的）。

循环单链表的边界陷阱：

带头结点空表：Head->next = Head（头结点指向自己）。插入第一个结点 P 后为 Head → P → Head，此时 P->next->next == P。
删除时的尾指针更新（2021 真题）：带头结点循环单链表删第一个元素，若该结点是 唯一元素（p == q），free 后尾指针 p 变野指针，必须先特判 if (p == q) p = h; 再释放。

🚫 边界条件全盲：链表删除必问”删空了怎么办”。凡带尾指针 / 双指针的删除，选项里没有 if 边界判断的 99% 是错的。把”链表只有一个元素”作为第一套测试用例。“带头结点”四个字值两分——结构里永远至少有 1 个结点。

关键细节 / 操作步骤

先判断题目考的是 查找效率 还是 插删效率。
若强调第 $i$ 个元素，优先想到 顺序表——下标直接定位，时间 $O(1)$ 。
若强调频繁中间插入删除，优先想到链表——只需改指针，时间 $O(1)$ （不计定位）。
若链表题问删除，先找 前驱结点 或利用双链表的 前驱指针。
若顺序表题问插入，先 整体后移 元素，再把新值放入空位，平均移动 $\frac{n}{2}$ 个元素。
若顺序表题问扩容，要想到 重新分配空间 与 元素拷贝（均摊 $O(1)$ ）。
若题目问”能否二分查找”，先判断是否有序且是否 随机访问方便——链表不适合因为不能直接跳到中点。
若题目问复杂度，先区分 定位阶段 和 操作阶段，再分别判断。
若题目涉及链表遍历，先考虑是否要从 头结点 逐个移动，时间 $O(n)$ 。
若题目只问”为什么”，优先从 连续性 与 指针连接 两个维度回答。
若题目问头结点的作用，核心是 统一空表和非空表的操作，简化边界处理——无头结点时首元素插入需特殊处理。
若题目问顺序表删除第 $i$ 个元素，需要向前移动 $n - i$ 个元素。
若题目问链表逆置，可用 头插法 逐个摘取结点重新插入，时间 $O(n)$ 空间 $O(1)$ 。
若题目问两个有序链表合并，使用 双指针归并，时间 $O(n+m)$ 。
若题目问链表是否有环，使用 快慢指针（快指针每次走两步，慢指针走一步），若相遇则有环。
若题目问顺序表按值查找，无序表需 逐个比较，有序表可二分查找降为 $O(\log n)$ 。
若题目问循环链表的特点，尾结点的 next 指向 头结点，可以从任意结点出发遍历全表。

⚠️ 易错辨析 顺序表”查找快”不代表”所有操作都快”，中间插入和删除时移动元素的代价可能很大（ $O(n)$ ）。链表”插入快”也不是无条件成立——若要先找到目标位置，定位过程本身可能就是 $O(n)$ 。很多人把”顺序表可随机访问”理解成”链表绝对不能访问第 $i$ 个元素”，其实链表也能访问，只是要从头走到目标结点，代价更高。顺序表扩容不是简单改长度，而常伴随 申请新空间、复制旧元素、释放旧空间。反例：在链表头部频繁插入时链表比顺序表快，但若每次都要求先查到第 $i$ 个再插，则链表并不一定更优。

💡 技巧与口诀 口诀：顺序表看位置，链表看指针；查找选顺序，插删选链表。适用场景：凡是出现”第 $i$ 个""随机访问""连续内存”就先想顺序表；出现”频繁插删""中间改动”就先想链表。若题目要求比较时间复杂度，先区分”定位”和”修改”两个阶段，再分别判断。头结点的存在可以 简化插入删除的边界判断。

📝 真题闭环 题目：若要求在表中频繁插入和删除元素，顺序表和链表哪个更合适？

解题思路：审题先抓”频繁插删”，切入点是链表；公式选择上不必复杂计算，关键是比较移动成本；计算关键点是顺序表需要搬移大量元素（ $O(n)$ ），而链表只需改指针（ $O(1)$ ）；易错防范是不要把”查找快”误当成”插删快”。

答案：链表更合适。
// T=O(n) S=O(1)
void insert(int a[], int *len, int pos, int x) {
    for (int i = *len; i > pos; --i) a[i] = a[i - 1];
    a[pos] = x;
    (*len)++;
}

cd ..