线性结构这节内容我讲了不下十遍每次讲完都发现还有人把链表是线性结构当成一件需要惊讶的事。数组、链表、栈、队列看起来完全不像一家人凭什么被归到同一个章节其实答案很直接它们在逻辑关系上是同一种东西——元素之间都是一对一的相邻关系区别只在于用连续内存承载还是用指针串起来以及插入删除被限制在哪一端。这一节叫3.1 线性结构是所有数据结构的地基。树、图、查找、排序那些让人头疼的东西最后都会退化成线性问题来处理。如果你刚学到这或者学完一遍想补底层认知这篇值得慢慢看。1. 先搞懂线性到底在说什么1.1 逻辑上的线性一对一的相邻关系数据结构的核心不是存储本身而是元素之间的关系。线性结构描述的是一种非常严格的关系在一个数据集合里除了第一个元素和最后一个元素其他每个元素都有且仅有一个直接前驱有且仅有一个直接后继。第一个元素没有前驱最后一个元素没有后继。这个定义看起来简单但它正是线性二字的全部含义。生活里的例子到处都是。火车站排队买票的队伍你前面有且只有一个人后面有且只有一个人电影院座位排成一列第3排5号的左边是3排4号右边是3排6号。队伍可以变长变短座位可以被占用或空着但谁和谁相邻这种关系始终稳定存在这就是逻辑结构。计算机学科里为什么要先区分逻辑结构和物理存储因为它们是两件事。逻辑上的线性只回答谁在谁旁边的问题并不规定元素在内存里必须挨着放。排队的人可以手拉手站在同一块空地上也可以用一根绳子串起来人跟人隔三米远——逻辑上依然是你前面是谁、你后面是谁。把这个分离想明白后面数组和链表的对比才不会拧巴。1.2 线性结构的典型成员表、栈、队列、串线性结构家族里有四个最常见的成员考试、面试、工程里翻来覆去就是它们。线性表是最一般的形态。它对外提供任意位置的插入、删除按序号访问按值查找就像一个完全开放的长队谁想站哪就站哪想走就走。这是线性结构的基础模型。栈是限制版的线性表所有插入和删除都只允许在表尾栈顶进行。先进后出像一摞盘子后放上去的先端走。队列也是限制版只能在一端插入队尾、另一端删除队头。先进先出像奶茶店的取餐口先下单的先拿走。串可以看作线性表的特例只不过元素被限定为字符。串本身有专门的高效算法比如子串匹配的KMP但它的底层存储和增删改查依然是线性结构那一套逻辑。这四个成员不是四种完全不同的东西而是同一套一对一相邻关系在不同约束下的变体。把栈理解为不让在中间插队的线性表把队列理解为只能在两边操作的线性表你学的时候就不会觉得是在学新东西了。1.3 常见误区线性不等于连续存储这个误区几乎每个新手都会踩一遍看到线性结构四个字就觉得内存里必然是连续的一段于是完全无法理解链表为什么也叫线性结构。前文已经说了线性是逻辑层面的概念连续存储只是顺序存储带来的结果。链表里每个节点可能散落在内存任意角落节点之间靠指针维持前后关系从逻辑上看它仍然是严格的一对一结构所以它是线性结构。反过来树、图这些结构中一个节点可能有多个子节点或者多个相邻节点逻辑上不是线性那才是真正的非线性结构。我见过有人面试被问数组和链表的区别回答一个是连续的一个是不连续的。没错但只答到了物理层面。更高一层的回答是两者都能表示线性表数组用连续地址实现随机访问链表用指针实现离散存储因此数组适合读多写少的场景链表适合频繁插入删除但不擅长随机访问的场景。能说出这一层才算真的懂线性结构。2. 顺序存储和链式存储到底该怎么选2.1 顺序存储为什么随机访问能做到O(1)顺序存储就是把线性表中的元素在内存里按先后顺序排列一个挨一个中间不留空位。数组是它最直接的表现形式。随机访问O(1)不是魔法是地址计算的结果。假设数组基地址是base每个元素占size字节那么第i个元素从0开始的地址就是 base i * size。一次乘法和一次加法就定位完成CPU拿着算出来的地址直接访问内存不需要任何遍历。所以哪怕数组里有几百万个元素你访问第一个和访问最后一个耗时几乎一样。但顺序存储的代价也出在这里——插入和删除。想在数组位置k插入一个元素那么从k开始后面所有元素都得往后挪一位。最坏情况是插到头部整个数组的所有元素都要移动时间复杂度O(n)。删除同理平均要移动约n/2个元素。这个挪数据的成本数据量小的时候无所谓一旦上百万量级一次头部插入可能就是灾难级延迟。还有一点很多人会忽略顺序表需要一段连续空间而且这个空间要么一开始就给足可能浪费要么满了以后再扩容需要重新分配内存并拷贝旧数据。扩容的坑我下一章专门讲。2.2 链式存储用空间和跳转换取灵活链式存储的核心是节点和指针。每个数据元素被包成一个节点节点里除了存储数据还要存一个或者两个指针指向逻辑上的前驱或后继。节点散落在内存各处通过指针串成一条链。链表的插入和删除不需要搬动任何数据。删除一个已知位置的节点只需要让前一个节点的next绕过它直接指向它的下一个然后把它释放掉插入也只需要修改两次指针。这个操作的时间复杂度是O(1)前提是你已经知道目标位置在哪里。但是链表的代价非常现实。第一多出来的指针字段是额外内存一个8字节的next指针在百万级节点的链表里就是几MB的开销。第二它不支持随机访问想取第k个节点只能从头开始走时间复杂度O(n)。第三也是现代CPU体系下最致命的问题链表节点内存离散每次访问下一个节点大概率会发生缓存未命中需要从主存加载数据速度比顺序访问慢一个数量级。这也是为什么很多高性能场景宁可选择顺序表也不选理论上复杂度更优雅的链表。2.3 选型经验拿数据和场景说话到底用顺序存储还是链式存储我自己的选型心法非常朴素先看访问模式再看操作位置最后看数据量级。先给一个结论现代工程里顺序存储的统治力比很多人想象要大得多。原因就是缓存局部性。数组在遍历时是顺序访问CPU的高速缓存会预取整段内存跑起来非常快。链表每次跳到一个随机地址缓存基本帮不上忙纯靠主存和指针跳转性能差距肉眼可见。真正适合链表的地方其实很有限。第一类你需要频繁在容器中间插入和删除而且位置不是靠遍历确定的比如实现LRU缓存时需要在已知节点处前后调整。第二类数据长度不确定、变化频繁而且操作主要集中在一端或者两端比如消息队列的队尾追加、队头弹出。第三类每个节点本身是很大的对象你不希望搬迁数据更愿意用指针管理链表的优势才真正显现。我的建议是做项目别一上来就写复杂链表。先用数组和动态数组实现遇到性能瓶颈再考虑换形态。大多数情况下你根本不会遇到那个瓶颈。3. 手写核心结构从顺序表到单链表3.1 顺序表的核心操作动态扩容、插入、删除顺序表的动态扩容是第一个坑。很多初学者用固定数组实现顺序表满了就报错逻辑倒是简单实用性太差。真正的动态数组应该在容量不足时自动扩容。扩容有两条原则。第一别一次只加一个位置。假如表长n每次插入都重新分配内存并拷贝旧数据那n次插入的总拷贝量是123...n整体是O(n^2)时间全耗在拷贝上。第二按倍数扩容常见是1.5倍到2倍。为什么倍数扩容能做到均摊O(1)可以把扩容想象成记账每次插入时除了本次写入的数据再预付一点未来扩容的搬迁成本。假设容量翻倍总共插入n个元素搬迁的总次数是O(n)翻倍行为的次数是O(log n)两者相加还是O(n)。均摊到每次插入就是O(1)。这就是动态数组在理论上的底气。参考一个简化的C语言扩容逻辑typedef struct { int *data; int size; // 当前元素个数 int capacity; // 已分配容量 } SeqList; void ensure_capacity(SeqList *l, int need) { if (l-size need l-capacity) return; int new_capacity (l-capacity 0) ? 4 : l-capacity * 2; int *new_data (int *)malloc(sizeof(int) * new_capacity); if (new_data NULL) { // 处理分配失败但不要直接free(l-data)原数据还有用 return; } for (int i 0; i l-size; i) new_data[i] l-data[i]; free(l-data); l-data new_data; l-capacity new_capacity; }这里有个很隐蔽的细节如果初始capacity为0直接写 capacity * 2结果还是0所以必须给个初始容量比如4或者16。生产环境拷贝数据建议用memmove而不是手写循环性能和可读性都更好。另外malloc失败时要保持原数据完好先申请成功再释放旧内存别反过来。插入的核心逻辑是先扩容再把位置k及其后面的元素全部后移一位。后移必须从后往前做否则前面的元素会把后面还没移动的数据覆盖掉。删除则反过来从前往后覆盖。平均移动n/2个元素这是顺序表逃不掉的时间成本。3.2 单链表的插入与删除眼睛盯着指针链表插入删除的全部精髓都在指针操作上。画图永远是第一位的每个节点画两个格子一个存data一个存next搞清楚了再写代码。在节点p后面插入新节点node只要两行node-next p-next; p-next node;这两行顺序绝对不能反。如果先写 p-next nodep原来的后继就丢了node后面到底是谁也变得诡异链表从这里断开。我总结成一句话先把新节点连向后继再把前驱指向新节点。后顾之忧先解决再动前驱。删除节点q的时候假设已经知道q的前驱pp-next q-next; free(q);先让前驱绕过q再释放节点。关键点在于如果只知道q本身、不知道前驱单链表是做不到O(1)删除的必须从头遍历找q的前驱。除非用那个偷天换日的技巧把q的data替换成q-next的data然后删除q的next。这个技巧面试偶尔会考但工程里别乱用语义太隐晦了。头节点是单链表里最实用的设计。它是链表的第一号哨兵节点自己不存实际数据next指向真正的第一个数据节点。好处是空表和非空表的插入删除逻辑完全统一不再需要一大堆if判断删除第一个数据节点时head始终能充当它的前驱。很多人第一次写链表不带头节点写到最后边界条件多到怀疑人生加一个哨兵立刻神清气爽。3.3 栈和队列用数组也能写出专业味道栈的两种实现都有价值。顺序栈最直白一个数组加一个top下标。入栈是 data[top] value出栈是 value data[top--]。两个边界必须处理好栈空时出栈要报错栈满时如果是定长数组要拒绝入栈或者触发扩容。队列用数组实现时有一个经典陷阱叫假溢出。假设数组长度是N队尾rear不断右移队头front也不断右移明明数组前段空出一大截rear却已经到末尾了再插入就报错。解决办法是循环队列让rear和front在逻辑上绕回成环// 入队 if ((rear 1) % N front) { /* 队满 */ } data[rear] value; rear (rear 1) % N; // 出队 if (rear front) { /* 队空 */ } value data[front]; front (front 1) % N;最让新手困惑的是队空和队满在物理下标上都表现为 front rear所以必须牺牲一个存储单元让队满条件变成 (rear 1) % N front也就是说长度为N的循环队列最多装N-1个元素。如果不肯牺牲这个位置就加一个size字段记录当前元素个数。我的建议是自己写的轮子大可以直接加size字段直观又省心不用抠那个少一格的边界。别人的代码如果只用一个变量判断队空队满八成是牺牲了一格读代码时注意一下就好。4. 线性结构在真实系统里无处不在4.1 函数调用栈每个程序员都身处其中的栈栈不是课本里的抽象玩具它就在每个进程的运行现场里。每次函数调用系统会往调用栈里压入一个栈帧栈帧里装着返回地址、局部变量、寄存器现场。函数返回时再弹出这个栈帧。程序嵌套调用多少层这个栈就叠加多少层。递归为什么会栈溢出本质上就是连续压栈而不弹出直到系统栈空间耗尽。工程里的解决思路通常有两种一是把递归改成显式栈循环自己用堆内存模拟系统栈完全掌握入栈出栈的节奏二是看能不能用尾递归把递归改写成迭代。这两条路本质都是在控制栈的深度。理解调用栈还有一个实际用途调试时看到的调用栈列表就是从当前函数一路回溯到入口的路径栈帧一个叠一个这本身就是线性结构在你眼前的一次完整展示。遇到栈溢出报错别慌顺着调用栈找递归或深层嵌套的元凶。4.2 队列从消息队列到环形缓冲队列最常见的价值是解耦。你在代码里往队列发消息消费者从另一端取消息生产者和消费者的处理速度不需要完全一致多出来的数据先排队等着。先进先出的线性结构天然适合这种场景它把不同节奏的两个系统隔开谁都不会因为对方的抖动而卡死。操作系统里的环形缓冲区也是队列。网卡收到的数据包先写进Ring Buffer协议栈再从里面取出来处理。这里为什么用环而不是普通数组因为缓冲区大小固定数据是流式不断的队头位置和处理位置都在移动环形结构可以让front和rear在数组末尾平滑地绕回避免每次都搬移数据。我自己写日志系统的时候也用过环形队列日志线程往里写消费线程往外读队列满了就丢弃最旧的一条或者阻塞。这种需求一个几百行的环形队列比任何花哨的数据结构都管用。4.3 双向链表、循环链表从编辑器撤销到LRU缓存编辑器的撤销和重做是一个教科书级的双栈问题每次操作压入undo栈撤销时把操作从undo弹出、压入redo栈。但如果你想要在历史记录里自由前进后退双向链表更合适。每个节点有pre和next可以向两个方向移动就像浏览器的前进后退按钮点一下往前走点一下往后走指针就是你的定位器。再看LRU缓存。LRU要求最近最少使用的数据被淘汰最经典的设计是哈希表加双向链表。哈希表保证按key查找O(1)双向链表保证命中节点移动到头部O(1)、尾部节点淘汰O(1)。这里为什么必须是双向链表因为在删除一个节点时单链表O(1)删除的前提是已知前驱节点而哈希表只记录节点指针本身拿不到前驱。双向链表让节点自带pre指针删除时直接取用巧妙避开了单链表的短板。操作系统的内存管理里也有链表。空闲内存块通过一个双向链表串起来分配时找合适的块回收时把相邻的空闲块合并。链表的节点增删频繁发生在任意位置而且数据量不大链式存储在这里比数组更适合。循环链表同样值得一提。约瑟夫问题用循环链表描述非常自然一群人围成一圈数到m的人出局从下一位继续数。循环链表天然支持绕回比在数组里做下标取模直观得多。虽然面试不一定要求你手写但这个例子能帮你理解环这种特殊线性结构。5. 踩坑实录线性结构最常见的几个翻车现场5.1 删链表节点把整个链删断了错误写法长这样想遍历删除某个节点代码里直接写 q q-next然后 free(q)。问题在于你已经把q改成了下一个节点再freefree掉的是下一个节点下一个节点还没被遍历到就没了整条链表当场断裂。如果再往后走还会访问已经释放的内存轻则数据错乱重则段错误。正确顺序永远是先保存q的next指针再把前驱的next指向它最后free。我之前调试过一段删除所有值为x的节点的代码一直报段错误最后定位到的问题不是删除逻辑本身而是循环体内对q的更新时机不对。排查这类问题的土办法是把每个节点的地址打印出来比对每一步之后next指向哪里看是谁把链引向了非法位置。5.2 循环队列判满判空永远差一个格新手写循环队列最容易在队满判断上翻车。如果写成 front rear 就认为队满队列空的时候也是这个条件入队和出队全乱套。解决办法前面已经给了要么牺牲一个存储单元要么加size字段。我个人强烈建议在自研代码里加size字段不要为了省那4个字节去扣少一格的逻辑否则看代码的人会被绕晕你自己过两个月再看也晕。另一个和循环队列相关的小坑是rear的推进方式。建议统一用 (rear 1) % N不要用先加1再if判断是否越界的写法后者容易漏掉边界。如果N是2的幂可以用 (rear 1) (N - 1) 代替取模性能略好不是2的幂就老实写%也不会慢到哪去。5.3 动态数组扩容的隐藏成本与内存失控扩容翻倍后均摊复杂度是O(1)但表面完美的背后有两个隐藏成本。第一搬迁数据时要一次性拷贝整个旧数组几百MB的数组一次扩容可能卡顿几十毫秒。高频路径里这种突刺不可接受所以才有了分块扩容、分段复制等思路。第二翻倍扩容很容易导致空间浪费当容量从1M涨到2M再到4M实际利用可能只有一半多一点这是典型的以空间换时间。应对方案也直接如果能预估最大容量初始化时直接分配到位后续永不扩容性能最稳但可能浪费内存无法预估就设置一个容量上限超过后拒绝写入或者换分块策略高性能场景下可以考虑内存池或者arena分配器减少频繁realloc带来的碎片问题。5.4 通用排查思路画状态图不靠猜线性结构的bug绝大多数是状态没画对。我的固定排查流程是三步先画出逻辑结构图把每个节点在逻辑上的前后关系标出来再画物理存储图标出数组的下标、front和rear的位置最后把每一行关键操作对应的状态变化写下来哪里与预期对不上bug就在哪里。这个方法对付链表问题尤其好用。有一次我排查一个双向链表插入的段错误画完图发现是插入尾节点时新节点的pre和原尾节点的next互相赋值顺序不对导致原尾节点的pre指向了错误位置。这要是靠打印日志硬猜可能几个小时都定位不到画图之后一分钟内就发现了。从教这门课到现在我最大的体会是线性结构不只是一章课程内容而是一种思维习惯。面试题里常考的反转链表判断回文链表LRU缓存全部是线性结构的变形工程里随手写的数组、队列、调用栈到处都是线性结构的影子。真正想明白它不是背住了数组和链表的区别而是形成一种先看关系、再选存储、最后算成本的思维框架。学完这一节我建议你别急着背概念自己动手写一个顺序表、一个单链表、一个循环队列跑通所有插入删除和边界情况。真踩过几次坑之后这些知识就长在身上了面试和写代码时自然会用出来。