线性表核心解析：顺序表与链表的设计取舍、操作细节与边界处理

数据结构这门课我前前后后翻过不下五遍每次重看线性表都有新体会。第一遍学的时候觉得顺序表和链表不就是数组和指针嘛能有多难第二遍做题才发现真正卡人的从来不是怎么存而是什么时候该用哪种存法、边界条件怎么处理、时间复杂度怎么算才不心虚。这篇笔记对应的是王道数据结构课程的第二部分核心落在线性表上——顺序表、单链表、双链表、循环链表、静态链表这几块。它解决的是数据元素之间一对一关系如何组织这个最基础也最容易被轻视的问题适合正在准备专业课考试的同学也适合工作几年后想回头把底层结构重新捋一遍的开发者。下面我按自己实际学习和做题的顺序来展开重点讲清楚每种结构的设计动机、操作细节和那些文档里不会明说但考试和实战都会踩的坑。1. 线性表到底在解决什么问题1.1 从一对一这个约束说起线性表是数据结构里最朴素的一种逻辑结构定义很干脆n 个相同类型数据元素的有限序列。关键词是有限和序列——有限意味着长度确定序列意味着除了第一个和最后一个每个元素都有且仅有一个前驱和一个后继。这个一对一的约束看起来简单但它直接决定了后面所有操作的边界插入只能在某个位置前后挪动删除必须补上空位查找只能顺着关系走。很多人学的时候会跳过这段定义直接看代码结果做题时对位序和数组下标混着用插入位置写错、删除越界这类错误反复出现。我自己的经验是先把逻辑结构线性表和存储结构顺序存储、链式存储这两层彻底分开后面就不会乱。逻辑结构讲的是元素之间的关系存储结构讲的是这种关系在内存里怎么落地。同一个线性表可以用连续的内存块存顺序表也可以用散落的节点加指针串起来链表逻辑上它们是等价的但操作代价完全不同。这里有个容易被忽略的点线性表要求元素类型相同。这不是随便定的类型相同意味着每个元素占用的空间一致顺序存储时才能用首地址 下标 × 元素大小直接算出任意元素的地址实现 O(1) 的随机访问。如果元素大小不一这个公式就失效了顺序存储的优势也就没了。理解这一层你才能明白为什么后面讲链表时节点里除了数据域还要专门留一个指针域——那是用额外空间换取灵活性的代价。1.2 顺序存储与链式存储的本质取舍顺序表和链表的对比几乎所有教材都会列一张表但表格背后的为什么才是关键。顺序表用一段连续空间存元素逻辑相邻的元素物理上也相邻好处是随机访问快、存储密度高不用额外存指针坏处是插入删除要移动大量元素、容量固定不易扩展。链表用节点加指针逻辑相邻物理上不一定相邻好处是插入删除只改指针、容量按需分配坏处是不能随机访问、每个节点都要额外空间存指针。我习惯用一个类比来记顺序表像电影院里连号的座位你想找第 5 排第 3 座直接走过去就行但如果中间要加一个人后面所有人都得往后挪链表像一列手拉手的人你想找第 5 个人必须从第 1 个开始一个个数过去但要在某两个人之间插一个新人只要让前后两个人改牵谁的手就行其他人不受影响。这个取舍直接决定了选型查多改少用顺序表改多查少用链表。但实际做题时还有更细的判断比如经常在表尾插入这种场景顺序表其实也不慢只要不扩容而链表如果只维护头指针每次尾插都要遍历到末尾反而退化成 O(n)。所以真正做题时要看操作集中在哪个位置不能一概而论。下面这张表是我做题时总结的对照比教材那张更贴近实际判断操作场景顺序表代价链表代价我的选型倾向按位置随机读取O(1)O(n)顺序表表头插入/删除O(n)O(1)链表表尾插入O(1)不扩容O(n)仅头指针顺序表按值查找O(n)O(n)看是否需要频繁改动频繁扩容需整体搬迁按需分配链表1.3 学习顺序为什么是先顺序表后链表王道课程的编排是先讲顺序表再讲链表这个顺序不是随意的。顺序表的实现直接对应数组大家对数组最熟悉理解下标访问连续存储几乎没有门槛可以先把线性表的抽象操作初始化、插入、删除、查找的语义搞清楚。等这些操作的语义在心里扎根了再引入链表你关注的焦点就自然从这个操作是什么意思转移到这个操作在链式存储下怎么实现认知负担被拆开了。我第一遍学的时候没意识到这一点顺序表草草看过就直奔链表结果链表插入时指针怎么改总是画错图。后来回头把顺序表的插入删除老老实实手写了一遍把第 i 个位置和下标 i-1的关系彻底理清再看链表才发现两者在边界处理上的思路是一致的——都是先判断位置合法性再定位再改动。所以如果你现在正卡在链表不妨先回去把顺序表的手写代码默一遍很多困惑会自己消解。2. 顺序表连续内存带来的快与痛2.1 用数组模拟顺序表时那几个必须想清楚的设计点顺序表的实现本质是用数组加一个长度变量。听起来简单但真正动手写之前有几个设计决策必须先定下来否则代码写到一半会反复返工。第一个决策是容量怎么表示。常见做法是定义一个最大容量常量MaxSize数组开这么大再用一个length记录当前实际元素个数。这里要区分数组容量和表长两个概念容量是数组能装多少表长是当前装了多少。很多初学者直接用表长当循环边界去访问数组一旦表长等于容量再插入就越界了。我习惯在插入前先判断length MaxSize满了就拒绝或扩容这个判断不能省。第二个决策是位序从 1 开始还是从 0 开始。教材和考试里说的第 i 个元素通常指位序从 1 开始而数组下标从 0 开始。这两者差 1是所有边界错误的根源。我的做法是对外接口一律用位序符合人的直觉和题目描述进入函数第一件事就是把它转成下标之后内部全用下标不再混用。这样至少能保证错误只可能出现在转换那一行排查范围小。第三个决策是插入和删除时元素怎么移动。插入要把第 i 个位置及之后的元素整体后移一位删除要把第 i 个位置之后的元素整体前移一位。移动方向很关键插入必须从后往前移否则前面的元素会覆盖后面的删除必须从前往后移否则后面的元素会覆盖前面的。这个方向我当年死记硬背过后来想明白了——移动的本质是把空位腾出来或把空位填上顺着空位移动的方向就不会错。// 顺序表插入在第 i 个位置位序从1开始插入元素 e bool ListInsert(SqList *L, int i, int e) { if (i 1 || i L-length 1) return false; // 位置合法性 if (L-length MaxSize) return false; // 容量检查 for (int j L-length; j i; j--) { // 从后往前移 L-data[j] L-data[j - 1]; } L-data[i - 1] e; // 位序转下标 L-length; return true; }上面这段代码里i L-length 1这个上界容易被写成i L-length差别在于能不能在表尾之后追加。位序length 1表示插在最后一个元素后面是合法的所以上界必须是length 1。这个细节考试特别爱考选择题里经常拿它做干扰项。2.2 插入删除的平均移动次数是怎么算出来的顺序表插入删除的时间复杂度是 O(n)但平均移动多少次这个结论很多人只记结果不会推。推导其实不难理解了之后对复杂度分析会有质的提升。假设表长为 n插入位置 i 可以取 1 到 n1 共 n1 种可能。在第 i 个位置插入时需要移动的元素个数是 n - i 1从第 i 个到第 n 个都要后移。假设每个位置插入的概率相等都是 1/(n1)那么平均移动次数就是$$\frac{1}{n1}\sum_{i1}^{n1}(n-i1) \frac{1}{n1}\cdot\frac{n(n1)}{2} \frac{n}{2}$$也就是说平均要移动一半的元素。删除同理表长 n删除位置 i 取 1 到 n移动 n - i 个元素平均移动 (n-1)/2 个。这两个结论要能自己推出来而不是背平均 n/2。我踩过一个坑有次做题问在长度为 n 的顺序表中删除第 i 个元素需要移动多少个元素我条件反射写了 n-i1结果错了。正确是 n-i因为删除第 i 个之后第 i1 到第 n 个前移一共 n-i 个。插入是 n-i1删除是 n-i差的就是被操作的那个元素本身。这个区别我在草稿纸上画了个小例子才彻底记住表 [a,b,c]删除第 2 个 b只需把 c 前移一位移动 1 个n-i 3-2 1对上了。2.3 顺序表实操中最容易翻车的三个边界第一个边界是空表删除。表长为 0 时任何删除都非法判断条件i 1 || i L-length里i 0在 length 为 0 时恒成立能正确拦截。但如果只写i 1忘了上界空表删除就会访问非法内存。第二个边界是表满插入。容量检查必须在移动元素之前做如果先移动再检查容量一旦满了数组已经越界写坏了。这个顺序不能反。第三个边界是位序与下标的转换点。我见过不少代码在循环里一会儿用data[i]一会儿用data[i-1]自己都绕晕了。统一原则函数入口转换一次内部只用下标。比如删除操作bool ListDelete(SqList *L, int i, int *e) { if (i 1 || i L-length) return false; *e L-data[i - 1]; // 取出被删元素 for (int j i; j L-length; j) { // 从前往后移 L-data[j - 1] L-data[j]; } L-length--; return true; }注意删除的循环从j i开始i 是位序对应下标 i-1 的后一个到j L-length结束把data[j]往前挪到data[j-1]。这个循环边界我建议每次写之前先在纸上画三个元素的例子跑一遍比死记靠谱。提示顺序表的所有边界错误本质都是位序、下标、长度三者的换算没统一。养成入口转换、内部统一的习惯能消掉一大半低级错误。3. 单链表指针操作的分水岭3.1 带头结点还是不带头结点这个选择影响所有代码单链表第一个绕不开的决策就是带不带头结点。头结点是放在第一个实际元素之前的一个额外节点它的数据域通常不存有效数据可以存表长等信息指针域指向第一个实际元素。带不带头结点直接决定了插入删除代码要不要特判在第一个位置操作。不带头结点时如果在第一个位置插入或删除第一个元素必须修改头指针本身而头指针是函数的入参C 语言里要改它就得传二级指针或者返回新头指针代码里到处是if (i 1)的特判。带头结点后第一个位置的操作和其他位置完全一样因为头指针永远指向头结点不变变的只是头结点的指针域。这就是头结点的核心价值——把边界情况变成普通情况让代码统一。我一开始觉得头结点是多余的空间浪费后来写了几遍不带头结点的插入删除被那些特判折磨得够呛才彻底转向带头结点。考试里两种都可能考但实际写代码我强烈建议带头结点。下面是不带头结点插入第一个位置的典型写法你能感受到那种别扭// 不带头结点在第1个位置插入需要改头指针 bool InsertFirst(LNode **head, int e) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data e; s-next *head; // 新节点指向原第一个 *head s; // 头指针改指向新节点 return true; }而带头结点后这段逻辑被吸收进通用的在第 i 个位置插入里不需要单独的函数。这个统一性在链表代码量大的时候价值巨大。3.2 指针改动的顺序为什么必须先连后断单链表插入的核心操作是改指针而指针改动顺序错了会导致链断裂或内存泄漏。以在节点 p 之后插入新节点 s 为例正确顺序是s-next p-next;新节点先指向 p 原来的后继p-next s;再让 p 指向新节点如果反过来先执行p-next s那么 p 原来的后继就丢了s 的 next 还没设置整条链从 s 往后就断了。这个先连后断的原则本质是在断开旧连接之前先把新连接建立好保证任何时刻都不会有节点失去引用。删除也是同理。要删除 p 的后继节点 q正确顺序是p-next q-next;让 p 跳过 qfree(q);再释放 q如果先 free(q) 再改 p-next那 p-next 就成了悬空指针访问它行为未定义。这个顺序错误在考试的手写代码题里扣分很狠因为它是逻辑对但实现错的典型。我记这个顺序的口诀是先接后断先断后放——插入先接新链再断旧链删除先断引用再释放内存。口诀不优雅但管用尤其是考试紧张的时候。3.3 头插法与尾插法建表一个细节决定元素顺序建立单链表有两种常见方式头插法和尾插法。头插法是每次把新节点插在头结点之后尾插法是每次插在链表末尾。两者的代码差别很小但建出来的链表元素顺序完全相反。头插法建表如果按 1、2、3 的顺序插入最终链表是 3、2、1因为每次新节点都跑到最前面。尾插法按 1、2、3 插入链表就是 1、2、3。这个差异在做链表逆置类题目时特别有用——头插法天然就是一个逆序工具。尾插法的关键是要维护一个尾指针r每次插入后更新r指向新的末尾。如果不维护尾指针每次尾插都要从头遍历到末尾建一个长度为 n 的链表就退化成 O(n²)。这个优化点很多人第一次写尾插法时会忽略// 尾插法建表维护尾指针 r void CreateListTail(LNode *head, int arr[], int n) { LNode *r head; // r 始终指向当前末尾 for (int i 0; i n; i) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data arr[i]; r-next s; // 接到末尾 r s; // 更新尾指针 } r-next NULL; // 末尾置空别忘 }最后那句r-next NULL是必须的否则链表末尾的 next 是野指针遍历时会越界。这个收尾动作我在第一次手写时漏过调试了半天才发现遍历停不下来。3.4 按位查找与按值查找遍历的两种终止条件单链表查找分两种按位查找找第 i 个节点和按值查找找第一个值为 e 的节点。两者都是从头遍历但终止条件和返回值不同容易混。按位查找的终止条件是走到第 i 个或走到 NULL。如果 i 超过表长遍历会走到 NULL此时应返回失败。代码里循环条件通常是while (p ! NULL j i)j 从 0 开始头结点算第 0 个走完 j i 时 p 就是第 i 个节点。按值查找的终止条件是找到值相等或走到 NULL。找到就返回节点指针走完没找到返回 NULL。这里有个性能细节单链表按位查找第 i 个节点是 O(n)因为必须从头数。这也是为什么链表不适合频繁按位置访问的场景。而如果题目要求找倒数第 k 个节点正统做法是用两个指针一个先走 k 步然后两个一起走前面的到末尾时后面的正好在倒数第 k 个。这个双指针技巧是链表题的常客本质是用两个指针的相对距离代替了先求总长再算位置的两次遍历。4. 双链表与循环链表把单向关系补全4.1 双链表多出来的 prior 指针解决了什么单链表只能单向遍历想找某个节点的前驱必须从头再走一遍代价 O(n)。双链表在每个节点里加一个prior指针指向前驱把找前驱从 O(n) 降到 O(1)。这个改动的代价是每个节点多一个指针的空间以及插入删除时要多维护一组指针。双链表插入的关键是四步指针改动顺序不能乱。以在节点 p 之后插入 s 为例s-next p-next;s-prior p;p-next-prior s;如果 p 有后继p-next s;第 3 步有个陷阱如果 p 是最后一个节点p-next是 NULL直接访问p-next-prior会崩溃。所以必须先判断p-next ! NULL。这个空指针判断是双链表代码里最常见的漏写点我当年考试就栽在这。删除节点 qq 是 p 的后继时要改两处p-next q-next;和q-next-prior p;同样要判断q-next是否为空。双链表的代码量比单链表多但逻辑更对称写熟了反而不容易错因为前后两个方向都要维护少改一个立刻能通过遍历发现。4.2 循环链表把末尾这个概念消掉循环链表是把单链表的尾节点 next 指回头结点或第一个节点形成一个环。这样做的好处是从任意节点出发都能遍历整个链表不存在走到末尾就停的问题。判断遍历结束的条件从p ! NULL变成p ! head或p-next ! head看具体实现。循环链表最实用的场景是频繁在表头表尾操作。普通单链表如果只维护头指针尾插要 O(n)循环链表如果维护的是尾指针rear那么rear-next就是头结点头插和尾插都能 O(1) 完成。这个技巧在实现队列时特别常用——用循环链表加尾指针实现队列入队出队都是 O(1)。判断循环链表遍历结束有个经典坑如果循环条件是p ! NULL那永远停不下来因为环里没有 NULL。必须用p ! head或者计数到表长。我见过有人调试循环链表时程序卡死就是因为沿用了单链表的while (p ! NULL)。4.3 静态链表没有指针时怎么模拟链式结构静态链表是用数组模拟链表。数组的每个元素是一个节点节点里存数据和下一个节点的数组下标叫游标或 next 域用下标代替指针。它存在的意义是在一些不支持指针的编程环境里仍然能实现链式存储的灵活性。静态链表的关键是区分数组下标和链表顺序。数组里元素的物理顺序和逻辑顺序无关逻辑顺序靠 next 域串起来。比如数组第 0 个元素存的是逻辑上第 3 个节点完全正常。初始化时通常把 next 域串成一个空闲链表插入时从空闲链表取一个节点删除时把节点还回空闲链表。静态链表的插入删除和单链表逻辑一致只是把p p-next换成p next[p]把malloc换成从空闲链表取。考试里静态链表考得不多但偶尔出选择题问静态链表的 next 域存的是什么答案是数组下标而不是地址这个要记清。结构类型找前驱找后继随机访问典型适用场景顺序表O(1)下标-1O(1)O(1)查多改少单链表O(n)O(1)O(n)频繁插入删除双链表O(1)O(1)O(n)需要双向遍历循环链表O(n)O(1)O(n)环形队列、轮转调度静态链表O(n)O(1)O(n)无指针环境5. 做题时真正拉开差距的几个思维习惯5.1 画图永远比空想快链表题不画图等于闭着眼睛改指针。我养成的习惯是拿到任何链表题先在纸上画三到五个节点标上头结点、数据域、next 箭头然后每改一次指针就在图上划掉旧箭头画新箭头。这个动作看起来慢实际上能省掉大量调试时间。画图还有个隐藏好处能直观看出边界情况。比如在第一个节点前插入画图时你会发现头结点前面没有节点自然就想到要不要特判删除最后一个节点画图时看到它的 next 是 NULL自然就想到空指针判断。很多边界错误不是想不到而是没画图所以没看见。我备考时专门准备了一本草稿本每道链表题都画图画完再写代码。后来发现那些反复出错的题几乎都是画图时漏画了某个箭头导致的。这个习惯看起来笨但性价比极高。5.2 复杂度分析要落到基本操作上很多人分析复杂度时凭感觉觉得有个循环就是 O(n)。更靠谱的做法是数基本操作的执行次数。顺序表插入的移动次数、链表遍历的指针跳转次数都是可以精确数出来的。数清楚了O(n) 还是 O(n²) 一目了然。举个容易错的例子在单链表中删除值为 x 的所有节点。如果每删一个就从头重新找那是 O(n²)如果一次遍历边找边删是 O(n)。区别就在于遍历这个基本操作执行了几遍。分析时把遍历一遍链表当成一个基本单位看它执行几次就不会错。还有个小技巧分析空间复杂度时看有没有随 n 增长而增长的额外空间。链表操作里如果只用了几个指针变量空间是 O(1)如果新建了一个和原表等长的链表空间是 O(n)。这个判断标准比死记结论可靠。5.3 手写代码时先写边界判断再写主逻辑我见过太多人写链表代码时先写主循环最后补边界判断结果边界判断和主逻辑对不上改来改去。更稳的顺序是函数一进来先把所有非法情况挡掉空表、位置越界、指针为空挡完之后剩下的就是一定能正常执行的主逻辑写起来心里踏实。以删除单链表第 i 个节点为例入口先判断i 是否小于 1、i 是否大于表长、链表是否为空。这三个判断做完后面的定位和删除就不会出意外。这种防御式编程的习惯在考试手写代码时能显著降低出错率因为阅卷老师最看重的就是边界处理是否完整。注意边界判断不是越多越好要判断真正可能发生的情况。比如带头结点的链表头指针本身不会为空除非初始化失败就不用判断头指针为空判断头结点的 next 为空即可。判断冗余了反而显得没想清楚。5.4 把逆置找中间判环这类套路题吃透链表题里有一批经典套路掌握了能覆盖一大片题目。逆置用头插法或三指针法找中间节点用快慢指针快指针走两步慢指针走一步判环用快慢指针相遇找倒数第 k 个用双指针保持 k 的距离。这些套路的共同点是用指针的相对运动代替额外的遍历或存储。拿判环来说快慢指针如果相遇说明有环这个结论的证明用到了在环里快指针每步追近慢指针一个节点必然追上的朴素道理。理解了这个道理就不会纠结为什么快指针走两步而不是三步——走两步保证每次追近一个走三步虽然也能追上但可能跳过分析起来麻烦。这些套路我建议不要死记代码而是记住用几个指针、各自怎么动、终止条件是什么这三要素代码现场推。死记的代码换个题面就不会用了理解了三要素才能迁移。6. 那些教材不会明说但考试会考的细节6.1 头结点的数据域到底存不存东西头结点的数据域教材一般说不存有效数据或可存表长等信息。考试里如果问头结点的作用标准答案是统一插入删除操作、方便处理空表和非空表。但如果题目问头结点的数据域能否存储有效数据答案是能只是通常不这么做因为一旦存了有效数据头结点就变成了实际节点很多头结点不算表长的约定就被打破了。我个人的做法是头结点数据域留空或存表长绝不存业务数据。这样所有从第一个实际节点开始的遍历逻辑都统一不会因为头结点特殊而多写分支。6.2 链表长度是否包含头结点这个问题考试爱挖坑。带头结点的单链表表长指的是实际数据节点的个数不包含头结点。所以一个只有头结点的链表表长是 0是空表。判断空表的条件是head-next NULL而不是head NULL。这个约定如果不清楚做题时求表长的循环边界就会写错。正确写法是从head-next开始计数每走一步计数加一走到 NULL 停止。如果从头结点开始数结果会多 1。6.3 顺序表扩容时为什么通常扩到两倍顺序表容量满了要扩容常见策略是扩到原来的 2 倍或 1.5 倍。为什么不是每次加固定长度因为如果每次只加 1插入 n 个元素总共要搬迁 12...n O(n²) 次而按倍数扩容搬迁次数是等比数列求和总共 O(n)均摊到每次插入是 O(1)。这个均摊分析的思想很重要它解释了为什么动态数组很多语言里的可变长数组的追加操作平均是 O(1)。扩到 2 倍还是 1.5 倍是个工程权衡2 倍扩容次数少但可能浪费较多空间1.5 倍空间利用率高但扩容更频繁。考试一般不深究倍数但按倍数扩容使均摊 O(1)这个结论要能说清楚。6.4 删除节点后 free 的顺序和野指针删除链表节点时正确顺序是先把前驱的 next 指向被删节点的后继再 free 被删节点。如果先 free 再改指针前驱的 next 就成了野指针。更隐蔽的坑是free 之后没有把指针置 NULL后续如果误用这个指针行为未定义。我的习惯是 free 之后立刻把局部指针变量置 NULL虽然对已经 free 的内存置 NULL 不能挽回什么但能防止后续代码误用。这个习惯在调试时特别有用因为野指针导致的崩溃往往位置飘忽置 NULL 后至少能快速定位到用了已释放的指针。6.5 循环链表判空和判满的特殊性循环链表的判空和普通链表不同。带头结点的循环单链表空表条件是head-next head头结点的 next 指回自己而不是head-next NULL。这个差别是因为循环链表没有 NULL 结尾末尾指回头部。循环队列的判空判满更经典为了区分空和满通常牺牲一个存储单元队空条件是front rear队满条件是(rear 1) % MaxSize front。这个牺牲一个单元的设计是为了避免空和满都是 front rear的歧义。理解了这个动机就不会记混判空判满的条件。7. 从笔记到实战我建议的练习路径学完线性表这一章光看笔记不够必须动手。我给自己定的练习路径是这样的先把顺序表的初始化、插入、删除、查找四个操作手写一遍不看书写完对照检查边界再把单链表的头插建表、尾插建表、按位插入、按位删除、按值删除各写一遍然后双链表的插入删除写一遍最后做五到十道综合题比如链表逆置、找中间节点、合并两个有序链表、判断回文、删除倒数第 k 个。这个路径的关键是先单结构后综合。单结构的代码写熟了综合题才有底气。我见过有人一上来就刷综合题结果每道题都卡在基础的指针操作上效率极低。基础操作就像乘法口诀背熟了才能做应用题。另外强烈建议用纸笔手写代码而不是在 IDE 里敲。IDE 有补全和报错会掩盖你对细节的不确定纸笔写出来的代码哪里不确定一目了然。考试也是纸笔提前适应这个环境很重要。我备考后期专门用空白纸默写各种链表操作默完再上机验证这个纸笔加验证的组合效果最好。最后分享一个我自己的检查方法写完任何链表代码用三个元素的例子手动跑一遍重点看第一个元素和最后一个元素的操作。第一个元素考验头结点的处理最后一个元素考验 NULL 的判断这两个位置对了中间的通常不会错。这个方法帮我抓出过无数边界 bug比盯着代码看有效得多。