顺序表与单链表详解：线性表的底层逻辑、核心操作与避坑指南-育师

数据结构这门课，线性表是真正的第一道分水岭。顺序表和单链表，这两个名字几乎出现在每一本数据结构的教材前两章，也是每一轮笔试面试的常客。很多人在这就学懵了：代码看得懂，一写就出错，尤其是链表，指针绕来绕去，越改越乱。这篇文章就把这两个结构掰开揉碎，从底层逻辑到代码实现，再到那些教材里不会明说的坑，完整梳理一遍，适合刚开始学数据结构、或者复习到链表还觉得不踏实的开发者。

1. 线性表到底在解决什么问题

1.1 为什么数据结构课程的第一站永远是它

现实世界里大量的数据天然是排成一队的：通讯录里按姓名排列的联系人、待办事项清单、股票的分时价格序列，甚至一段音频的采样点。把这类“一个挨着一个、有先后次序”的数据抽象成统一模型，就是线性表。它的核心定义只有一条：由 n 个数据元素组成的有限序列，每个元素除了第一个和最后一个，都有一个直接前驱和一个直接后继。

这条定义的价值在于，它把所有“排着队的数据”的共性操作统一了：往队里某个位置塞一个新元素（插入），把某个位置的元素拿走（删除），查看某个位置的元素（按位置访问），以及统计队伍有多长（求长度）。如果你后续学栈、队列、字符串，会发现它们本质上都是线性表加了不同的访问约束——栈只允许在一端操作，队列一端进另一端出。所以线性表这部分学不透，后面的内容全都飘着，因为所有后续结构都要复用这里建立起来的存储和操作思维。

1.2 顺序表和单链表：两条完全不同的存储路线

同样一组排着队的数据，计算机里有两种截然不同的存法。

顺序表用的是“连续存储”，就是直接在内存里划一整块连续空间，元素一个挨一个放。这就像一条街上的门面房，门牌号连续，你想找第 8 家店，从街头数到第 8 个门牌就行，不用挨家敲门。

单链表用的是“链式存储”，每个元素单独分配一块内存，不保证大家在物理上挨着。每个节点除了存自己的数据，还要额外存一个指针，指向下一个节点在哪。这就像开在城里各个角落的分店，每家店都贴一张纸条告诉你下一家店的具体地址。你想找第 8 家店？抱歉，你得从第一家店出发，一路看纸条找过去。

这两条路线没有绝对的优劣，各赚各的，各亏各的。顺序表因为连续存储，访问快，但插入删除需要挪动大量数据；链表因为散落存储，增删只改几个指针，但按位置访问就要从头走到尾。把这两条路的核心机制搞清楚，是后面所有判断的根基。

2. 顺序表：连续内存的得与失

2.1 底层逻辑：数组加个尾巴就是顺序表

很多人觉得顺序表神秘，其实说穿了非常简单：顺序表就是“动态数组 + 两个变量”。一个变量记录现在装了多少元素（一般叫 length），另一个变量记录总共分配了多少空间（一般叫 capacity）。数组负责存数据，length 指向有效数据末尾，capacity 表示数组最大能装多少。

用 C 语言写一个顺序表的结构体就是：

#define ElemType int typedef struct { ElemType* data; // 指向堆上分配的连续内存 int length; // 当前元素个数 int capacity; // 当前容量 } SeqList;

初始化的时候，先分配一块初始容量的空间，比如 10 个元素大小，把 length 置 0。之后所有操作都围绕这三个字段展开。判断表空看 length 是否为 0，判断表满看 length 是否等于 capacity，访问第 i 个元素直接写 data[i-1]（元素从 1 开始编号，下标从 0 开始，这个细节很多人写代码时栽过跟头）。

2.2 动态扩容：为什么两倍扩容是经典选择

顺序表一开始容量固定，但元素可能会越加越多，容量不够时就要扩容。最朴素的做法是：新分配一块更大的内存，把旧数据全部拷过去，释放旧空间，然后更新 data 指针和 capacity。

关键问题来了：每次扩容应该扩多少？有人觉得需要再加 10 个就分配原容量 + 10，看似省内存，实则开销很大。假设从一个元素开始，每次加 10 个元素都要扩容一次，那么插入第 11、21、31 个元素时都发生搬迁，数据越搬越多，总搬家元素数是 10 + 20 + 30 + ...，这是一个 O(n²) 级别的累积量，数据量大时卡到怀疑人生。

如果换成倍扩，容量 10 → 20 → 40 → 80，每次扩容的数据搬迁量翻倍，总搬迁量约为 2n，是线性级别。有人统计过，均摊到每一次插入操作，时间复杂度是 O(1)。这就是经典的均摊分析：偶尔一次插入贵，但长期看每个插入的平摊成本很便宜。所以业内惯例就是 1.5 倍或 2 倍扩容，实践里两倍最简单，避免频繁搬迁。

