顺序表与链表：存储结构、代码实现与工程选型全解析

顺序表和链表这两个词对搞过编程的人来说就像馒头和米饭人人都吃过但真让你说清楚两者区别很多人反而会卡壳。我这些年面试过不少候选人也带过不少课程设计发现一个很有意思的现象大家背得出来“数组查询快、链表插入快”但一旦上手写代码要么把顺序表扩容写错要么链表指针一改就死循环。这篇文章干脆把顺序表和链表从头到尾拆一遍从存储结构、核心操作、代码实现到嵌入式场景和面试题帮真正想搞懂的人把这块地基打牢。适合的人群很明确正在学数据结构的在校生、准备技术面试的求职者以及工作中需要自己实现基础容器却不太确定怎么选的开发同学。1. 存储模型决定了命运为什么顺序表能随机访问链表却只能“顺藤摸瓜”很多教材上来就甩复杂度表格但没解释清楚背后的物理原因。我觉得这才是理解顺序表和链表的第一步它们的存储模型从根本上决定了各自的性格。1.1 顺序表一块连续内存的“肌肉记忆”顺序表的底层就是数组C语言里对应int a[100]Java里对应ArrayList内部的Object[]。它的核心特征是“一段连续的、地址递增的内存空间”。因为连续你访问第 i 个元素时根本不用从头找直接算地址base_addr i * sizeof(element)这就是教科书上说的“随机访问 O(1)”。这个能力是物理层面给的不依赖任何遍历逻辑。连续内存还有一个隐藏优势缓存友好。CPU读取内存时不是一次只读一个字节而是成块地预取到高速缓存里。顺序表访问第 i 个元素时它附近的若干个元素大概率已经被缓存了所以挨着遍历的时候速度极快。这也是为什么工程上很多貌似该用链表的场景实测用数组反而更快的原因之一。我用一个生活类比顺序表就像电影院的一排固定座位座位号连续你知道自己是7排5座一步就能走过去而且旁边坐的是谁你扫一眼就清楚。顺序表的代价也来自连续内存插入和删除一个元素后面所有元素都得挪位置。最坏情况在头部操作整个表全部搬家。同时表长度是固定的动态数组也是固定容量扩容搬移所以你还得关心容量够不够、要不要扩容。1.2 链表散落节点的“手拉手队列”链表则是另一个极端。每个节点可以放在内存的任意角落节点之间通过指针“手拉手”连起来。C语言里就是struct Node { int data; struct Node *next; };这个data是数据域next是存着下一个节点地址的指针域。正因为物理位置不连续你没办法直接算出第 k 个节点在哪只能老老实实从头节点开始顺着next一个节点一个节点跳过去这就是“顺序访问 O(n)”。链表的优势在于动态拼接。只要你知道某个节点的前驱插入和删除只需要修改指针指向不需要搬动任何元素。再换句话说顺序表的“血”是连续的伤筋动骨要动全身链表的“血”是分散的打断一根线重新接上就行。但散落分布的代价很大指针本身要占内存64位系统下每个 next 占8字节而且节点在内存里东一个西一个CPU预取时命中率低遍历效率肉眼可见地不如数组。别忘了链表还会频繁malloc每次分配出的节点内存很可能不连续进一步加剧缓存不友好。链表就像一条用无数根绳子串起来的风筝线你想拿第100只风筝必须拽着线一只一只数过来。1.3 复杂度表不是故事的全部平均情况掩盖了哪些细节教科书上常用的对比表是这样操作顺序表单链表按下标/按值访问O(1)O(n)头部插入O(n)O(1)尾部插入O(1)*O(1)**中部插入O(n)O(n)***删除O(n)O(n)***带星号的地方就是容易误导人的地方。顺序表尾部插入确实是 O(1)但前提是容量够一旦容量不够需要扩容要把老数据全部复制到新内存单次操作退化到 O(n)。不过如果按“摊还分析”来看扩容发生的频率低平均下来每个元素仍然近似 O(1)这也是动态数组能用得这么爽的原因。链表尾部插入能不能 O(1)取决于你有没有维护尾指针。很多初学写的链表只保存一个head每次尾部插入都得从头走到尾那是 O(n)。维护一个tail指针后尾部插入才变成真正的 O(1)。另外链表“中部插入 O(n)”乍一看和顺序表一样但两个 O(n) 的含义完全不同链表花时间是“找到那个节点”找到之后插入是 O(1)顺序表花时间是“搬动后续所有元素”。这个区别在面试里稍微追问一下就能看出水平差在哪。2. 顺序表实战用完整C代码实现集合并集顺便看清移动元素的成本网上搜顺序表很容易搜到“求解一般集合的并集问题”这种经典题目。拿这道题做例子很合适因为它既要遍历、又要判重、还要插入几乎把顺序表的核心操作全用了一遍。2.1 问题本身怎么拆解题目要求给定两个集合 A 和 B用顺序表存储求 A∪B结果里不能有重复元素。算法思路不复杂先把 A 的全部元素复制到结果表里。遍历 B 的每个元素在结果表里查一遍如果没出现过就追加到结果表末尾。关键在于第二步的判重。顺序表没有任何“哈希能力”查一个元素只能线性扫描所以并集算法的整体复杂度是 O(lenA lenB × lenResult)最坏情况下是 O(m×n) 级别。这就是顺序表做集合运算的瓶颈。2.2 完整C语言实现下面是一份可以直接跑通的完整代码我自己在课程设计里也是这么写的适合初学者逐行消化#include stdio.h #include stdlib.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int length; } SeqList; void init(SeqList *list) { list-length 0; } // 在顺序表中查找元素返回下标找不到返回-1 int find(SeqList *list, int value) { for (int i 0; i list-length; i) { if (list-data[i] value) { return i; } } return -1; } // 在末尾追加元素注意考虑容量已满的情况 void append(SeqList *list, int value) { if (list-length MAX_SIZE) { printf(顺序表已满无法追加 %d\n, value); return; } list-data[list-length] value; list-length; } // 求并集把集合A和集合B的并集写入 result void unionSet(SeqList *A, SeqList *B, SeqList *result) { init(result); for (int i 0; i A-length; i) { append(result, A-data[i]); } for (int i 0; i B-length; i) { if (find(result, B-data[i]) -1) { append(result, B-data[i]); } } } int main() { SeqList A, B, C; init(A); init(B); append(A, 1); append(A, 2); append(A, 3); append(A, 5); append(B, 3); append(B, 4); append(B, 5); append(B, 6); unionSet(A, B, C); printf(A ∪ B ); for (int i 0; i C.length; i) { printf(%d , C.data[i]); } printf(\n); return 0; }这份代码里有几个不容易注意到的细节find是线性查找它承担了“查重”的责任append里一定要检查容量否则越界写入会污染相邻内存这是栈缓冲区溢出最常见的来源之一unionSet里第一段循环直接拷贝 A因为 A 本身就是集合不会有重复元素。2.3 复杂度为什么这么高以及怎么优化这段代码跑下来A 里有 lenA 个元素B 里有 lenB 个元素。第一段循环拷 A 是 O(lenA)第二段循环里每次都在结果表上 find每次 find 最坏扫到结尾所以是 O(lenB × lenResult)。如果 A 和 B 大小接近 n那整体就是 O(n²)。数据规模上百还没感觉一旦上万肉眼可见地卡。工程上怎么优化最简单的方案如果元素取值范围固定且不大比如0~255直接开一个 bool 数组做标记查重变成 O(1)。更通用的方案是哈希表这也是为什么很多框架里union操作用HashSet而不是ArrayList。再有一种思路先对两个集合排序排序 O(nlogn)然后用双指针一趟合并总复杂度被压到 O(nlogn)既省空间又省时间。顺序表不是不能做集合运算而是要用对工具明白这层逻辑比背代码有意义得多。3. 单链表、循环链表、双链表三种变体的应用权衡链表看起来花样多其实就是三种基本变体来回组合单链表、循环链表主要是指循环单链表、双链表。很多人学到这里会懵为什么需要这么多种本质原因是它们各有各的“麻烦解决点”。3.1 三个结构放到一起对比特性单链表循环单链表双链表节点结构data nextdata nextprev data next尾节点指向NULL头节点/头结点NULL是否可以反向遍历否否是从尾部找前驱O(n)O(n)O(1)典型场景栈、队列、邻接表约瑟夫环、轮转调度LRU缓存、双向队列单链表是基础所有复杂变体都从它出发。循环单链表就是把尾节点的next指向头节点形成一个环。它的作用在于你从任意一个节点出发理论上都能找到所有节点不需要维护尾指针就能实现尾部插入 O(1)——因为尾节点就是头节点的前驱。双链表则多了一个prev指针指向直接前驱。它解决的最大痛点是“单向链表删除了当前节点却找不到前驱”。在单链表里你只能从头再找一遍前驱那是 O(n)双链表里直接p-prev就到手了。3.2 带头结点和不带头结点一个“哑元”能省多少事很多教材的图喜欢画“带头结点的链表”初学的人总疑惑这个空节点到底图什么我自己带实验课的时候发现不带头结点的链表写起来很容易绕晕。举个代码层面的例子。不带头结点的链表如果要在头部插入一个节点你得修改外部的头指针函数里必须用二级指针传参void insertAtHead(Node **head, int value) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-next *head; *head newNode; // 修改外部指针 }如果不小心写成head newNode那就“改了形参丢了实参”主调函数里原头指针纹丝不动后面还在拿旧头节点遍历直接死循环或者段错误。带头结点的链表没有这个问题头结点永远固定在第一个位置新节点插在头结点后面就行头指针不需要改变函数传一级指针就够了。提示头结点是哨兵节点不存数据不是“第一个数据节点”。别把带头节点的链表和不带头结点的链表搞混。判断链表是否为空带头结点写法是head-next NULL不带头结点写法是head NULL这是两个习惯体系。不带头结点并非一无是处。它的内存更紧凑、语义更简单Linux内核里的链表实现就不带头结点不过它用的是另一种侵入式设计后面第5章会讲到。换句话说面试里你能把带头结点带来的“头插法、删除第一个节点无需二级指针”这些好处说清楚比单纯背结论要强得多。3.3 循环单链表的经典舞台约瑟夫环和轮转调度约瑟夫环问题几乎是数据结构实验课的标配n 个人围成一圈从第 k 个人开始报数数到 m 的人出圈然后下一个人继续从1报数求最后的幸存者。这个问题用循环单链表实现非常自然——因为“围成一圈”本身就是循环链表的结构被淘汰节点就是链表中被删除的节点每次从1...m数数就是在环上移动 m 步。核心代码框架大概是// 假设 head 是指向循环链表中某个节点的指针节点结构是 data next Node *p head; while (p-next ! p) { // 只有一个节点时循环结束 Node *prev p; for (int i 1; i m; i) { prev p; p p-next; // 报数移动 } prev-next p-next; // p 出圈 printf(%d , p-data); free(p); p prev-next; // 从下一个人继续 }循环链表在这种场景里的优势非常直观你不用单独处理“到末尾回开头”的边界问题因为根本不存在末尾指针绕一圈自然回到起点。工程上类似的场景是操作系统的进程轮转调度时间片用完后进程回到队列末尾本质上就是一个循环链表在转。3.4 双链表的代价与收益别只记得它很好用双链表不是没有缺点。每个节点多一个prev指针64位系统下每个节点凭空多8字节100万元素的链表就等于多出来8MB内存。插入和删除的时候因为要同时维护prev和next代码里最少要改四个指针的指向写错了就出现“前后指针对不上”的脏数据。那么多花这些代价图什么图的是“找前驱O(1)”。最经典的应用是LRU缓存淘汰算法哈希表负责O(1)定位节点双向链表负责O(1)把最近访问的节点移到头部、把最久未使用的节点从尾部淘汰。这种“哈希双向链表”的组合几乎是面试必考而选双链表而不是单链表的原因很简单删除一个节点时需要知道它的前驱来重接链表双链表一步到位单链表还得把全链表再扫一遍。4. 手写单链表六大操作建立、插入、遍历、删除、清空、逆序这一节我完全是按实验课的标准来写的每一个操作都配代码和易错点。你把这六个操作都手写熟单链表这块基本就过关了。4.1 在指定位置插入核心不是“找到位置”而是“找到前驱”单链表的插入套路是固定的要在位置 i 插入节点必须找到位置 i-1 的那个节点也就是新节点的前驱。很多人第一次写总是想直接找到第 i 个节点然后发现插不进去因为单链表只认“前驱改 next”不知道谁是“前继”。// 在第 pos 个位置插入节点pos从0开始计数 void insertAt(Node **head, int pos, int value) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-next NULL; // 插入到头部 if (pos 0) { newNode-next *head; *head newNode; return; } // 找前驱 Node *prev *head; for (int i 0; i pos - 1 prev ! NULL; i) { prev prev-next; } if (prev NULL) { printf(插入位置越界\n); free(newNode); return; } newNode-next prev-next; prev-next newNode; }这里有个至关重要的细节newNode-next prev-next;和prev-next newNode;两条语句的顺序不能反过来。如果先把prev-next改成newNode那原来后面的节点就丢失了内存泄漏不说链表直接断成两截。我见过好多初学者顺序写反排了一晚上 bug 才找到问题。想想最快的方式验证先“挂住”后面的节点再让前面的节点指向新节点顺序不能乱。4.2 遍历和递归迭代写法背后藏着两个方向链表的遍历最简单一个while循环顺着 next 走void traverse(Node *head) { Node *cur head; while (cur ! NULL) { printf(%d , cur-data); cur cur-next; } }要注意别写成cur-next ! NULL作为循环条件那样会把最后一个节点漏掉。我见过不少新手这么改说“这样后代少访问一次空指针”结果输出里面少了一个元素。递归遍历的价值在于“逆序输出”可以不修改指针。比如要求从尾到头打印链表迭代方案得先逆置麻烦又费空间递归方案三行搞定void printReverse(Node *node) { if (node NULL) return; printReverse(node-next); printf(%d , node-data); }原理很简单递归先往深处走走到链表尾回溯的时候再打印。这样天然实现了逆序。但代价是递归深度等于链表长度链表特别长时可能导致函数调用栈溢出。所以这种写法适合小型链表和演示生产环境慎用。4.3 清空链表为什么必须先保存 next清空链表是实验课里报错最频繁的一个操作。新手最容易写成void clearWrong(Node *head) { while (head ! NULL) { free(head); // 先把 head 释放了 head head-next; // 再读 head-next —— 野指针访问 } }这段代码的问题非常隐蔽又非常致命free(head)之后head指向的内存已经被系统回收你再读head-next访问的是已释放内存这是典型的 use-after-free轻则读到随机数据重则直接崩溃。正确写法是先把下一个节点地址存下来再释放当前节点void clear(Node **head) { Node *cur *head; while (cur ! NULL) { Node *next cur-next; // 先救命把下一个节点保存好 free(cur); cur next; } *head NULL; // 最后把外部头指针置空 }清空函数接收二级指针也是关键点。如果只传一级指针Node* head函数内部把head置成 NULL 不会影响外部变量主调函数里的头指针仍然是野指针后续再访问就是悬空指针。我给个规则凡是可能修改链表头指针的函数头插、头删、清空都一律用二级指针。4.4 链表逆序三指针迭代与Python递归实现链表逆序是面试出勤率最高的题。迭代版本用三个指针逻辑一句话当前节点的next指向前一个节点然后三个指针整体后移。用C语言写Node* reverseList(Node *head) { Node *prev NULL; Node *cur head; while (cur ! NULL) { Node *next cur-next; // 1. 先保存下一个节点 cur-next prev; // 2. 转弯指向原前驱 prev cur; // 3. prev 前进 cur next; // 4. cur 前进 } return prev; // 遍历完prev 就是新头 }这里最容易错的一步还是顺序一定要先保存next再做“转弯”。如果你先改cur-next那原来的cur-next就丢了整个链表后半截迅速分崩离析。做这道题的时候建议在纸上画三个节点手动演一遍指针变化比死记代码管用得多。Python 里同样的问题可以用递归写代码更短class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverse_list(head: ListNode) - ListNode: if head is None or head.next is None: return head new_head reverse_list(head.next) head.next.next head head.next None return new_head递归的核心信念是“假设子链表已经逆好了”。比如链表1 - 2 - 3 - 4递归处理2 - 3 - 4得到4 - 3 - 2再把1接到2的后面就得到4 - 3 - 2 - 1。head.next.next head这行是递归版最精华的一行它让后一个节点反过来指向前一个节点。最后把head.next置空防止形成环。递归的代码短但隐藏的栈开销很大工程里同样不建议超长链表用递归面试除外——面试官真的爱看这种解法。5. 嵌入式场景下的链表没有malloc也能优雅管理内存聊完学生时代的链表再聊聊工程里的链表。嵌入式系统里的链表写法跟教科书差别不小值得单独拿出来说。5.1 为什么嵌入式系统普遍不用 malloc嵌入式环境对实时性和内存确定性要求极高。malloc的问题在于分配时间不确定首次分配可能需要找足够大的空闲块内存碎片不可控频繁分配释放后小碎片越来越多大块内存被切碎而且在没有操作系统或者MMU的环境下堆空间本身很小。很多嵌入式标准甚至直接禁用动态内存分配比如汽车电子里的 MISRA-C 规范就限制 malloc/free。那链表这种需要动态节点的结构怎么在嵌入式里用呢答案是用“内存池 侵入式链表”。5.2 内存池加侵入式链表一个简化版实现思路教科书通常把链表节点设计成struct Node { int data; struct Node *next; };这是“数据持有指针”的玩法——你要用链表就得让每个数据对象包一个指针。而侵入式链表反过来结构体里内嵌链表节点用户数据自己持有指针。Linux内核的list_head就是这么设计的嵌入式领域也大量沿用这种思想。// 侵入式链表节点 struct list_head { struct list_head *next; struct list_head *prev; }; // 用户自己的结构体里面内嵌一个 list_head struct timer_entry { int duration; int callback_id; struct list_head link; // link 就是用于串联的“钩子” };内存池的做法开机时提前分配一块数组作为节点池把空闲节点串成一个空闲链表。每次需要一个节点就从空闲链表头部取一个释放时还回空闲链表。整个过程没有malloc没有内存碎片分配耗时稳定在几个时钟周期内static struct timer_entry pool[64]; static struct list_head free_list;初始化阶段手动把pool[0]到pool[63]都加入空闲链表后面所有定时器操作只从池里取、往池里还。这样链表具备的动态性还在但又规避了动态内存分配的所有坑。5.3 典型应用事件队列、定时器链表、缓冲区管理拿定时器管理举例嵌入式系统里可能有几十个定时器每个都有不同的到期时间。常见的做法是把它们按到期时间排序挂在一个双向链表上中断来临时只需要检查头节点的定时器是否到期到期就执行回调并删除节点完全不需要扫描全部定时器。因为插入新定时器时需要找到合适的位置双链表的“找前驱O(1)”在这类场景里发挥关键作用。事件队列则常用环形缓冲本质是数组实现的队列或者循环单链表。比如串口接收中断产生一个事件往事件链表的尾部追加主循环从头取事件处理。这里循环链表的优势是头尾相连空闲节点和忙碌节点之间不存在“NULL边界”需要特判代码更简洁。嵌入式里编码的首要原则是“可预测”所以内存池侵入式链表这套组合在单片机、路由器、汽车ECU里都非常常见。搞明白这套思路你回头再读Linux内核源码里的list_head宏会觉得异常亲切。6. 面试题与实验课高频雷区逆置链表、释放内存、指针更新的顺序最后聊聊面试和实验课里的那些“经典坑”。这些坑我自己踩过也看过无数学生踩过总结出来给你避雷。6.1 逆置链表的边界条件空表、单节点、双节点逆置链表的代码看起来短但面试官最爱在边界条件上挖坑。你得保证这些情况全部正确处理空链表head NULL循环根本不进返回 NULL通过。单节点链表head-next NULL循环只执行一次返回原节点通过。双节点链表最容易测出你有没有忘记把新尾节点的next置为 NULL。逆置后原来头节点变成新尾节点它的next必须指向 NULL否则链表就有环。测试用例可以这么打// 单节点逆置 Node *head createNode(1); Node *newHead reverseList(head); // 期望 newHead head且 head-next NULL很多人的逆置实现依赖原链表最后一个节点已经是 NULL 这个事实所以反转过程中cur-next一旦指到后面就必须在最后把原头节点的next处理干净。这也是为什么我推荐写逆置时先在纸上画“两个相邻节点反转”的过程再抽象成代码可以少踩一半的坑。6.2 实验课错误排行榜段错误、死循环、长度没更新我统计过自己带过的实验课错误基本集中在三类。段错误最多的原因访问了 NULL 或已释放节点。比如“删除链表中第 pos 个节点”没有先判断pos是否越界或者删除最后一个节点后忘了把倒数第二个节点的next置 NULL后面遍历时又顺着野指针跑。死循环第二多循环条件写错典型的是把while (cur ! NULL)写成while (cur-next ! NULL)导致最后一个节点没处理或者修改指针后又回到原节点形成环。最隐蔽的环出现在单链表的逆置或循环链表的边界一旦某个节点的next被改成它自己无论你怎么遍历都会无限循环。第三类是“逻辑正确但结果全错”在一个带头结点的链表里忘记录有“头结点不算数据”打印的时候把哨兵数据也打出来或者插入删除后忘记更新length字段。顺序表也有这个问题length和capacity是老哥们念念不忘的两个变量length表示当前有效元素个数capacity表示能容纳的元素个数初学者特别容易混。6.3 工程开发里的选型Java的ArrayList和LinkedList别再被名字骗了贴一个非常经典的工程对比Java 的ArrayList就是动态数组顺序表LinkedList是双向链表。教科书给的结论是“链表插入快”于是很多人业务代码里随手就用LinkedList结果性能一测反而不如ArrayList为什么原因有三层。第一LinkedList的“插入快”指的是“找到位置后插入 O(1)”但如果你想按索引插入LinkedList需要先 O(n) 找到那个位置这跟数组一样慢。第二LinkedList每个节点是一个独立对象要新分配内存节点对象还有对象头开销100万个元素就多出几十MB内存遍历时缓存命中率极低。第三Java 的链表节点还会因为 GC 的引用追踪产生额外开销。所以工程上的常规选型标准是这样的需求推荐原因频繁按下标访问顺序表O(1) 随机访问缓存友好频繁在尾部追加顺序表摊还 O(1)扩容可控频繁在头部/尾部增删且节点数巨大链表两端插入 O(1)不需要搬移频繁按值查找都不行用哈希表频繁中部增删但规模不大顺序表更好链表找节点 O(n)数据量小时数组搬移反而更快我自己写代码时的习惯是先把顺序表作为默认选项除非明确需要“在保持头尾节点指针不变的情况下做大量动态拼接”否则不轻易上链表。很多自认为“链表性能好”的代码一 profile 就发现瓶颈根本不在插入而在遍历和缓存。结尾就不多写了最后留一句实操建议。这六个操作最好自己敲一遍再删掉然后不看任何参考代码重新写出来。链表这东西光看永远会一写就废。写熟了之后你对指针、内存释放、边界条件这些基本功都会有质的提升后面的二叉树、图、跳表学起来会顺很多。