先聊点实在的。顺序表和链表这两个名字几乎出现在每一本数据结构教材的前三章也是很多初学者第一次觉得“数据结构有点绕”的地方。当时我学到这里最大的困惑是明明数组已经够用了搞个链表出来还要 malloc、还要指来指去到底是图啥后来自己写过一阵子业务代码、刷过一些题才慢慢理解这哥俩本质上代表了两种截然不同的存储世界观。顺序表靠“物理相邻”换取随机访问的速度链表靠“指针串联”换取插入删除的灵活没有绝对的好坏只有合不合适的场景。这篇文章我想从内存布局、基础操作、典型例题到工程选型把顺序表和链表拆开揉碎讲一遍。适合刚学数据结构还没建立感觉的同学也适合准备笔试面试想梳理一遍的人。我会把实现细节、复杂度分析还有我踩过的坑都放进去尽量让看完的你能直接写出能跑的代码而不是只会背概念。1. 同一个线性表两种存储世界观1.1 顺序表一段连续内存的“物理排队”顺序表说白了就是数组。它的核心特征是所有元素按顺序躺在一段连续的内存空间里一个挨一个物理上是紧挨着的。你把第一个元素的地址拿到手想找第 i 个元素直接拿首地址加上 i 乘以单个元素大小就行这就是教科书上说的随机存取。这种连续布局带来的好处非常直观。你要查第 5 个元素不用从头数算一下偏移就能直接定位。CPU 在加载数据时也是一片一片按缓存行加载的连续内存天然对缓存友好所以顺序表在实际运行中的速度往往比理论分析还要快一点。代价就是插入和删除需要“搬砖”往中间塞一个元素后面所有元素都得往后挪一位删除一个元素后面所有元素都得往前挪一位。数据量一大这个挪动的成本就很扎眼。我用一个生活化的例子来解释顺序表就像电影院连座票你买了一张第 5 排的票座位号直接决定了你的位置进场不用犹豫但如果有人要坐到你边上整排的人可能都得往旁边挪一挪这就是插入开销的来源。1.2 链表各自租房用指针串起来链表走的是另一条路。它的每个节点都是单独分配的内存不保证物理相邻每个节点里存着自己的数据还有一个指针指向下一个节点的地址。你要找第 i 个元素只能从第一个节点开始顺着指针一步一步往下走这叫顺序存取。这种设计的优点在于插入和删除非常痛快。只要你能找到目标位置的前一个节点改一下指针指向就能完成操作不需要搬动其他任何数据。缺点是随机访问很痛苦想拿第 100 个元素就得从前往后数 99 次。而且每个节点还要多占一份指针空间典型的时间换空间、空间也换时间的“两头都沾”。还拿电影院类比链表就像你组织了一场城市定向活动每个人只知道下一个人住哪你想找第 10 个人就得问第 9 个人第 9 个人得问第 8 个人。但要临时往队伍里插一个人只要改两条“线索”就行其他人根本不用动。这两种方案能长期共存根本原因是它们解决的是不同的问题。如果你主要操作是按下标查数据选顺序表如果你的操作以频繁增删为主、又很少按下标访问那链表更合适。后面我会用一张对比表把这些差异量化出来。2. 顺序表从建表到扩容把每个细节抠明白2.1 动态数组的扩容策略为什么是翻倍C 语言里传统数组的长度是写死的用起来很别扭。实际工程里我们基本都用动态顺序表也就是 C 的 vector、Java 的 ArrayList 或者自己手写的动态数组。动态扩容有一个常见套路当元素个数等于当前容量时申请一块更大的内存把旧数据复制过去然后释放旧空间。扩容倍数通常取 1.5 或 2这个细节很多人没注意。为什么不能每次只扩一个元素的位置因为那样每插入一个元素都可能触发一次 O(n) 的搬迁总代价会变成 O(n^2)。翻倍扩容的核心收益在于随着容量指数增长触发扩容的次数非常少把每次扩容的复制成本均摊到所有插入操作上每个插入的均摊复杂度就是 O(1)。我用一个简单计算说明。假设初始容量是 1按 2 倍扩容到 n总共扩容约 log2(n) 次每次复制的元素数分别是 1、2、4、8……加起来约等于 2n。也就是说插入 n 个元素的总体复制量是 O(n)平均到每次插入就是 O(1)。这也是面试里常问的“vector 的 push_back 为什么均摊 O(1)”的标准答案。下面给一个简化的 C 语言动态顺序表示例重点看扩容逻辑#include stdio.h #include stdlib.h typedef struct { int *data; int size; // 当前元素个数 int capacity; // 当前容量 } SeqList; void init(SeqList *list) { list-capacity 4; list-size 0; list-data (int *)malloc(sizeof(int) * list-capacity); } void push_back(SeqList *list, int value) { if (list-size list-capacity) { list-capacity * 2; list-data (int *)realloc(list-data, sizeof(int) * list-capacity); } list-data[list-size] value; } void printList(SeqList *list) { for (int i 0; i list-size; i) { printf(%d , list-data[i]); } printf(\n); } int main() { SeqList list; init(list); for (int i 1; i 10; i) { push_back(list, i); } printList(list); free(list.data); return 0; }注意代码里用的 realloc 在扩容时可能原地扩展也可能搬去新地址但对使用者来说返回值才是新的有效地址所以一定要把返回值赋回给 data。很多人写 realloc 时忽略返回值后续访问的是旧指针一旦内存被搬走就是访问已释放的内存这是非常经典的坑。2.2 插入删除操作的“搬砖”细节顺序表的插入和删除难点不在指针而在元素的移动。往第 pos 个位置插入元素时需要把 pos 到 size-1 的元素统一往后移一位然后再把新元素放进去。删除时则反过来把后面的元素往前覆盖。为什么必须从后往前移动因为你要腾出位置给新元素如果从前往后覆盖前面的元素会盖掉后面还没移动的元素。以插入为例必须先把最后一个元素挪到 size 位置再挪倒数第二个到 size-1依次类推最后腾出的 pos 位置才能安全写入。删除操作则是从 pos1 开始往前覆盖直到把最后一个元素覆盖到 size-2 的位置。这里有一个很多初学者会忽略的问题插入和删除后 size 的更新顺序。插入要先判断容量是否已满再把元素后移最后 size 加一删除要先 size 减一再往前覆盖或者先覆盖再 size 减一都可以但要注意别让最后一格残留值影响判断。实际工程里删除元素我一般会顺手把末尾残留的引用置空防止内存泄漏这在存放对象指针的顺序表里尤其重要。下面给出插入和删除的核心代码int insert(SeqList *list, int pos, int value) { if (pos 0 || pos list-size) return -1; if (list-size list-capacity) { push_back(list, 0); // 触发一次扩容等价于 capacity * 2 list-size--; // 把临时加的元素去掉 } for (int i list-size; i pos; i--) { list-data[i] list-data[i - 1]; } list-data[pos] value; list-size; return 0; } int erase(SeqList *list, int pos) { if (pos 0 || pos list-size) return -1; for (int i pos; i list-size - 1; i) { list-data[i] list-data[i 1]; } list-size--; return 0; }这段代码里插入时的“借用 push_back 触发扩容”有点取巧仅为展示思路。真实项目里建议把扩容逻辑单独抽成 ensure_capacity 函数直接把容量翻倍代码更清晰也不会产生上面这种临时加元素再减掉的怪操作。我在初学阶段写过类似的怪代码后来 Code Review 被同事点名说“意图不清晰”从那之后扩容就单独写了。2.3 洛谷 P3156 询问学号顺序表的教科书应用刷题的时候经常看到顺序表的经典应用题比如洛谷 P3156 【深基15.例1】询问学号。题目大意是有 n 个学生按顺序排好每个人有一个学号然后给 m 次询问每次问第 x 个学生的学号是多少。n 和 m 都可能很大要求快速回答。这个题的核心就是“按下标查询”天然就是顺序表的主场。直接把学号按输入顺序存进数组每次询问输出 arr[x-1] 即可时间复杂度 O(1)。如果非要用链表存每次查询都得从头走到第 x 个节点单次查询 O(x)m 次下来很可能超时。这个例子特别适合新手理解数组下标的威力按下标访问本质就是“首地址 偏移量”一次算术运算直接拿到目标内存这是链表做不到的。当时我做这个题的时候顺手对比过两种写法链表虽然也能过小数据但大数据量下差距肉眼可见。顺序表的第一个实战优势就体现在这里。3. 链表指针操作、逆序反转与高频考题3.1 节点定义和单向链表构建链表的基础是节点。单链表节点定义在 C 语言里就是一个结构体数据域加指针域C 里用 struct 一样能写也可以用 class 包装。下面是最常见的定义方式typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int value) { Node *node (Node *)malloc(sizeof(Node)); node-data value; node-next NULL; return node; }建立一个单链表通常有两种方式头插法和尾插法。头插法每次把新节点插到头节点前面代码短但数据顺序会反转尾插法需要遍历到尾部或维护一个尾指针数据顺序保持输入顺序。笔试和面试里如果在 O(1) 时间要建立链表但不在乎顺序用头插需要保持顺序用尾插。我当年学链表最容易晕的就是插入一个新节点为什么“先处理新节点的 next再改前驱的 next”。道理其实很简单你先改前驱的 next后面的链表就丢了新节点还没接上整个链表就断了。所以铁律是先连后断。先让新节点的 next 指向前驱原本的 next再把前驱的 next 指向新节点。给出尾插法代码Node *append(Node *head, int value) { Node *node createNode(value); if (head NULL) return node; Node *p head; while (p-next ! NULL) { p p-next; } p-next node; return head; }这段代码在空链表时会直接返回新节点作为头节点。这是一个很常见的细节很多初学者忘了处理 head 为 NULL 的情况一上来就 while (p-next) 然后对 NULL 解引用直接段错误。写链表函数第一件事就应该想清楚“传进来的指针可能是空吗”把所有空指针分支都考虑一遍。3.2 单链表的插入、删除与完整遍历实现链表的插入分三种情况头部插入、中间插入、尾部插入。中间插入需要先找到目标位置的前驱节点 pre然后执行“先连后断”的指针操作。删除节点也需要找到前驱节点 pre把 pre-next 跳过待删节点直接指向待删节点的后继。为什么总是强调“前驱”因为单链表只有指向后继的指针你只拿到了当前节点是没法知道谁在它前面的。这也是单链表删除节点的一个经典限制如果你只知道要删除的节点指针而且它是最后一个节点那没有头节点的情况下就没办法把前驱的 next 置空只能靠遍历找前驱。这也是为什么很多面试题会考“给定一个节点如何在不知道头节点的情况下删除它”通常做法是把后继的值拷贝过来再删除后继这是一种精妙的“偷梁换柱”。删除函数的实现可以这样写int deleteNode(Node **head, int value) { if (*head NULL) return -1; Node *dummy (Node *)malloc(sizeof(Node)); dummy-next *head; Node *pre dummy; while (pre-next ! NULL pre-next-data ! value) { pre pre-next; } if (pre-next NULL) { free(dummy); return -1; } Node *toDelete pre-next; pre-next toDelete-next; free(toDelete); *head dummy-next; free(dummy); return 0; }这里我引入了虚拟头节点 dummy这个技巧非常实用。它解决了“删除的是第一个节点时头节点本身要变”的问题。如果不引入 dummy你就得单独判断 head 是否需要更新代码会多出不少分支。虚拟头节点让所有节点的删除操作统一成“找前驱改 next”无需再对头节点特殊处理。我在博客里给初学者讲链表时永远推荐先学会 dummy 节点写出来又安全又直观。遍历链表则是基本功从 head 出发不断往后移动指针直到 NULL。很多人会写成 while (p ! NULL) 然后打印 p-data注意别把 p 和 p-next 在循环条件里搞混否则打印到最后一个节点时又往前走了一步越界访问空指针。3.3 单链表逆序从“经典高频题”到手把手推导单链表逆序应该是链表题里出场率最高的题目之一几乎每一场面试都可能遇到。三指针迭代法是最容易理解的方法。思路是用 pre、cur、next 三个指针cur 指向当前尚未反转的节点pre 指向已经反转好的链表头next 临时保存 cur 原本的后继。每一步做三件事保存 next把 cur-next 指向 pre三个指针整体前移。循环结束后pre 就是新链表的头节点。以链表 1 - 2 - 3 - NULL 为例初始pre NULLcur 1next 2第一步cur-next 指向 NULL链表变成 1 - NULLpre 移到 1cur 移到 2第二步cur-next 指向 1链表变成 2 - 1pre 移到 2cur 移到 3第三步cur-next 指向 2链表变成 3 - 2 - 1pre 移到 3cur 变为 NULL结束返回 pre结果就是 3 - 2 - 1这个过程的动画感很强我建议初学者在纸上画出每一步的指针变化比看十遍代码都管用。代码实现Node *reverseList(Node *head) { Node *pre NULL; Node *cur head; while (cur ! NULL) { Node *next cur-next; cur-next pre; pre cur; cur next; } return pre; }这里的关键就是 next 指针必须提前保存。如果不保存执行完 cur-next pre 之后原来的后继就丢了链表直接断掉。我自己第一次写的时候忘了保存 next调试了半小时最后还是画图才反应过来。还有一种递归写法代码很短但理解成本高核心是“把 head 之后的链表反转再让 head 的下一个节点回头指向 head”。递归版在面试里偶尔会问但实际写代码我更推荐迭代版既不爆栈也更容易调试。如果你想把两个版本都掌握可以先写几遍迭代版再尝试理解递归版。3.4 链表相交与链表排序的解题思路热词里出现了“3898 · 链表相交(二)”和“链表排序”这两个问题也很有代表性。链表相交的意思是两个单链表从某个节点开始后面的节点全部共用。因为单链表的 next 指针只有一个一旦相交后续路径必然完全重合形成 Y 字形不可能出现 X 形后再分开的情况。求相交节点的经典思路是先分别统计两个链表的长度让长链表的指针先走长度差步然后两个指针同步前进第一次相遇的节点就是交点。时间复杂度 O(n m)空间复杂度 O(1)。也可以用哈希集合把 A 链表的节点全部加入集合再遍历 B 找第一个在集合里出现的节点但空间复杂度会变成 O(n)。面试优先讲双指针法因为它不需要额外空间。链表排序则是一个经典考点。链表不像数组那样方便二分归并但归并排序天然适合链表。因为归并排序的核心操作是“合并两个有序序列”只要求顺序访问不需要随机访问这和链表的能力完全匹配。实现思路用快慢指针找到链表中点把链表切成两半递归排序再合并。合并两个有序链表本身也是高频题。基本套路是创建一个虚拟头节点然后用两个指针分别指向两个链表的头部每次取较小值的节点接到新链表尾部。注意当其中一个链表为空时直接把另一个链表整体接上即可不需要一个个节点遍历。这个“直接接过去”的细节能省很多时间也反映了链表操作里指针赋值的高效性。4. 顺序表 vs 链表复杂度只是及格线4.1 一张表看懂时间复杂度差异很多同学把选择依据笼统理解为“查多用数组增删多用链表”这个说法方向上没错但不够精确。真正决定差异的是操作位置和操作频率。我把常见操作的时间复杂度整理成了一张表操作顺序表链表按下标/按值访问O(1)O(n)头部插入O(n)所有元素后移O(1)尾部插入O(1) 均摊扩容时 O(n)O(1) 有尾指针否则 O(n)中间插入O(n)移动一半元素O(1) O(n) 查找位置删除头部O(n)O(1)删除尾部O(1)但要处理剩余元素O(n)需找前驱查找某个值O(n)有序可二分 O(log n)O(n)无法二分从表里能发现一个容易忽略的点链表的“插入删除 O(1)”是有前提的前提是你已经拿到了目标位置的前驱节点。如果只知道要插入的值你得先遍历去找到位置这时候查找成本 O(n) 才是大头插入本身反而无所谓。所以实际工程里链表只有在“你已经持有插入位置的指针”时才真正占优比如 LRU Cache 场景里配合哈希表定位节点。尾部插入也值得细说。单链表如果没有尾指针每次尾部插入都要遍历到末尾复杂度 O(n)。很多人在实现时加了 tail 指针尾部插入才降到 O(1)。顺序表的尾部插入虽然偶尔触发扩容但均摊下来是 O(1)。所以“尾部反复插入”这件事顺序表往往比链表更省心。4.2 缓存局部性顺序表“看起来更快”的秘密只看复杂度表有的同学可能会觉得两者差距没那么大但实际跑起来顺序表的优势往往比理论值更大尤其是在遍历场景。这个差距主要来自 CPU 缓存。CPU 读取内存不是按字节读的而是按缓存行读取通常 64 字节。顺序表元素在内存里紧挨着你访问第 0 个元素时第 1、2、3 个很可能已经一起被加载进缓存了后续访问几乎不碰内存。链表节点散布在堆的不同位置每访问一个节点大概率要重新从内存加载频繁发生缓存未命中速度自然慢。我自己做过一个简单测试在 100 万元素规模下遍历一遍顺序表和单链表顺序表耗时大约是链表的 1/5 到 1/10。这个差距不是常数级的而是“缓存友好”和“缓存不友好”的差距。所以在性能敏感的代码里即使理论复杂度一样我也会优先考虑连续内存的存储方案。这是很多教科书不会写、但真实工程里非常关键的一点。面试求职时如果你能在答完复杂度后主动补一句“顺序表因为缓存局部性更好实际遍历性能会优于链表”会显得你对底层原理有真正的理解。4.3 工程场景选型建议选型这件事说到底要看你的核心操作是什么。我给你整理了一些典型的场景参考需要频繁按下标访问元素比如排行榜、游戏实体列表、常驻内存的配置表用顺序表。读取性能高代码也简单。经常在头部插入删除比如实现一个最近访问列表、消息队列的头部消费场景用链表更划算顺带配合头指针操作 O(1)。需要实现 LRU 缓存经典方案是哈希表 双向链表。哈希表负责 O(1) 查找双向链表负责 O(1) 移动节点到头部这个场景链表不可替代。数据规模小且基本一次性遍历优先用顺序表。省内存、省空间、缓存友好。元素本身很大插入删除极其频繁节点数量动态变化明显链表可以避免大块内存的频繁复制。内存碎片也是个考虑因素。链表每次创建节点都要分配一次小块内存长期运行容易产生内存碎片顺序表通过一次大块分配和翻倍扩容碎片相对少一些。对嵌入式、长期服务的系统来说这一点尤其值得注意。我实际写业务代码的经验是大部分情况下顺序表是够用的而且更好调试。链表只在几个特定场景里大放异彩比如 LRU、约瑟夫环、大规模增删且不常访问的需求。所以选型时别上来就图链表“插入快”而忽略查找代价先问清楚自己的操作模式再拍板。5. 实战中的坑与调试思路5.1 空指针、野指针和链表断链链表调试最经典的就是空指针异常和断链问题。空指针多见于没有判空就解引用断链多见于插入删除时指针操作顺序写反比如先改了前驱的 next再想去拿后继就发现已经空了。我在线下帮学弟学妹看代码时发现90% 的链表 bug 集中在三个地方创建节点后没有初始化 next 为 NULL、插入时顺序错误、删除时没有释放节点内存。前两个会导致程序崩溃后一个会导致内存泄漏。排查这种问题一个很有效的办法是画图。把每一步前后的链表状态画出来标清楚当前预、当前、下一个指针的位置很快就能定位是哪一步把链子搞断了。另外最好在写完链表操作后打印一遍完整链表确认结果。我习惯写一个 debugList 函数每次操作后调用它把链表从头到尾打印出来。这个方法看起来笨拙但排查效率极高。很多人在链表出问题时盯着代码反复看不如实际跑一次看输出。5.2 顺序表扩容后的经典问题顺序表扩容之后最经典的问题就是“之前的指针还能不能用”。在 C 语言里如果用 malloc 分配数组然后手动扩容扩容后内存可能搬到了新地址旧指针就变成了悬垂指针。C 的 vector 也有类似问题扩容后迭代器会失效。我之前写过一段代码先把一个元素的地址存下来再往 vector 里 push 很多元素触发扩容结果旧地址内容已经变了排查了很久才发现是扩容导致的内存搬移。避免方法很简单不要长期持有顺序表内部元素的地址或迭代器需要时通过下标实时获取。C 里如果确实需要在扩容过程中保留元素引用可以用 deque它扩容时不会移动已有元素或者预留容量 reserve从根上避免反复扩容。还有一类坑是容量和大小搞混。size 是当前元素个数capacity 是当前容量。插入前判断的是 size 是否等于 capacity很多人会误写成 capacity导致容量已经满了还在写入越界破坏内存里的其他数据。这类 bug 很隐蔽最好在 insert 函数入口处统一判断 size别把两个值混用。5.3 链表相交与环形链表的调试心得热词里提到的“3898 · 链表相交(二)”这类题目调试时容易犯一个认知错误以为两个链表相交就是值相等。实际上链表相交判断的是节点地址相等不是数据域相等。两个不同的节点可能存着相同的值但它们的地址不同不代表相交。判断环的经典问题是“给定一个链表判断有没有环找环入口”。快慢指针法是最常见的方案快指针每次走两步慢指针每次走一步如果相遇说明有环。找环入口时一个指针从头节点出发一个指针从相遇点出发每次都走一步再次相遇的点就是环入口。这个结论很多面试官会问“为什么”本质是因为快指针走的距离是慢指针的两倍通过等式推导可以得出入口到相遇点的距离与头节点到入口的距离相等。调试链表相关题目时我强烈建议自己在本地写一个“制造相交链表”或“制造带环链表”的辅助代码。自己用 malloc 创建一串节点手动把某个节点的 next 接到另一个链表的中间节点然后运行算法这样能直观验证你的判断逻辑而不是直接在刷题网站上盲调。5.4 刷题与笔试的常见应对策略如果目标是面试和笔试链表题目的“题感”能在短时间内快速建立。我总结出来的核心套路是准备虚拟头节点操作前先画图牢记“先连后断”注意判空。顺序表题目则在“边界条件”上做文章插入位置是 0 还是 size删除位置是 size-1 还是不存在扩容后容量是否足够这些边界条件的判断几乎决定了代码能不能一次通过。另外强烈建议把常见题型过一遍单链表逆序、链表相交、环形链表、链表排序、合并两个有序链表、删除倒数第 N 个节点、找链表中间节点。这七道题熟练之后大部分链表题都能转化为其中某一种模式的变体。顺序表方面则重点看二分查找、双指针、滑动窗口这些题目在数组里很常见本质都在吃“随机访问”的红利。我自己练算法时的经验是不要只满足于代码跑通要能说清楚每个关键步骤为什么这么写。面试官往往更看重你的推导过程而不是你背下来的代码。你如果能画着图把“链表逆序每一步指针怎么变”讲明白基本就稳了。6. 写在最后的一点个人体会我从接触数据结构到现在顺序表和链表的代码写过不下几十遍。每次重新实现一遍都会对“数据结构是存储和组织数据的方式”这句话多一层理解。顺序表的优雅在于简洁和高效连续内存、下标访问、缓存友好这些特性让它在绝大多数常规场景里成为默认选择链表的优雅在于灵活和动态通过指针打破物理空间的限制让数据组织拥有了更多可能性。如果让我给新手一个建议我会说别只背结论一定要亲手把两种结构都从零实现一遍包括插入、删除、逆序、扩容这些操作然后跑起来测试。你写出的每一个段错误都是最真实的老师。特别是链表画图比看代码更重要把指针的每一步变化画在纸上你会恍然大悟。最后再分享一个小技巧学数据结构之前先强迫自己回答一个问题——这种数据结构最适合解决什么痛点带着问题去学你会发现顺序表和链表不是两个需要背诵的知识点而是两把各有用处的工具。工具没有高低会选工具才是本事。