void ensureCapacity(SeqList* list, int need) { if (list->capacity >= need) return; int newCap = list->capacity == 0 ? 4 : list->capacity * 2; while (newCap < need) { newCap *= 2; } ElemType* newData = (ElemType*)malloc(sizeof(ElemType) * newCap); for (int i = 0; i < list->length; i++) { newData[i] = list->data[i]; } free(list->data); list->data = newData; list->capacity = newCap; }

注意一个容易被忽略的细节：扩容后旧数据要全部搬到新内存，但新内存里 length 之后的区域是不确定值。所以任何时候都只允许访问下标小于 length 的元素，绝不能因为 capacity 很大就随意操作后面那些“还没登记的”位置。

2.3 插入删除的真实代价：内存搬运才是大头

顺序表最核心的两个操作就是插入和删除。现在我想在下标 i 的位置插入一个新元素 x，正确步骤是：把从 i 开始到末尾的所有元素统统向后挪一位，然后在空出来的位置写入 x。

int insert(SeqList* list, int index, ElemType x) { if (index < 0 || index > list->length) return 0; // 越界检查 ensureCapacity(list, list->length + 1); for (int i = list->length; i > index; i--) { list->data[i] = list->data[i - 1]; } list->data[index] = x; list->length++; return 1; }

删除是反向操作：从 i+1 开始到末尾，全部向前挪一位，覆盖掉要删的元素。

int removeAt(SeqList* list, int index) { if (index < 0 || index >= list->length) return 0; for (int i = index; i < list->length - 1; i++) { list->data[i] = list->data[i + 1]; } list->length--; return 1; }

这两段代码看着简单，里面的经验却不少。第一个坑是循环方向。插入必须从后往前挪，如果你从前往后挪，数据会被后面的元素覆盖掉，全乱套。删除则必须从前往后挪，方向反了一样出错。第二个坑是边界判断。插入允许 index == length，相当于在末尾追加；删除时 index == length 是非法位置，没有任何元素可删。这两个边界条件，很多初写的人会搞混。

时间复杂度的计算也很直接：平均插入位置在中间，大约要搬一半元素，所以 O(n)。但这里的 n 不是指的循环多少次那么简单，真正花时间的是内存数据的成块移动。计算机的内存拷贝是顺序读写，缓存友好度尚可，一次拷贝虽快，量大了一样扛不住。所以顺序表的最优使用场景是：以访问为主、少量在尾部增删，而不是频繁在中间插插删删。

提示：如果在开头持续插入，顺序表就是灾难。每插入一个元素都要把整表往后挪一位，一万个元素插入一次就挪一万下，十万就得挪十万下。这时候就该让链表登场了。

3. 单链表：用指针换灵活性

3.1 节点设计：数据域加指针域，最小闭环

单链表的基本单位是节点，每个节点是一个结构体，包含数据域和指针域。数据域存具体值，指针域存下一个节点的地址。

typedef struct LNode { ElemType data; struct LNode* next; } LNode;

这个定义里有个关键点：next 是指向 LNode 类型的指针，而 LNode 这个结构体还没定义完。C 语言里这种“自引用”是合法的，因为指针本身只占固定大小，不需要完整结构体的信息。这就像图纸上画了个箭头指向另一张还没画完的图纸，只要你知道图纸将来长什么样，箭头的指向本身是可以表达的。

整个链表就是靠这一串节点串起来的：每个节点的 next 指向下一个，最后一个节点的 next 指向 NULL，NULL 是链表里最重要的标志，它意味着“到头了”。遍历、查找、判空、防越界，全部依赖这个空指针作为终点哨兵。

3.2 头节点到底要不要：一个战略问题

写链表时首先就要决定：要不要设一个“头节点”？这是新手看不懂网上代码的重要原因之一。头节点也叫哨兵节点，它不存有效数据，专门放在第一个有效节点前面。加了它，链表哪怕一个有效元素都没有，也仍然存在一个实际节点，链表永不真正为空。

我的建议是：学习阶段明确搞懂两种写法，但实操和考试一律带头节点。原因有两个。第一，带头节点后，在头部插入和删除不用特殊处理。不带头节点的链表，删除第一个元素时就要修改头指针本身，函数里得用二级指针或者返回新的头指针，逻辑容易漏。带头节点后，头指针永远是那个哨兵，永远不变，插入删除逻辑统一。第二，遍历的判定条件好写：从头节点的 next 开始，走到 NULL 结束。没头节点的时候，判空要写成 head == NULL，加过头节点后，判空写 head->next == NULL 就行。

更直白地说，带头节点是把“链表是否为空”这个取决于外部指针状态的问题，转换为“哨兵后面有没有节点”这个内部状态，彻底避开了空指针无法访问内容的尴尬。

void initList(LNode** head) { *head = (LNode*)malloc(sizeof(LNode)); (*head)->next = NULL; }

有人会问，这个不存数据的节点不是浪费空间吗？一个指针变量而已，换来的是全代码逻辑的统一，这个交易非常划算。实际项目中几乎没人愿意为了省一个节点去处理一堆边界特判。

3.3 核心操作拆解：指针游戏的三条铁律

链表操作看着花哨，其实本质上就是围绕“一条铁律、两步操作”反复展开。铁律是：在插入或删除节点时，必须先处理“后继关系”，再处理“前驱关系”。具体来说，先让新节点指向后一个节点，再让前一个节点指向新节点，顺序绝不能反。

以在第 pos 个节点后插入新节点为例：

int insertAfter(LNode* preNode, ElemType x) { if (preNode == NULL) return 0; LNode* newNode = (LNode*)malloc(sizeof(LNode)); newNode->data = x; newNode->next = preNode->next; // 铁律第一步：新节点先指向后面的 preNode->next = newNode; // 铁律第二步：前节点再指向新节点 return 1; }

为什么第一步必须先让 newNode->next 指向 preNode->next？因为这两行交换顺序就会断链。如果先执行 preNode->next = newNode，原后续节点就找不到了，preNode 后面的整个链表都丢失了。这个顺序问题是链表新手第一大崩溃来源，写错了就在那疯狂 debug，怎么都找不到原因，其实就一句话的事。

删除操作同理，删除 preNode 的后继节点：

int deleteNext(LNode* preNode) { if (preNode == NULL || preNode->next == NULL) return 0; LNode* delNode = preNode->next; preNode->next = delNode->next; // 跳过被删除节点 free(delNode); // 释放空间 return 1; }

这里要先拿一个临时指针 delNode 保存待删节点，否则你执行完 preNode->next = delNode->next 后，delNode 的地址还知道，但通过链表已经无法访问它了，要释放内存必须保留这个指针。

遍历查找也是基本功。从头节点的 next 出发，每步检查是否为空，为空就停：

int findPos(LNode* head, int k) { LNode* cur = head->next; int count = 0; while (cur != NULL) { if (count == k) return cur->data; cur = cur->next; count++; } return -1; // 没找到 }

这类循环有统一写法：先检查节点是否为空，再访问它的数据和指针。顺序反过来，先 cur->next 再判空，空链表直接崩溃。

3.4 链表反转：所有面试题的老祖宗

链表反转是公认的经典题，也是检验是否真正理解指针操作的分水岭。不做任何多余分配，只靠三个指针原地反转，核心思路是：遍历链表，每次把当前节点的 next 指向前一个节点，然后整体向前推进。

LNode* reverseList(LNode* head) { LNode* pre = NULL; LNode* cur = head->next; // 从第一个有效节点开始 LNode* next; while (cur != NULL) { next = cur->next; // 先保存下一个节点，防止断链 cur->next = pre; // 当前节点指向前一个 pre = cur; // 前指针前进 cur = next; // 当前指针前进 } head->next = pre; // 头节点指向原来的末尾 return head; }

这段代码最关键的细节就在循环体里那三行。为什么返回前还要把 head->next 赋值？因为原来头节点后面挂的是反转前的第一个节点，反转后那个节点变成了最后一个，next 指向 NULL，如果不重新挂头节点，整个链表就断开了。

很多人第一次写反转，写到 cur->next = pre 这一步就陷入困惑：它把当前节点的 next 改了，那原来当前节点指向的后面那个节点怎么办？这就全靠提前保存的 next。如果你先移动 cur 再想访问后续节点，你已经崩溃了。这个过程强烈建议自己画一遍图：一个方框代表节点，箭头代表 next，走一步改一根线，画个三五个节点的例子，一次就能彻底记住。

4. 顺序表和链表选型：没有最好，只有最合适

4.1 复杂度分析不能只看表象

很多人背了一句话“数组查询快，链表增删快”，但这是简化过的结论，真实情况复杂得多。从大 O 复杂度看：

操作	顺序表	单链表
按位置访问	O(1)	O(n)
头部插入	O(n)（整体后移）	O(1)（有头节点）
尾部插入	O(1)（容量够时）	O(n)（需遍历到尾）
中间插入	O(n)	O(n)（需先遍历找到位置）
按值查找	O(n)	O(n)
按位置删除	O(n)	O(n)

单看这张表，链表似乎只有在头部增删时占便宜，其他时候都没优势，那为什么还要链表？因为大 O 掩盖了两个重要事实：一是链表不需要连续大块内存，碎片化的内存也能利用；二是链表存多少用多少，顺序表往往要预留容量。

但反过来，链表每个节点要额外存一个 next 指针，这也占内存。存储密度上，顺序表接近 100%，链表只有数据域占比，64 位系统里一个 int 数据加一个 8 字节指针，存储密度不到三分之一。数据量大的时候，链表的空间开销相当可观。

4.2 实际开发中的选型经验

我自己的判断标准向来是这几条。

第一，元素总量基本稳定、读写频率高，优先顺序表。比如保存一批配置文件项、排行榜列表，个数固定，访问多，顺序表配合下标访问是最优解。

第二，元素长度动态变化剧烈、且主要在头尾操作，优先链表。比如一个任务队列，任务不断从队尾加入、从队头取出，带头节点的单链表加一个尾指针，头尾操作都是 O(1)。

第三，元素结构庞大、每个节点携带大量字段时，链表的空间开销占比就下降了。比如每个节点是一个几百字节的大结构体，多一个 8 字节的指针根本不值一提，此时链表反而合适，因为它免去了顺序表整块搬迁时的内存复制成本。

第四，也是很多人容易忽略的一点：内存拷贝的实际成本。顺序表插入删除时搬运的是一次性的大块内存复制，实际速度往往比你的直觉快很多，因为现代 CPU 的顺序内存访问和优化非常强。反之链表要逐个节点访问，每次都要进行指针跳转，内存访问是离散的，缓存命中率会低，数据量大时链表反而更慢。很多人在数据分析、缓存敏感场景里用链表，最后发现性能不如顺序表，就是因为没考虑到缓存的影响。

4.3 快慢指针：链表的专属进阶思路

链表虽然随机访问慢，但在特定问题上可以做到非常优雅。快慢指针是链表的经典操作：一个指针一次走一步，另一个一次走两步，两个指针同时出发。当快指针走到链表末尾时，慢指针恰好走到中间节点。

LNode* findMiddle(LNode* head) { if (head == NULL || head->next == NULL) return NULL; LNode* slow = head->next; LNode* fast = head->next; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }

类似地，判断链表是否有环，也可以用快慢指针：如果存在环，快指针总会在环里追上慢指针。这两个问题常规思路都是 O(n) 或 O(n²)，快慢指针把它压到 O(n) 时间、O(1) 空间。面试里很多链表题，本质都是快慢指针的变体。

提示：写快慢指针时循环退出条件要写完整。既要是 fast != NULL，也要是 fast->next != NULL。漏掉一个，或顺序写反，奇数长度和偶数长度的链表就会一个正常一个崩溃。

5. 实操过程中的坑与经验

5.1 顺序表最常见的三种崩法

顺序表崩溃的模式比较集中，主要就三类。

第一，访问越界。最常见的原因是 length 和 capacity 搞混，或者插入位置判断错误。插入时允许 index == length，但删除时 index == length 就是越界。写代码前先在纸上标清楚有效下标范围是 0 到 length-1，插入的合法区间是 0 到 length，删除的合法区间是 0 到 length-1。

第二，扩容后数据没拷全。ensureCapacity 里只拷了 length 个元素，但有人会图省事用 memcpy 拷贝整个 capacity 大小的空间，结果把未初始化的区域也拷过去了，表面上没崩，实际上后面的数据全是垃圾值。

第三，扩容后忘记更新 length 的对应关系。其实 length 是元素个数，和容量无关，扩容不会改变 length。但有些代码中临时用了局部变量存旧值，搞混之后插入逻辑就乱了。

5.2 链表最常见的死循环与丢链

链表的问题往往是逻辑性的，代码能编译通过，但一运行就卡死或输出错乱。死循环的典型原因有三个。

第一个是遍历时判空条件写错。写成 while (cur->next != NULL) 而不是 while (cur != NULL)，那么最后一个节点的 next 是 NULL，循环会提前退出，尾部数据丢漏。如果写成 while (cur->next != NULL) 且 cur 本身可能是 NULL，空链表直接崩溃。标准写法一定是 while (cur != NULL)。

第二个是插入删除时断链。新节点先指向后一个，前一个再指向新节点，顺序反了就断。删除节点忘了保存被删节点的 next，直接改动 pre->next，也会断链。

第三个是反转链表时指针移动顺序错乱。我见过有人把 next 的保存放在 cur->next = pre 之后，此时 cur->next 已经被改了，后面那个节点早就找不到了，瞬间变成了一条断链加一条环。

遇到这类问题，我的调试套路很固定。首先检查所有涉及 next 的地方，确认没有“先改后取”。然后打印遍历结果，确认是否输出了全部节点。再检查循环退出条件。如果这三点都查不出问题，就专门打一个 tmp 指针，在每一步操作前输出当前节点地址、当前节点数据、当前节点 next 地址，肉眼跟一遍图，基本都找得到。