尧图网页设计 
说实话我写这篇东西的起因有点朴素。带新人做项目的时候连着几个人在我面前栽在链表上有人连头插法建表的结果是逆序都说不对有人写着写着把链表head弄丢了。归根到底面试八股可以背但真到写代码的时候指针一绕就懵。后来我想了想问题出在很多人一开始学数据结构时就把线性表当“概念”学没有真正吃透顺序表和单链表这两个最基本的物理实现形态。写这篇文章就是想把“线性表”这一块从头到尾掰开揉碎。里面会有完整的C语言实现包括顺序表并集求解、单链表逆序、合并两个有序单链表这类高频考点也会把那些“书上一笔带过、实操才踩坑”的细节全部翻出来。不管你是正在上数据结构课的学生、准备考研刷题的人还是半路转码想补基础的这篇文章的目标只有一个让你看完之后能真正自己写出能跑的代码。1. 线性表的整体设计与思路拆解1.1 线性表到底是什么排队论线性表这个东西你用生活常识就能理解大半。它就是一个“排好队的序列”每个人都有且仅有一个前驱和一个后继除了队首和队尾。比如食堂打饭的队伍、书架上一排挨着的书都符合线性表的特征有限、有序、关系单一。脑门上不需要记“n个数据元素的有限序列”这种绕口定义你只需要抓两个关键词有限和序列。有限意味着数据不能无限多序列意味着数据有先来后到的顺序。在数学上它是抽象的可以由任意类型的数据元素组成而在计算机里我们真正要解决的是怎么在内存里安放这些“排队的人”。这就是整个线性表学习的核心矛盾——逻辑结构是线性的但你物理上存储它的方式不是唯一的。于是就有了两种经典方案一种是把人按顺序排在一个连续的大操场上顺序表另一种是人站得乱七八糟、每个人手里拿张纸条写着下一个人在哪链表。1.2 为什么先学顺序表和单链表很多教材把线性表放在栈、队列、树、图之前不是没有道理的。顺序表和单链表几乎覆盖了所有基础数据结构的实现套路连续存储靠下标计算链式存储靠指针搬运。你后面学的双向链表、循环链表、二叉树的孩子表示法本质上都是在“节点指针”这个骨架上做文章。顺序表和单链表共同解决的问题是一样的——用线性结构组织数据但它们的取舍完全相反顺序表用连续内存 下标访问打的是空间局部性和O(1)随机访问这张王牌。单链表用离散内存 指针串联赌的是插入删除不用搬运数据、内存不够还能拼碎片这张牌。没有谁绝对优于谁只有适合不适合。这也是我特别强调“不要死记结论要理解为什么”的原因。比如面试官问你“为什么链表插入是O(1)”你要是回答“因为只要改指针”那说明你只见树木——链表的插入确实是O(1)但前提是你已经站在要插入的节点上了。如果你拿到一个链表头节点想插到尾部那得先O(n)地走过去。这就是理解“为什么”和死记“是什么”的区别。1.3 学习路径怎么安排我建议的顺序是先顺序表后链表。原因是顺序表更贴近直觉它就是数组的进阶版你在C语言课里写过的数组操作几乎可以原封不动迁移过来。等顺序表吃透了再学链表时你只需要集中精力对付“指针怎么拉”这一个新问题而不必同时兼顾“数据怎么组织”。2. 顺序表连续空间带来的高效与代价2.1 存储结构设计与核心参数顺序表说白了就是动态数组。但和普通数组最大的区别是普通数组长度固定而顺序表维护了**当前有效元素个数size和当前容量capacity**这对孪生参数。数据结构定义我习惯这样写#define INIT_CAPACITY 4 typedef struct { int* data; // 指向动态分配的连续内存 int size; // 当前已存储的元素个数 int capacity; // 当前最大容量 } SeqList;这里有个小细节size是元素的个数capacity是最大能装多少。访问元素时用list.data[i]其中i的范围是0 i size这个边界一定要刻在脑子里。很多人写越界访问就是因为把size和capacity搞混了。2.2 初始化与动态扩容初始化逻辑很简单申请一块初始容量大小的空间把size清零。void initList(SeqList* list) { list-data (int*)malloc(INIT_CAPACITY * sizeof(int)); if (list-data NULL) { printf(内存分配失败\n); exit(1); } list-size 0; list-capacity INIT_CAPACITY; }关键是扩容。顺序表插入时如果size capacity就必须先扩容否则就会越界写内存。扩容的经典做法是申请一块新内存把旧数据搬过去释放旧内存。void expandCapacity(SeqList* list) { int newCapacity list-capacity * 2; int* newData (int*)malloc(newCapacity * sizeof(int)); if (newData NULL) { printf(扩容失败\n); exit(1); } for (int i 0; i list-size; i) { newData[i] list-data[i]; } free(list-data); list-data newData; list-capacity newCapacity; }至于为什么是扩2倍而不是扩1.1倍这是个很好的思考题。假设初始容量1每次扩2倍插入n个元素的总体移动次数大约是2n均摊下来每次插入是O(1)如果你每次只多扩一个位置那插入n个元素的总移动次数就是123...nO(n²)均摊下来每次插入是O(n)。扩容倍数太小频繁搬运数据性能直接崩。这也是Java的ArrayList默认扩1.5倍、C的vector扩2倍背后的逻辑。2.3 插入操作的完整实现与边界顺序表的插入分为三种场景头插、尾插、指定位置插。指定位置插是核心头插和尾插都是它的特例。在位置pos插入元素val的完整步骤如下检查pos是否合法要求0 pos size。检查容量满了就扩容。从最后一个元素开始把size-1到pos之间的元素统一往后挪一位。在pos位置写入新值。size。void insertAt(SeqList* list, int pos, int val) { if (pos 0 || pos list-size) { printf(插入位置不合法\n); return; } if (list-size list-capacity) { expandCapacity(list); } for (int i list-size; i pos; i--) { list-data[i] list-data[i - 1]; } list-data[pos] val; list-size; }为什么要从后往前搬因为如果你从前往后搬前面元素会直接覆盖后面还没搬的元素数据直接丢。这个顺序问题初次上手的人百分之百犯过。插入的时间复杂度分情况头插是O(n)尾插均摊O(1)指定位置平均O(n)。所以“顺序表插入是O(n)”这个说法严格来讲是不准确的尾插就是O(1)。2.4 删除操作的实现与边界删除操作的整体思路和插入对称。在位置pos删除元素后需要把pos1到size-1的元素统一往前挪一位然后size--。void deleteAt(SeqList* list, int pos) { if (pos 0 || pos list-size) { printf(删除位置不合法\n); return; } for (int i pos; i list-size - 1; i) { list-data[i] list-data[i 1]; } list-size--; }这里插入和删除的边界是个易混点。插入允许pos size相当于尾插但删除时pos size是非法的因为data[size]根本不存在。我自己带新人时的经验是凡是边界判断出问题先画一条0到size的数轴把pos标上去看。删除后要不要缩容一般不需要你只是逻辑上移除了元素物理空间留着反而是种资源池后续插入可以直接复用。只有当内存极度受限、长期删除不插入时才考虑缩容而且建议采用“低于容量四分之一才缩容到一半”的策略避免频繁扩缩抖动。2.5 实战拆解求解一般集合的并集问题这个题目是很多学校实验课和面试里都会出现的给定两个无序集合A和B求A ∪ B。核心思想是先复制A的所有元素到结果顺序表C然后遍历B中每个元素如果C中不存在该元素则插入C尾部。关键代码在“判断是否存在”这一步它需要一个按值查找函数int indexOf(SeqList* list, int val) { for (int i 0; i list-size; i) { if (list-data[i] val) { return i; } } return -1; } SeqList unionSet(SeqList* A, SeqList* B) { SeqList C; initList(C); for (int i 0; i A-size; i) { insertAt(C, C.size, A-data[i]); } for (int i 0; i B-size; i) { if (indexOf(C, B-data[i]) -1) { insertAt(C, C.size, B-data[i]); } } return C; }整体时间复杂度是O(n×m)n是A的大小m是B的大小。因为每次判断B中元素是否存在都要在C里线性查找。如果你要求更高性能可以先对两个集合排序再用归并思路把复杂度降到O(nlogn mlogm)但作为实验课来说O(n×m)已经足够展示顺序表的基本操作。这个例子还有个价值它把顺序表的按值查找、尾插、按位置插入全部串起来了相当于一套综合实践。2.6 顺序表的优缺点总结优点按下标访问是货真价实的O(1)数据紧凑、缓存命中率高实现简单、不需要处理指针。缺点插入删除涉及大量数据搬移扩容时需要额外的内存拷贝而且扩容策略选不好时性能抖动会很严重。顺序表适合的是“读多写少”的场景——数据量相对稳定、频繁按下标访问、很少在中间插删。比如一个排行榜、一个按照索引读取的配置表。3. 单链表指针把离散空间穿成线3.1 为什么要用链表顺序表的问题在内存碎片化和插删成本上。想象一下你内存里空闲空间其实挺多但每一块都不连续每一块都小于你要申请的总大小malloc就会失败。链表的思路是不要求你一次性交出连续空间我在每个节点里存一份数据外加一个指针指向下一个节点用指针把这些分散的位置串成一条逻辑上的线。链表的本质就是“空间换时间的赌注”牺牲掉指针占用的额外存储通常8字节换来了O(1)的插入删除前提是已有目标节点的前驱以及不必一次性申请大片连续内存的灵活性。3.2 单链表的结构体定义typedef struct Node { int data; struct Node* next; } Node;这里必须注意C语言结构体里不能用Node直接声明next字段的指针吗实际上可以但前提是在typedef名字生效之前结构体内部必须用struct Node*这种形式。因为typedef是在结构体定义结束时才生效的结构体内部Node这个名字还不存在。关于用不用头节点dummy head我的建议是刷题和实现时带头节点。头节点不存数据它的next指向真正的第一个数据节点。带头节点的好处是所有操作尤其是删除和头插都统一了不需要单独处理“链表为空”和“删除第一个节点”的特殊情况逻辑分支少很多。3.3 基本操作头插、尾插、按值删除头插法是最简单的插入方式但它有个容易让人误解的地方——头插法建表的顺序和输入顺序相反。void insertHead(Node* head, int val) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next head-next; head-next newNode; }这里有一个经典错误顺序如果先把head-next赋值给newNode-next之后再去改head-next那没问题但如果反过来先把head-next指向newNode再设置newNode-next那原来的链表就丢了一截。正确顺序必须记住先搭好新节点的next再改前驱的next。因为一旦前驱的next指向新节点旧链表的“入口”就没了你再也找不到后半个链表。尾插法需要先遍历到尾节点然后把新节点接上去。注意遍历终止条件是p-next ! NULL而不是p ! NULL否则你停在NULL上没法接节点了。void insertTail(Node* head, int val) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next NULL; Node* p head; while (p-next ! NULL) { p p-next; } p-next newNode; }按值删除的要点是找前驱因为单链表只能向前走你删一个节点必须知道它前面是谁。删除的完整流程是遍历时用一个prev指针同步记录当前节点的前驱找到目标后将prev-next指向target-next然后free(target)。void deleteByValue(Node* head, int val) { Node* prev head; Node* cur head-next; while (cur ! NULL cur-data ! val) { prev cur; cur cur-next; } if (cur ! NULL) { prev-next cur-next; free(cur); } }这个函数里prev和cur不能用一个指针搞定除非你用二级指针或者递归否则删除了目标之后你没法再操作它的前驱。3.4 核心高频操作单链表逆序单链表逆序是面试和笔试里出现频率极高的题几乎每个考链表的公司都问过。它考察的不是你会不会背代码而是你懂不懂指针搬移的顺序。迭代法是空间O(1)的最优解法核心是三个指针prev前驱、cur当前节点、next后驱。每轮循环做三件事先保存next再把cur-next指回prev最后整体后移。Node* reverseList(Node* head) { Node* prev NULL; Node* cur head; while (cur ! NULL) { Node* next cur-next; cur-next prev; prev cur; cur next; } return prev; }这里有个刚接触时很容易绕晕的点为什么要先保存next因为当你执行cur-next prev的时候cur原本的next就丢了。没有next指针的话下一轮你就不知道往哪走了。这个“先保存再改”的顺序跟头插法新节点先搭next再改head是同一个道理本质上是**“任何指针被覆盖前都要先留下逃生通道”**。Python版本很多人喜欢用一行交换来写我顺便给出来def reverse_list(head: Optional[ListNode]) - Optional[ListNode]: prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prevPython和C的逻辑完全一样只是不需要手动管理内存。另外递归法也可以实现逆序思路是先把后续部分逆好再让原头节点的next指向自己、自己指向空。但递归的代价是额外栈空间O(n)在数据量大的时候可能会爆栈。3.5 核心高频操作合并两个有序单链表合并两个有序链表是另一个高频题考法是两个链表各自有序合并后仍然有序。最简洁的实现是递归但递归的空间开销是O(nm)。迭代法配合**哨兵节点dummy**是更推荐面试中的写法。Node* mergeTwoLists(Node* l1, Node* l2) { Node dummy; dummy.next NULL; Node* tail dummy; while (l1 ! NULL l2 ! NULL) { if (l1-data l2-data) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next (l1 ! NULL) ? l1 : l2; return dummy.next; }这里的dummy节点非常讲究。它让我不用单独处理“第一个节点到底选l1还是l2”这个特殊逻辑因为dummy.next总是会被正确赋值。最后那个tail-next (l1 ! NULL) ? l1 : l2也很省事因为剩余的部分本来就是有序链表直接一次性接上即可。合并过程比较次数最多O(nm)次空间O(1)是标准的归并思路。这个代码学会之后leetcode上“合并K个升序链表”也只需要在此基础上做二分归并即可。3.6 关于循环单链表的一个提醒循环单链表就是把尾节点的next指向头节点形成一个环。它在约瑟夫问题、轮转调度里有很自然的应用。不要被“循环”两个字吓到它和普通单链表唯一的区别就是遍历的终止条件从p ! NULL变成了p ! head。唯一的坑是如果你用while (p ! NULL)去遍历循环链表会死循环跑半天都出不来。我见过有人调试这个问题调了一晚上最后发现就是少判了一个出发点。4. 顺序表和单链表的选型对比与进阶考点4.1 一张表讲清楚选型逻辑我整理过一张表带新人的时候直接甩给他们看维度顺序表单链表随机访问O(1)按下标直接算地址O(n)必须从头遍历插入/删除平均O(n)需要搬移已知前驱时O(1)空间占用紧凑但可能预留空闲额外存储next指针典型8字节缓存友好性高连续内存低节点分散扩容需要整体搬移到新空间不用随时申请节点适用场景读多写少、按下标访问写多读少、内存碎片化注意“链表插入删除是O(1)”这句话的前提是已知前驱节点。如果只给链头、要按值找节点然后删除那找到前驱本身就是O(n)。面试里区分这个细节基本上就能看出是不是真懂。4.2 工程实践里怎么选真实工程里绝大多数情况用的是动态数组也就是顺序表思想。Java的ArrayList、C的vector、Python的list、Go的slice底层全是顺序表。为什么因为现代计算机缓存极其宝贵连续内存的遍历速度远快于离散的链表节点跳转。即使链表在“插入删除”理论上更优但暂停指针在内存里乱跳所花费的时间往往比数组的搬移代价还高。那链表在工程里还有什么用呢主要场景一是LRU缓存淘汰算法里的哈希表双向链表结构二是文件系统、内存管理里把空闲块串起来的组织方式三是操作系统内核的一些任务队列。这些场景的共同特征是数据本身分散、大小不确定、需要频繁改前后关系。4.3 高频进阶面试题串讲掌握了基础操作之后以下几个题几乎是链表板块的必答题判断链表是否有环快慢指针一个每次走两步、一个每次走一步有环就一定会相遇。时间复杂度O(n)空间O(1)。找到链表的中间节点同样是快慢指针快指针到末尾时慢指针正好在中间。找倒数第k个节点第一个指针先走k步然后两个指针同步走第一个走到尾时第二个就是倒数第k个。判断两个链表是否相交先分别求长度让长的先走差值步然后同步遍历找相同节点。这些题看起来五花八门骨子里全是同一件事指针的移动时机和终止条件。很多人觉得链表难难不在代码难在脑子里没有把节点的next关系画出来。我自己的习惯是遇到指针操作先画一张节点图标清楚每一步谁指向谁再动手写代码。写完之后用几个特殊场景测试空链表、只有一个节点、两个节点、环。5. 常见问题与排查技巧实录5.1 新手最容易踩的四个坑坑一链表头部插入后整个链表丢了。原因通常是先改了head-next再设置新节点的next导致原来的后续节点失联。排查技巧是插入前先把链表长度打印出来插入后打印如果变短了说明后半个链表丢了。坑二删除节点后忘free。这是C语言的经典内存泄漏。删除后不释放程序跑一会儿内存就涨上去了。排查手段是配合Valgrind或者AddressSanitizer跑一遍它会直接报告泄漏点。坑三free之后继续用指针。这是野指针问题。释放后的指针应该立即置为NULL否则一旦被复用就产生未定义行为。坑四顺序表插入时没检查容量直接把数据写到了越界位置。C语言不报错但会悄悄篡改相邻内存。这类bug最难查只能靠valgrind或者ASAN报“heap-buffer-overflow”才能定位。5.2 我自己调试链表的土办法调试这事我试过各种高端手段最后还是觉得最简单的办法最好用写一个printList函数把链表从头到尾的值打印出来每次操作后调一次。写一个getListLength每次插入删除之后核对长度变化。憋不住的时候直接画图把每个指针指到哪写清楚。这事听起来土但它比gdb单步调试有效率得多。因为链表的bug往往是逻辑层面的“指针指向错位”你用眼睛看着数据流反而比断点更容易发现。5.3 常见问题速查症状可能原因解决办法链表打印出来只有部分节点插入顺序出错旧节点被覆盖丢失检查插入代码确保先改新节点再改前驱打印出现死循环不停输出循环终止条件写错常见于循环链表检查while判断条件不要用p ! NULLfree之后崩溃野指针访问free后置NULL统一指针管理顺序表打印出现乱码越界写或未初始化检查插入时容量判断和初始化代码删除后前一个节点的next还是自己删除逻辑里前驱定位错检查prev和cur推进顺序逆序后链表只剩一个节点逆序循环里next指针没保存好确认循环内先存next再改next合并后结果出现重复或漏点比较条件写反确认的归属画两个链表模拟一遍5.4 给新手的建议从手画图到写代码我最后想认真说一句链表真的不是靠“背”能搞定的。你可以在考前把代码记下来但语言一换、API一变马上就露出马脚。真正扎实的做法是第一步拿一支笔和一张纸画一条有三个节点的链表手动模拟头插、尾插、逆序、删除每一步都画出指针的变化第二步不看任何参考自己用C语言写出来跑通第三步把链表换成循环链表再实现一遍。三步走完链表这一关差不多就过了一大半。我自己在实际教学中见过太多人卡在“看书觉得懂了、写代码不会”之间后来带着他们画了几遍图问题往往在半小时内就解决了。这个办法比任何教程都管用因为画图逼着你去思考指针的状态变化而写代码只是把思考过程落地而已。 线性表从顺序表到单链表：核心原理与C语言实战解析
说实话我写这篇东西的起因有点朴素。带新人做项目的时候连着几个人在我面前栽在链表上有人连头插法建表的结果是逆序都说不对有人写着写着把链表head弄丢了。归根到底面试八股可以背但真到写代码的时候指针一绕就懵。后来我想了想问题出在很多人一开始学数据结构时就把线性表当“概念”学没有真正吃透顺序表和单链表这两个最基本的物理实现形态。写这篇文章就是想把“线性表”这一块从头到尾掰开揉碎。里面会有完整的C语言实现包括顺序表并集求解、单链表逆序、合并两个有序单链表这类高频考点也会把那些“书上一笔带过、实操才踩坑”的细节全部翻出来。不管你是正在上数据结构课的学生、准备考研刷题的人还是半路转码想补基础的这篇文章的目标只有一个让你看完之后能真正自己写出能跑的代码。1. 线性表的整体设计与思路拆解1.1 线性表到底是什么排队论线性表这个东西你用生活常识就能理解大半。它就是一个“排好队的序列”每个人都有且仅有一个前驱和一个后继除了队首和队尾。比如食堂打饭的队伍、书架上一排挨着的书都符合线性表的特征有限、有序、关系单一。脑门上不需要记“n个数据元素的有限序列”这种绕口定义你只需要抓两个关键词有限和序列。有限意味着数据不能无限多序列意味着数据有先来后到的顺序。在数学上它是抽象的可以由任意类型的数据元素组成而在计算机里我们真正要解决的是怎么在内存里安放这些“排队的人”。这就是整个线性表学习的核心矛盾——逻辑结构是线性的但你物理上存储它的方式不是唯一的。于是就有了两种经典方案一种是把人按顺序排在一个连续的大操场上顺序表另一种是人站得乱七八糟、每个人手里拿张纸条写着下一个人在哪链表。1.2 为什么先学顺序表和单链表很多教材把线性表放在栈、队列、树、图之前不是没有道理的。顺序表和单链表几乎覆盖了所有基础数据结构的实现套路连续存储靠下标计算链式存储靠指针搬运。你后面学的双向链表、循环链表、二叉树的孩子表示法本质上都是在“节点指针”这个骨架上做文章。顺序表和单链表共同解决的问题是一样的——用线性结构组织数据但它们的取舍完全相反顺序表用连续内存 下标访问打的是空间局部性和O(1)随机访问这张王牌。单链表用离散内存 指针串联赌的是插入删除不用搬运数据、内存不够还能拼碎片这张牌。没有谁绝对优于谁只有适合不适合。这也是我特别强调“不要死记结论要理解为什么”的原因。比如面试官问你“为什么链表插入是O(1)”你要是回答“因为只要改指针”那说明你只见树木——链表的插入确实是O(1)但前提是你已经站在要插入的节点上了。如果你拿到一个链表头节点想插到尾部那得先O(n)地走过去。这就是理解“为什么”和死记“是什么”的区别。1.3 学习路径怎么安排我建议的顺序是先顺序表后链表。原因是顺序表更贴近直觉它就是数组的进阶版你在C语言课里写过的数组操作几乎可以原封不动迁移过来。等顺序表吃透了再学链表时你只需要集中精力对付“指针怎么拉”这一个新问题而不必同时兼顾“数据怎么组织”。2. 顺序表连续空间带来的高效与代价2.1 存储结构设计与核心参数顺序表说白了就是动态数组。但和普通数组最大的区别是普通数组长度固定而顺序表维护了**当前有效元素个数size和当前容量capacity**这对孪生参数。数据结构定义我习惯这样写#define INIT_CAPACITY 4 typedef struct { int* data; // 指向动态分配的连续内存 int size; // 当前已存储的元素个数 int capacity; // 当前最大容量 } SeqList;这里有个小细节size是元素的个数capacity是最大能装多少。访问元素时用list.data[i]其中i的范围是0 i size这个边界一定要刻在脑子里。很多人写越界访问就是因为把size和capacity搞混了。2.2 初始化与动态扩容初始化逻辑很简单申请一块初始容量大小的空间把size清零。void initList(SeqList* list) { list-data (int*)malloc(INIT_CAPACITY * sizeof(int)); if (list-data NULL) { printf(内存分配失败\n); exit(1); } list-size 0; list-capacity INIT_CAPACITY; }关键是扩容。顺序表插入时如果size capacity就必须先扩容否则就会越界写内存。扩容的经典做法是申请一块新内存把旧数据搬过去释放旧内存。void expandCapacity(SeqList* list) { int newCapacity list-capacity * 2; int* newData (int*)malloc(newCapacity * sizeof(int)); if (newData NULL) { printf(扩容失败\n); exit(1); } for (int i 0; i list-size; i) { newData[i] list-data[i]; } free(list-data); list-data newData; list-capacity newCapacity; }至于为什么是扩2倍而不是扩1.1倍这是个很好的思考题。假设初始容量1每次扩2倍插入n个元素的总体移动次数大约是2n均摊下来每次插入是O(1)如果你每次只多扩一个位置那插入n个元素的总移动次数就是123...nO(n²)均摊下来每次插入是O(n)。扩容倍数太小频繁搬运数据性能直接崩。这也是Java的ArrayList默认扩1.5倍、C的vector扩2倍背后的逻辑。2.3 插入操作的完整实现与边界顺序表的插入分为三种场景头插、尾插、指定位置插。指定位置插是核心头插和尾插都是它的特例。在位置pos插入元素val的完整步骤如下检查pos是否合法要求0 pos size。检查容量满了就扩容。从最后一个元素开始把size-1到pos之间的元素统一往后挪一位。在pos位置写入新值。size。void insertAt(SeqList* list, int pos, int val) { if (pos 0 || pos list-size) { printf(插入位置不合法\n); return; } if (list-size list-capacity) { expandCapacity(list); } for (int i list-size; i pos; i--) { list-data[i] list-data[i - 1]; } list-data[pos] val; list-size; }为什么要从后往前搬因为如果你从前往后搬前面元素会直接覆盖后面还没搬的元素数据直接丢。这个顺序问题初次上手的人百分之百犯过。插入的时间复杂度分情况头插是O(n)尾插均摊O(1)指定位置平均O(n)。所以“顺序表插入是O(n)”这个说法严格来讲是不准确的尾插就是O(1)。2.4 删除操作的实现与边界删除操作的整体思路和插入对称。在位置pos删除元素后需要把pos1到size-1的元素统一往前挪一位然后size--。void deleteAt(SeqList* list, int pos) { if (pos 0 || pos list-size) { printf(删除位置不合法\n); return; } for (int i pos; i list-size - 1; i) { list-data[i] list-data[i 1]; } list-size--; }这里插入和删除的边界是个易混点。插入允许pos size相当于尾插但删除时pos size是非法的因为data[size]根本不存在。我自己带新人时的经验是凡是边界判断出问题先画一条0到size的数轴把pos标上去看。删除后要不要缩容一般不需要你只是逻辑上移除了元素物理空间留着反而是种资源池后续插入可以直接复用。只有当内存极度受限、长期删除不插入时才考虑缩容而且建议采用“低于容量四分之一才缩容到一半”的策略避免频繁扩缩抖动。2.5 实战拆解求解一般集合的并集问题这个题目是很多学校实验课和面试里都会出现的给定两个无序集合A和B求A ∪ B。核心思想是先复制A的所有元素到结果顺序表C然后遍历B中每个元素如果C中不存在该元素则插入C尾部。关键代码在“判断是否存在”这一步它需要一个按值查找函数int indexOf(SeqList* list, int val) { for (int i 0; i list-size; i) { if (list-data[i] val) { return i; } } return -1; } SeqList unionSet(SeqList* A, SeqList* B) { SeqList C; initList(C); for (int i 0; i A-size; i) { insertAt(C, C.size, A-data[i]); } for (int i 0; i B-size; i) { if (indexOf(C, B-data[i]) -1) { insertAt(C, C.size, B-data[i]); } } return C; }整体时间复杂度是O(n×m)n是A的大小m是B的大小。因为每次判断B中元素是否存在都要在C里线性查找。如果你要求更高性能可以先对两个集合排序再用归并思路把复杂度降到O(nlogn mlogm)但作为实验课来说O(n×m)已经足够展示顺序表的基本操作。这个例子还有个价值它把顺序表的按值查找、尾插、按位置插入全部串起来了相当于一套综合实践。2.6 顺序表的优缺点总结优点按下标访问是货真价实的O(1)数据紧凑、缓存命中率高实现简单、不需要处理指针。缺点插入删除涉及大量数据搬移扩容时需要额外的内存拷贝而且扩容策略选不好时性能抖动会很严重。顺序表适合的是“读多写少”的场景——数据量相对稳定、频繁按下标访问、很少在中间插删。比如一个排行榜、一个按照索引读取的配置表。3. 单链表指针把离散空间穿成线3.1 为什么要用链表顺序表的问题在内存碎片化和插删成本上。想象一下你内存里空闲空间其实挺多但每一块都不连续每一块都小于你要申请的总大小malloc就会失败。链表的思路是不要求你一次性交出连续空间我在每个节点里存一份数据外加一个指针指向下一个节点用指针把这些分散的位置串成一条逻辑上的线。链表的本质就是“空间换时间的赌注”牺牲掉指针占用的额外存储通常8字节换来了O(1)的插入删除前提是已有目标节点的前驱以及不必一次性申请大片连续内存的灵活性。3.2 单链表的结构体定义typedef struct Node { int data; struct Node* next; } Node;这里必须注意C语言结构体里不能用Node直接声明next字段的指针吗实际上可以但前提是在typedef名字生效之前结构体内部必须用struct Node*这种形式。因为typedef是在结构体定义结束时才生效的结构体内部Node这个名字还不存在。关于用不用头节点dummy head我的建议是刷题和实现时带头节点。头节点不存数据它的next指向真正的第一个数据节点。带头节点的好处是所有操作尤其是删除和头插都统一了不需要单独处理“链表为空”和“删除第一个节点”的特殊情况逻辑分支少很多。3.3 基本操作头插、尾插、按值删除头插法是最简单的插入方式但它有个容易让人误解的地方——头插法建表的顺序和输入顺序相反。void insertHead(Node* head, int val) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next head-next; head-next newNode; }这里有一个经典错误顺序如果先把head-next赋值给newNode-next之后再去改head-next那没问题但如果反过来先把head-next指向newNode再设置newNode-next那原来的链表就丢了一截。正确顺序必须记住先搭好新节点的next再改前驱的next。因为一旦前驱的next指向新节点旧链表的“入口”就没了你再也找不到后半个链表。尾插法需要先遍历到尾节点然后把新节点接上去。注意遍历终止条件是p-next ! NULL而不是p ! NULL否则你停在NULL上没法接节点了。void insertTail(Node* head, int val) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next NULL; Node* p head; while (p-next ! NULL) { p p-next; } p-next newNode; }按值删除的要点是找前驱因为单链表只能向前走你删一个节点必须知道它前面是谁。删除的完整流程是遍历时用一个prev指针同步记录当前节点的前驱找到目标后将prev-next指向target-next然后free(target)。void deleteByValue(Node* head, int val) { Node* prev head; Node* cur head-next; while (cur ! NULL cur-data ! val) { prev cur; cur cur-next; } if (cur ! NULL) { prev-next cur-next; free(cur); } }这个函数里prev和cur不能用一个指针搞定除非你用二级指针或者递归否则删除了目标之后你没法再操作它的前驱。3.4 核心高频操作单链表逆序单链表逆序是面试和笔试里出现频率极高的题几乎每个考链表的公司都问过。它考察的不是你会不会背代码而是你懂不懂指针搬移的顺序。迭代法是空间O(1)的最优解法核心是三个指针prev前驱、cur当前节点、next后驱。每轮循环做三件事先保存next再把cur-next指回prev最后整体后移。Node* reverseList(Node* head) { Node* prev NULL; Node* cur head; while (cur ! NULL) { Node* next cur-next; cur-next prev; prev cur; cur next; } return prev; }这里有个刚接触时很容易绕晕的点为什么要先保存next因为当你执行cur-next prev的时候cur原本的next就丢了。没有next指针的话下一轮你就不知道往哪走了。这个“先保存再改”的顺序跟头插法新节点先搭next再改head是同一个道理本质上是**“任何指针被覆盖前都要先留下逃生通道”**。Python版本很多人喜欢用一行交换来写我顺便给出来def reverse_list(head: Optional[ListNode]) - Optional[ListNode]: prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prevPython和C的逻辑完全一样只是不需要手动管理内存。另外递归法也可以实现逆序思路是先把后续部分逆好再让原头节点的next指向自己、自己指向空。但递归的代价是额外栈空间O(n)在数据量大的时候可能会爆栈。3.5 核心高频操作合并两个有序单链表合并两个有序链表是另一个高频题考法是两个链表各自有序合并后仍然有序。最简洁的实现是递归但递归的空间开销是O(nm)。迭代法配合**哨兵节点dummy**是更推荐面试中的写法。Node* mergeTwoLists(Node* l1, Node* l2) { Node dummy; dummy.next NULL; Node* tail dummy; while (l1 ! NULL l2 ! NULL) { if (l1-data l2-data) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next (l1 ! NULL) ? l1 : l2; return dummy.next; }这里的dummy节点非常讲究。它让我不用单独处理“第一个节点到底选l1还是l2”这个特殊逻辑因为dummy.next总是会被正确赋值。最后那个tail-next (l1 ! NULL) ? l1 : l2也很省事因为剩余的部分本来就是有序链表直接一次性接上即可。合并过程比较次数最多O(nm)次空间O(1)是标准的归并思路。这个代码学会之后leetcode上“合并K个升序链表”也只需要在此基础上做二分归并即可。3.6 关于循环单链表的一个提醒循环单链表就是把尾节点的next指向头节点形成一个环。它在约瑟夫问题、轮转调度里有很自然的应用。不要被“循环”两个字吓到它和普通单链表唯一的区别就是遍历的终止条件从p ! NULL变成了p ! head。唯一的坑是如果你用while (p ! NULL)去遍历循环链表会死循环跑半天都出不来。我见过有人调试这个问题调了一晚上最后发现就是少判了一个出发点。4. 顺序表和单链表的选型对比与进阶考点4.1 一张表讲清楚选型逻辑我整理过一张表带新人的时候直接甩给他们看维度顺序表单链表随机访问O(1)按下标直接算地址O(n)必须从头遍历插入/删除平均O(n)需要搬移已知前驱时O(1)空间占用紧凑但可能预留空闲额外存储next指针典型8字节缓存友好性高连续内存低节点分散扩容需要整体搬移到新空间不用随时申请节点适用场景读多写少、按下标访问写多读少、内存碎片化注意“链表插入删除是O(1)”这句话的前提是已知前驱节点。如果只给链头、要按值找节点然后删除那找到前驱本身就是O(n)。面试里区分这个细节基本上就能看出是不是真懂。4.2 工程实践里怎么选真实工程里绝大多数情况用的是动态数组也就是顺序表思想。Java的ArrayList、C的vector、Python的list、Go的slice底层全是顺序表。为什么因为现代计算机缓存极其宝贵连续内存的遍历速度远快于离散的链表节点跳转。即使链表在“插入删除”理论上更优但暂停指针在内存里乱跳所花费的时间往往比数组的搬移代价还高。那链表在工程里还有什么用呢主要场景一是LRU缓存淘汰算法里的哈希表双向链表结构二是文件系统、内存管理里把空闲块串起来的组织方式三是操作系统内核的一些任务队列。这些场景的共同特征是数据本身分散、大小不确定、需要频繁改前后关系。4.3 高频进阶面试题串讲掌握了基础操作之后以下几个题几乎是链表板块的必答题判断链表是否有环快慢指针一个每次走两步、一个每次走一步有环就一定会相遇。时间复杂度O(n)空间O(1)。找到链表的中间节点同样是快慢指针快指针到末尾时慢指针正好在中间。找倒数第k个节点第一个指针先走k步然后两个指针同步走第一个走到尾时第二个就是倒数第k个。判断两个链表是否相交先分别求长度让长的先走差值步然后同步遍历找相同节点。这些题看起来五花八门骨子里全是同一件事指针的移动时机和终止条件。很多人觉得链表难难不在代码难在脑子里没有把节点的next关系画出来。我自己的习惯是遇到指针操作先画一张节点图标清楚每一步谁指向谁再动手写代码。写完之后用几个特殊场景测试空链表、只有一个节点、两个节点、环。5. 常见问题与排查技巧实录5.1 新手最容易踩的四个坑坑一链表头部插入后整个链表丢了。原因通常是先改了head-next再设置新节点的next导致原来的后续节点失联。排查技巧是插入前先把链表长度打印出来插入后打印如果变短了说明后半个链表丢了。坑二删除节点后忘free。这是C语言的经典内存泄漏。删除后不释放程序跑一会儿内存就涨上去了。排查手段是配合Valgrind或者AddressSanitizer跑一遍它会直接报告泄漏点。坑三free之后继续用指针。这是野指针问题。释放后的指针应该立即置为NULL否则一旦被复用就产生未定义行为。坑四顺序表插入时没检查容量直接把数据写到了越界位置。C语言不报错但会悄悄篡改相邻内存。这类bug最难查只能靠valgrind或者ASAN报“heap-buffer-overflow”才能定位。5.2 我自己调试链表的土办法调试这事我试过各种高端手段最后还是觉得最简单的办法最好用写一个printList函数把链表从头到尾的值打印出来每次操作后调一次。写一个getListLength每次插入删除之后核对长度变化。憋不住的时候直接画图把每个指针指到哪写清楚。这事听起来土但它比gdb单步调试有效率得多。因为链表的bug往往是逻辑层面的“指针指向错位”你用眼睛看着数据流反而比断点更容易发现。5.3 常见问题速查症状可能原因解决办法链表打印出来只有部分节点插入顺序出错旧节点被覆盖丢失检查插入代码确保先改新节点再改前驱打印出现死循环不停输出循环终止条件写错常见于循环链表检查while判断条件不要用p ! NULLfree之后崩溃野指针访问free后置NULL统一指针管理顺序表打印出现乱码越界写或未初始化检查插入时容量判断和初始化代码删除后前一个节点的next还是自己删除逻辑里前驱定位错检查prev和cur推进顺序逆序后链表只剩一个节点逆序循环里next指针没保存好确认循环内先存next再改next合并后结果出现重复或漏点比较条件写反确认的归属画两个链表模拟一遍5.4 给新手的建议从手画图到写代码我最后想认真说一句链表真的不是靠“背”能搞定的。你可以在考前把代码记下来但语言一换、API一变马上就露出马脚。真正扎实的做法是第一步拿一支笔和一张纸画一条有三个节点的链表手动模拟头插、尾插、逆序、删除每一步都画出指针的变化第二步不看任何参考自己用C语言写出来跑通第三步把链表换成循环链表再实现一遍。三步走完链表这一关差不多就过了一大半。我自己在实际教学中见过太多人卡在“看书觉得懂了、写代码不会”之间后来带着他们画了几遍图问题往往在半小时内就解决了。这个办法比任何教程都管用因为画图逼着你去思考指针的状态变化而写代码只是把思考过程落地而已。