每次带新人做数据结构入门我第一句话基本都是线性表这个概念你哪怕毕业十年也躲不开。面试官爱问数组和链表的区别刷题网站天天考反转链表业务代码里面试者纠结用ArrayList还是LinkedList——说到底就是“顺序表”和“链表”这两个老冤家之间的博弈。今天我不打算念教科书直接把它们从内存模型、增删改查的真实代价、代码实操到工程选型一件件拆开讲透。如果你想搞清楚“到底什么时候该用链表、什么时候该用顺序表”或者正在准备数据结构实验课、面试手撕算法这篇内容可以作为一份还算靠谱的参考。1. 两种结构的内存模型决定了它们的性格差异1.1 顺序表一块连续空间里的“规矩人家”顺序表说白了就是数组底层是一段物理连续的内存。C语言里逻辑上第i个元素的地址直接拿起始地址加i * sizeof(T)算出来所以随机访问是天然优势。正是这个“连续”带来了两个后续影响第一你可以按下标一步到位地取任何元素第二一旦空间不够扩容就得整体搬家——提前估算容量到上限然后重新申请一块更大的内存把老元素一个一个复制过去。Java的ArrayList就是这么做的扩容倍率常见1.5倍C vector有的用2倍使用的人感觉不到但底层那一次次拷贝是真实存在的开销。顺序表有三个关键词物理连续、随机访问O(1)、插入删除O(n)。这个O(n)很有意思插入一个元素为了腾出一个坑从插入位置往后的所有元素都必须整体后移一位。别小看这个“挪”当你存的是结构体甚至大对象时逐字节搬移的时间会非常可观。删除操作同理把后面的元素挨个往前补位。所以顺序表在“按号找人”这件事上快得离谱在“腾地方”这件事上是个慢性子。我再补一个容易忽略的方向顺序表看着简单容量管理其实很讲究。预分配太大浪费内存太小频繁扩容实时性要求高的系统里扩容那几毫秒可能就闯祸了。所以严谨的做法是提前评估数据规模或者提供一个reserve接口让使用方提前申请容量别让扩容发生在关键路径上。1.2 链表指针串起来的“散装游击队”链表的内存是“散装”的每个节点单独分配空间彼此之间靠指针连接。一个节点通常包含数据域和指针域指针域指向下一个节点。因为不需要物理连续插入和删除就可以只操作指针——把前一个节点的next从指向旧节点改为指向新节点节点本身不用动。但代价也来了你想找第k个节点没有任何捷径只能从头指针出发沿着next一个一个往下走平均要走n/2步。链表还有好几个变种正好对应热词里的“单链表”“双链表”“循环单链表”“不带头结点的单链表”。单链表的节点只存一个next指针方向感非常强只能往前走。双链表在节点里再加一个prev指针可以回头走但每个节点多占用一个指针的内存。循环单链表把最后一个节点的next指回头结点遍历可以绕圈适合环形缓冲、约瑟夫环这类场景。不带头结点的链表省掉了那个占位用的头结点代码边界条件瞬间变多头指针本身随时可能被修改这个坑后面专门展开。还有一点链表的内存碎片问题在长期运行的服务里特别突出。频繁malloc和free会让堆上出现大量小块空洞嵌入式系统更是忌讳这一点。热词里提到“嵌入式链表代码示例”其实嵌入式不是不用链表而是讲究用内存池预分配节点避免裸malloc带来的碎片化。这个思路在工程上同样值得普通后端参考。1.3 一个类比记住核心差异把顺序表想象成电影院连排座位观众按号入座、整整齐齐。中途有新观众想坐第五排第五排之后的所有人都得起来挪一下。链表则像一根绳子串起一大堆气球气球物理位置散在各处绳子打结或解开就能完成增删但你想数到第八个气球必须从第一个开始一个个往下数。这个类比几乎能解释后续所有操作复杂度差异面试被问到“数组和链表有什么区别”从这个角度切入比硬背对比表更有说服力。2. 关键操作对比访问、插入、删除的真实代价2.1 按下标访问顺序表的降维打击顺序表按下标访问是真正的O(1)地址直接算出来不需要遍历。链表找第k个节点必须从头开始走k-1次next平均情况O(n)。这个差异在数据量大时是灾难性的十万个元素顺序表做一万次随机访问毫无压力链表做一万次随机访问相当于跑了几亿次指针跳跃。工程里凡是“按位置高频读取”的场景比如排行榜、缓存池、消息队列的索引结构顺序表都是更稳的选择。另外补充一点链表节点在内存里不是连续存放的CPU缓存命中率很低。顺序表因为连续局部性好一次缓存行加载能把好几个元素一起带出来。所以即使在理论上链表访问是O(n)实际跑起来可能比理论更慢。这个工程细节教科书写得少但线上压测区别明显。2.2 插入与删除链表终于扳回一局如果代码里已经持有某个节点的指针链表的插入和删除是O(1)的。插入一个新节点到p后面核心操作就两行newNode-next p-next; p-next newNode;。顺序表就惨了插入一个元素意味着从插入位置往后所有元素整体后移哪怕你有下标可以直接定位到目标位置搬移的成本依然摆在那里。但这里有个几乎所有初学者都会忽略的点很多人算复杂度时默认“知道了插入位置”可如果这个位置本身只能靠遍历才能拿到那定位就是O(n)。所以严谨的说法是链表的插入删除是“定位O(n)操作O(1)”顺序表是“定位O(1)移动O(n)”。到底哪种划算取决于数据规模、元素大小以及你手上是否已经有现成的节点指针。删除操作还有一种极易出错的情况不带头结点的链表删除第一个节点时必须修改头指针本身。如果函数里只传入Node *head那修改的只是形参调用方的头指针纹丝不动。正确做法是传二级指针Node **head或者让函数返回新的头指针。这也是热词里“不带头结点的单链表”被反复搜索的原因——一个占位的头结点看似浪费实则把边界条件大幅简化。2.3 一张表看清复杂度差异操作顺序表链表按下标/位置访问O(1)O(n)头部插入O(n)全部元素后移O(1)直接改头指针指定节点后插入O(n)定位移动O(1)持有目标指针时中间插入O(n)O(n)定位O(1)操作删除指定节点O(n)元素前移O(1)持有前驱指针时空间占用紧凑可能预留冗余每节点多一个指针额外开销这个表放进工程语境还能引发另一个思考顺序表扩容是1.5倍还是2倍均摊复杂度都是O(1)但扩容瞬间会卡顿调整步长只能缓解不能消除。链表没有扩容概念却要面对分配器开销和碎片问题。没有银弹只有针对场景做取舍。3. 代码实操三种语言五段代码把两种结构玩明白3.1 顺序表实现集合并集C语言热词里有一条“求解一般集合的并集问题的用顺序表实现完整c代码详解”这道题基本是所有学校的必修实验。思路很直接先复制集合A的全部元素到结果数组再遍历集合B如果B中某个元素没有在A里出现过就追加到结果数组末尾。#include stdio.h #include stdbool.h #define MAX_SIZE 100 // 求集合A和B的并集结果存入result返回并集长度 int unionSet(int a[], int n, int b[], int m, int result[]) { int k 0; for (int i 0; i n; i) { result[k] a[i]; } for (int j 0; j m; j) { bool exists false; for (int i 0; i n; i) { if (b[j] a[i]) { exists true; break; } } if (!exists) { result[k] b[j]; } } return k; } int main() { int a[] {1, 3, 5, 7, 9}; int b[] {3, 5, 8, 9, 11}; int result[MAX_SIZE]; int size unionSet(a, 5, b, 5, result); for (int i 0; i size; i) { printf(%d , result[i]); } printf(\n); return 0; }这段代码的时间复杂度是O(n*m)因为每个B元素都要在A里做一次线性查找。如果A和B都提前排好序可以优化到O(nm)两个下标同时走小的元素直接进结果相等时只进一个两个下标一起前进。面试能主动说出这个优化效果远好于只会背模板。再提醒一个坑题目如果没有给范围限制result数组开多大要心里有数。理论上并集最大长度是nm所以开nm大小最保险。用固定的MAX_SIZE兜底只是偷懒方案工程里得更严谨。3.2 指定位置插入建立单链表C语言热词“在指定位置插入建立单链表”几乎是每个数据结业实验的必备环节。我给出一个完整可运行的版本重点看插入函数怎么处理边界条件。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 在链表的第 pos 个位置插入值为 val 的节点pos 从 0 开始 void insertAt(Node **head, int pos, int val) { Node *newNode (Node *)malloc(sizeof(Node)); newNode-data val; newNode-next NULL; if (pos 0) { newNode-next *head; *head newNode; return; } Node *cur *head; for (int i 0; cur ! NULL i pos - 1; i) { cur cur-next; } if (cur NULL) { printf(插入位置越界\n); free(newNode); return; } newNode-next cur-next; cur-next newNode; } void printList(Node *head) { while (head ! NULL) { printf(%d - , head-data); head head-next; } printf(NULL\n); } int main() { Node *head NULL; insertAt(head, 0, 10); insertAt(head, 1, 20); insertAt(head, 1, 15); // 得到 10 - 15 - 20 printList(head); return 0; }这个代码里有三个细节必须展开。第一为什么插入函数用Node **head因为pos0时要修改头指针本身传一级指针改的是形参拷贝调用方的head不会变。这个坑在“不带头结点的单链表”场景里尤其致命。第二malloc之后要不要检查返回值实验课可以偷懒工程代码必须检查内存分配失败返回NULL直接使用就是空指针崩溃。第三越界时要记得free掉已经malloc出来的节点否则每次错误插入就泄漏一块内存。热词里“单链表的清空”同样在讲这件事malloc和free必须成对出现。这也是为什么我总强调链表的“遍历”基本功。实验报告里printList看起来像摆设但调试链表全靠它。遍历时每个节点打印地址和值一旦发现地址跳变或者重复问题位置立刻暴露。3.3 Java顺序表与Python链表逆序Java那边热词搜“java顺序表代码”的同学大多在写作业。手写一个简化版顺序表其实不难一个数组加一个size满了就扩容。public class SeqList { private int[] data; private int size; public SeqList(int cap) { data new int[cap]; size 0; } public void insert(int index, int value) { if (size data.length) { grow(); } for (int i size; i index; i--) { data[i] data[i - 1]; } data[index] value; size; } private void grow() { int newCap data.length (data.length 1); int[] newData new int[newCap]; System.arraycopy(data, 0, newData, 0, size); data newData; } public int get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(); } return data[index]; } }data.length (data.length 1)就是1.5倍扩容用位移代替乘法是性能敏感代码的常见写法。这段代码基本复刻了ArrayList的核心逻辑理解了它再去读JDK源码会顺畅很多。Python链表逆序是面试高频题思路是三个指针轮换推进。核心就一个先把next保存下来再反转cur的next指向然后三个指针整体前移。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverse_linked_list(head): prev None cur head while cur: nxt cur.next # 1. 先保存后继避免指针丢失 cur.next prev # 2. 反转当前节点指向 prev cur # 3. 前驱指针前移 cur nxt # 4. 当前指针前移 return prev # 结束时 prev 就是新头节点这段代码手撕时最容易翻车的就是忘了“先保存nxt”。一旦先执行cur.next prev原来的后继节点就找不到了链表在后面直接断掉。三指针轮换的顺序是铁律保存、翻转、推进一步都不能乱。逆置完成后原来的头节点变成尾节点它的next正好是None所以prev初始就是None逻辑非常自洽。4. 工程选型与避坑指南4.1 四问法决定用哪个第一问主要操作是读还是写读多写少选顺序表写多读少优先链表。第二问数据规模变化大不大频繁在头部或中间插入删除链表更合适几乎只做尾部追加顺序表更香。第三问元素本身多大如果元素是几百字节的大结构体顺序表扩容和插入时的整体搬移会把大量字节拷来拷去链表只改指针代价小很多。第四问平台有没有内存约束嵌入式环境、长时间运行的服务器进程要警惕链表malloc/free带来的碎片化必要时用内存池管理节点。这四个问题想清楚绝大多数选型纠结都能化解。ArrayList和LinkedList之争真正常见结论是如果你不确定先用顺序表。因为顺序表缓存友好、访问快、实现简单而LinkedList的“O(1)插入”往往需要你手里已经有节点指针才成立业务代码里常常要先get(index)找位置结果又搭进去O(n)。Java官方甚至直接建议不要随便用LinkedList。4.2 常见问题排查速查表写实验或者调线上问题的时候遇到下面的现象直接对号入座现象原因解法链表插入后输出丢前半段头指针没更新用二级指针或返回新头删除节点后程序崩溃free后还访问了该指针先保存nextfree后置NULL顺序表插入越界却无报错size增长逻辑出错插入前先检查size1是否超容量链表遍历死循环尾节点next没置NULL创建节点时把next初始化为NULL并集结果重复没判断B元素是否已存在按并集算法先查A再追加扩容后老数据丢失拷贝范围错误拷贝size个而非newCap个元素其中“尾节点next没置NULL”几乎是新手链表代码的头号杀手。malloc出来的内存里next是随机值不手动初始化printList走到最后一个节点后继续顺着垃圾指针乱跑最后段错误。这个坑学校老师不强调但自己写一遍就能深刻体会。4.3 实操中的独家经验我写链表这些年总结出几个比较实用的习惯。一是定义节点结构体时顺手在注释里标明指针指向谁比如“next指向下一个节点”防止自己过两天回来看代码还要推理半天。二是链表操作尽量封装成函数别让业务代码里到处裸改指针。散落的指针操作调试起来非常痛苦封装之后每层逻辑都能单独验证。三是动手写代码前先在纸上画一画头结点和各个指针的变化方向特别是插入删除涉及多指针的场景画清楚再写写完基本一次过。另一个容易被忽视的经验是关于“双链表”和“循环单链表”的取舍。需要从尾部往头走才考虑双链表需要环形处理比如约瑟夫环、音视频帧缓冲才考虑循环单链表其他情况单链表足够。别为了炫技引入不必要的复杂度。嵌入式场景我补充一点很多RTOS源码里的链表是侵入式设计链表节点直接嵌入业务结构体而不是外包一层Node这样可以用container_of宏从节点指针反推业务结构体首地址省一次额外分配。业务开发暂时用不上但了解Linux内核的list_head有助于理解更高阶的链表组织方式。再补充一个很多人写顺序表时爱犯的毛病按值删除元素时习惯先遍历找位置再调用一个按下标删除的函数结果白白遍历两次。正确做法是一次遍历同时维护前驱指针找到目标后先处理前驱的next再释放当前节点一步到位。这正是顺序表和链表思维的分水岭——用顺序表时脑子里想的是“搬移”用链表时脑子里想的是“指针切换”一旦转换过来后面刷数据结构题会顺畅很多。我个人带项目的体会是数组和链表这对基础的线性容器几乎是一切高级数据结构的底色。字符串、队列、图算法最终都会落到这两种思路的组合上。把连续内存和散列指针这两个核心矛盾吃透再去学哈希表、跳表、B树理解成本会低一个量级。如果当初有人用“连排座位”和“气球绳子”这两个类比帮我开窍我大概能少走不少弯路。希望这篇也能帮你把这两块硬骨头啃下来。