链表这个东西我在带新人或者看开源代码的时候几乎每次都要拿出来讲一遍。你可以说它基础但真要用好里面门道不少。C语言里没有现成的容器不像C有STL的listJava有LinkedList你想在C里用链表就得从结构体定义开始一步步自己造轮子。这个过程说难不难但绝对值得走一遍因为链表不只是数据结构它背后那一套内存管理、指针操作的思维是C语言的核心。这篇文章的目标很直接让你看完之后能自己动手写出一个单链表能完成创建、插入、删除、遍历、反转这些基本操作并且知道在什么场景下该用链表而不是数组。我会从最底层的结构体定义开始讲配合内存视角解释每一步代码在干什么最后再聊聊实际项目中那些避开坑的经验。适合刚学完C语言基础、准备进阶的同学也适合工作中遇到链表相关代码但一直没捋清楚的开发者。1. 折腾链表之前先想清楚数组哪里不够用1.1 数组的存储方式决定了它的读写特性很多人一开始接触C语言用的最多的数据结构就是数组。数组在内存里是一段连续的地址空间每个元素紧挨着排布。比如你定义int arr[10]那么arr[0]和arr[1]在内存里相差4个字节假设int占4字节。这种连续存储带来的好处是访问第n个元素特别快直接算地址arr n*sizeof(int)一步到位时间复杂度O(1)。但连续存储也带来了两个绕不开的问题。第一个问题创建数组的时候必须指定大小C语言里不支持动态扩容的数组。你预估了100个元素的容量结果业务发展了要存200个那就麻烦了。要么你一开始就开一个很大的数组浪费内存要么你手动重新分配一块更大的空间并把旧数据拷过去非常折腾。第二个问题在数组中间插入或删除一个元素为了保持连续性你必须把后面所有的元素都往前或往后挪一位。这个操作的代价是O(n)数据量一旦上来性能就会很难看。1.2 链表的思路用指针把散落的内存串起来链表的思想很简单既然连续内存有这些限制那我就不要求内存连续了。每个节点各管各的用指针把它们串起来。也就是说每个节点除了存数据还要存一个指针指向下一个节点。物理上它们可以东一个西一个但只要顺着指针走就能逐个访问到所有节点。这个设计带来什么好处首先是存储空间可以动态申请来一个数据就创建一个节点不会提前预判容量。其次是插入和删除只需要修改指针的指向不需要移动数据操作的时间复杂度是O(1)。当然代价也明显不能随机访问。你想找第n个节点必须从头开始一个个往后走复杂度O(n)而且每个节点需要一个指针变量会额外汇些内存开销。所以链表和数组不是谁完全替代谁而是取舍不同。频繁插入删除就用链表频繁按下标访问就用数组。我自己的经验是很多小的工具代码用数组就够了但一旦涉及数据量不确定、频繁增删、或者需要在多个容器之间移动数据的场景链表就会发光发热。2. 单链表手把手实现搞懂每个指针在干嘛2.1 节点的结构体怎么定义C语言里实现链表第一步就是定义节点的结构体。最简单的单链表一个节点包含一块数据和一个指向下一个节点的指针。数据这块初学者先用int就好了后面熟练了可以换成任意类型。typedef struct Node { int data; struct Node* next; } Node;注意这里struct Node* next是一个自引用指针也就是说节点结构体里存了指向另一个节点的地址。用typedef把struct Node重命名为Node后面写代码能省不少事。很多新手容易在这里卡住写typedef struct Node { int data; Node* next; } Node;注意在结构体内部还不能直接用Node因为typedef还没生效必须写成struct Node*。这里有个细节要特别留意next指针就好比一条链子上的环扣。链表能不能走下去全靠它串联。如果某个节点的next指错了或者没有置为NULL程序很可能会出大问题。所以我个人习惯是每次创建一个节点后立刻把next置为NULL不给野指针一点机会。2.2 创建节点和初始化链表有了结构体接下来就是创建链表了。创建链表有三种常见方式头插法、尾插法、以及插入到指定位置。先从创建单个节点开始。// 创建一个新节点返回节点指针 Node* createNode(int data) { Node* newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); return NULL; } newNode-data data; newNode-next NULL; return newNode; }这里用malloc动态分配内存分配完必须检查返回值是否为NULL。很多教材里会略过这个检查但实际工程里内存分配失败是会发生的尤其是长时间运行的程序。检查一下打印个错误日志总比程序莫名其妙崩掉好。接着是初始化一个空链表。链表要有个头指针指向链表的第一个节点。空链表的话头指针就是NULL。通常我们定义一个Node* head NULL;就代表一个空链表。还有一种写法是使用带虚拟头节点的链表即head指向一个不存数据的哨兵节点它的next才真正指向第一个有效节点。这种写法在链表为空、插入删除第一个节点时处理逻辑会统一很多后面碰到边界条件你就知道它的好了。2.3 头插法和尾插法到底用哪个头插法顾头思义新节点插在链表头部成为新的第一个节点时间复杂度O(1)。void insertAtHead(Node** head, int data) { Node* newNode createNode(data); newNode-next *head; *head newNode; }这里为什么传Node** head而不是Node* head这是很多初学者最容易迷惑的地方。因为我们要修改头指针本身的值让它指向新节点。如果只传Node* head在函数内部修改head那只是修改了形参的副本外部真正的头指针不会变。要想通过函数修改变量的值就必须传地址也就是二级指针。尾插法新节点插在链表尾部。需要先找到当前的最后一个节点。void insertAtTail(Node** head, int data) { Node* newNode createNode(data); if (*head NULL) { *head newNode; return; } Node* temp *head; while (temp-next ! NULL) { temp temp-next; } temp-next newNode; }尾插法的时间复杂度是O(n)因为要遍历到末尾。如果你频繁尾插且链表很长性能会受影响。这时候可以额外维护一个尾指针每次插入直接接在尾指针后面再更新尾指针这样也能做到O(1)。不过维护尾指针意味着每次插入删除都要考虑更新它逻辑上要多操一份心。通常简单的演示代码不会这么写但实际项目里这是很常见的优化。我个人在工程实现里更常用的其实是头插法加后续处理。因为头插法相当于是把链表反转了一次顺序在需要逆序输出、或者不要求保持插入顺序的场景下头插法效率高代码也简洁。2.4 遍历链表看看到底存了什么遍历是最基本的操作从head出发顺着next指针一路走过去直到遇到NULL。理解了遍历你就理解了链表的读取逻辑。void printList(Node* head) { Node* temp head; while (temp ! NULL) { printf(%d - , temp-data); temp temp-next; } printf(NULL\n); }这里我用一个temp指针来遍历而不是直接动head。为什么因为head是链表的入口一旦丢失后面所有节点都找不到了。很多新手在遍历时直接head head-next;遍历完发现 head 变成了 NULL链表整个丢了。记住向链表中传入头指针的函数如果不是要修改链表的头节点就不要去更改head的值。如果要修改那就传二级指针。另外特别提醒一个问题遍历时的循环条件while (temp ! NULL)和while (temp-next ! NULL)是有区别的。前者可以访问到最后一个节点后者会在最后一个节点就停下来。在链表操作中到底是停在最后一个节点还是越过后一个节点当终点取决于你要干什么。比如你要找倒数第二个节点用后者你要打印所有节点用前者。这个边界条件写代码之前心里先有个数。3. 链表操作的几个重点与难点逐个突破3.1 按值删除节点边界条件一个都不能少删除节点是链表操作里最容易出错的尤其是按值删除。逻辑上要分三种情况删的是头节点、删的是中间节点、删的是尾节点。虽然中间和尾可以合在一起处理但新手拆开理解比较容易。Node* deleteByValue(Node* head, int value) { Node* temp head; Node* prev NULL; // 如果头节点的值就是要删的 while (temp ! NULL temp-data value) { head temp-next; free(temp); temp head; } // 删除后续匹配的节点 while (temp ! NULL) { while (temp ! NULL temp-data ! value) { prev temp; temp temp-next; } if (temp NULL) { return head; } prev-next temp-next; free(temp); temp prev-next; } return head; }这段代码删除了链表中所有等于value的节点而不只是第一个。这里最核心的变量是prev它记录当前节点temp的前一个节点。删除temp时只要让prev-next跳过temp指向temp-next就相当于把temp从链中摘除了。摘除之后free(temp)释放内存然后temp prev-next继续往后扫描。这个地方有个非常容易踩的坑如果temp是头节点此时prev还是NULL不能执行prev-next temp-next因为prev是空指针。所以必须先单独处理头节点的情况。这就是我在前面提到的带虚拟头节点的链表能简化的地方——它让prev永不为NULL代码逻辑可以统一处理。3.2 反转链表笔试面试高频题本质是拆链和重连反转链表也是一个特别经典的题目。它看起来很绕但核心就一句话从头到尾遍历每访问一个节点就把它指向前一个节点。Node* reverseList(Node* head) { Node* prev NULL; Node* current head; Node* next NULL; while (current ! NULL) { next current-next; // 先保存下一个节点 current-next prev; // 反转指针 prev current; // prev 后移 current next; // current 后移 } return prev; // 遍历结束prev 就是新的头节点 }理解这段代码核心是搞清楚三指针的推进过程。current指向当前正在处理的节点prev指向已经处理好的那部分链表的头节点即当前节点的前一个next则提前把即将要处理的节点保存下来。为什么要保存next因为current-next prev这一步会把当前节点的 next 指针给覆盖掉如果不提前保存后面就找不到原来的下一个节点了链表就断了。反转这个操作我用一句话总结它考验的不是语法而是你能不能在心里画出三个指针在链上移动的过程。画不出来就动手比喻比如你有一串珠子你想倒着串每次拿起一个珠子把它前面的线换到后面。建议新手在纸上画出几个节点的初始和每步变化图多画几次就通了。3.3 检测环、找中间节点快慢指针经典应用除了基本操作链表还有一些进阶技巧最典型的是快慢指针。快指针一次走两步慢指针一次走一步。两个指针一起从头出发如果链表有环快慢指针一定会相遇如果没环快指针会先走到NULL。int hasCycle(Node* head) { Node* slow head; Node* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) { return 1; } } return 0; }循环条件里为什么是fast ! NULL fast-next ! NULL因为快指针一次走两步如果不先确认 fast 和 fast-next 都不为空直接访问fast-next-next就会访问空指针程序直接崩溃。这个边界条件的理解要比死记重要得多。还有找链表的中间节点也是快慢指针快指针走两步慢指针走一步当快指针到达末尾时慢指针刚好在中间。快慢指针的思想在很多链表和数组类问题上都能用到值得花时间掌握。4. 双链表和循环链表什么时候值得升级4.1 双链表的定义和插入删除优化单链表只有一个方向的指针从某个节点只能往后走不能回头。所以如果你想删除某个已知节点却不知道它的前一个节点只能从头遍历来找它的前趋时间复杂度O(n)。双链表就是来解决这个问题的每个节点增加一个prev指针指向前一个节点。这样无论是向前还是向后遍历都行了删除节点时也能直接通过prev找到前一个节点。typedef struct DNode { int data; struct DNode* prev; struct DNode* next; } DNode;双链表的插入和删除写起来比单链表要多几条语句因为要同时更新两个方向的指针。比如在节点p后面插入新节点newNodenewNode-next p-next; newNode-prev p; if (p-next ! NULL) { p-next-prev newNode; } p-next newNode;这里一定要注意如果p-next不为空得先把p-next-prev指向新节点然后再改p-next。顺序反了比如先执行p-next newNode那p原来的下一个节点就找不到了p-next-prev就操作到新节点上了链表结构直接损坏。双链表的指针操作强烈建议画图辅助写完代码再对着图走一遍检查有没有指针悬空。4.2 循环链表和约瑟夫环循环链表就是让尾节点的next指回头节点形成一个环。这个结构在需要循环处理的场景里很好用比如操作系统进程调度里的时间片轮转以及约瑟夫环问题。约瑟夫环问题我印象很深当时学的时候用循环链表解特别直观。一群人围成一圈从某个位置开始报数报到某个数字的人出列然后从下一个人继续报数直到所有人出列。用循环链表模拟这个过程每次要删除的就是当前报数到的那个节点删除后继续往下报数非常自然。// 约瑟夫环代码骨架 Node* josephus(Node* head, int k) { Node* p head; Node* prev NULL; // 先找到尾节点形成循环链表 // 然后循环删除报数到 k 的节点 while (p-next ! p) { // 找到第 k 个节点 for (int i 1; i k; i) { prev p; p p-next; } // 删除 p 节点 prev-next p-next; printf(出列: %d\n, p-data); free(p); p prev-next; } // 最后剩下的就是幸存者 return p; }这个代码看着简单但里面有很多边界细节比如如何正确找到尾节点形成环尾节点的 next 本来指向 NULL改一下指向头就行以及当链表只剩下一个节点时p-next p循环就该结束。约瑟夫环是我自己比较推荐用来练手链表的题目它能把插入、删除、循环遍历、边界判断全都用上而且逻辑清晰很适合检验自己有没有真的掌握链表。4.3 内核链表和高级链表的启发如果你看过Linux内核代码会发现内核里的链表定义方式跟上面讲的完全不一样。它不是把链表节点嵌入结构体而是反过来结构体里嵌一个链表节点struct list_head。这个list_head里面只包含next和prev指针通过container_of宏可以根据链表节点的地址计算出宿主结构体的地址从而找到数据。struct list_head { struct list_head *next, *prev; }; // 用法自定义结构体里嵌入 list_head struct my_data { int value; struct list_head list; };这种设计的妙处在于链表操作的代码是通用的不管你的数据是什么类型只要你把list_head嵌进去就能用同一套函数来管理。你用list_add插入节点用list_for_each遍历完全不用为每种数据类型写一套链表操作。我第一次看到这套东西的时候很震撼因为之前学的都是“链表里有数据”而内核这种是“数据里有链表”思维完全反过来了。后面我做项目如果某个结构体需要被多个链表同时管理比如同时按时间排序又按优先级排序就会想到这种嵌入式的做法在每个结构体里放两个list_head分别用于不同的链表挂接。这种思路在你理解了基础链表之后再去研究会打开一个新世界。5. 链表内存管理和信息清理最容易泄漏的地方5.1 动态内存分配和释放配对链表节点用malloc动态申请用完必须释放否则就会造成内存泄漏。一个链表占用的内存如果是几百几千个节点可能还没什么感觉但在长期运行的服务器进程里频繁创建销毁链表而不释放内存占用会一路飙升最终导致程序被系统杀掉或者卡死。释放整个链表的操作用递归写也可以但更推荐循环写法因为递归深度太深会有栈溢出的风险。void freeList(Node* head) { Node* temp; while (head ! NULL) { temp head; head head-next; free(temp); } }这个循环的写法很典型先用temp保存当前要释放的节点然后把head往后移再释放temp。顺序不能颠倒必须先保存下一个节点再释放当前节点否则释放之后你再访问head-next读到的就是已经释放的内存。5.2 悬空指针问题悬空指针英文叫 dangling pointer指的是指针指向的内存已经被释放了但指针本身还保存着那个地址。这时如果再去访问这个指针行为是未定义的。可能碰巧还能读到旧数据也可能程序崩溃还可能把那块内存覆盖成别的内容查起来非常难。防止悬空指针最好的办法是在释放内存后立刻把指针置为NULL。比如free(temp); temp NULL;这样如果后面不小心又访问了这个指针你至少能通过检查temp NULL发现问题而不是对着一个野指针瞎调半宿。这也是我一直强调的free和 置NULL是两件事缺一不可。5.3 内存泄漏的排查工具程序跑着跑着内存越来越大怎么定位是不是链表泄漏了Linux 上用valgrind就很方便。编译的时候带-g选项保留调试信息然后跑valgrind --leak-checkfull ./your_program它会把泄漏的内存分配位置和大小全部打印出来。我在做 C 项目的时候几乎每跑一个程序都要用 valgrind 过一遍能省去很多后面排查的力气。除了 valgrindAddressSanitizer也很好用。编译时加上-fsanitizeaddress在代码执行到越界访问或者释放后再访问的地方会立刻报错定位问题比 valgrind 更快。这个工具在本地开发、CI 检查里都很值得配置上。6. 链表应用场景盘点面试题之外的实战价值6.1 操作系统和底层软件中的链表链表离我们不远。操作系统内部大量使用了链表比如进程控制块PCB的管理所有进程通过链表串起来方便遍历调度。文件系统里空闲块的管理也可以用链表来串接。设备驱动中的缓存、请求队列也常见链表的影子。C 语言下的很多基础库比如 glib 里的 GList、GQueueepoll 事件的就绪队列等本质上也是链表或者以链表作为底层结构。对做后端开发或者基础软件的人来说链表不是面试里的一道题而是每天都会碰到的现实。6.2 业务设计中链表的实际用法业务层面上凡是“不确定数量、频繁增删、有序遍历”的场景都可以考虑链表。比如在线用户列表用户随时上线和下线用链表管理很合适。消息队列的实现如果用数组的话头部出队要整体移动用链表则队头出队只要改指针。LRU 缓存淘汰算法经典实现之一是“哈希表双链表”双链表用来记录访问顺序每次访问就把节点移到链表头部淘汰时从尾部删除这个结构很多语言里的 OrderedDict 就是这么实现的。还有在游戏开发里渲染对象的层级关系、碰撞检测中动态实体集合的管理用链表往往比用数组更灵活。当然现代游戏引擎有更复杂的数据结构但链表思想依然在里面起着基础作用。6.3 链表选型的后半段建议说句实在话也不要神话链表。C 语言里没有现成的高层容器链表因为实现简单、不需要依赖第三方库成了很多 C 项目的首选。但如果你的需求是频繁按下标访问或者数据量小到数组绰绰有余那直接用数组、甚至用静态数组配合一个size变量记录长度会简单得多。数据量在几百条以内数组遍历一次也就是几微秒没必要为了“用链表而用链表”。还有一点如果你的数据需要频繁增删但增删的位置随机而且你能快速定位到目标位置链表的 O(1) 才有意义。如果每次增删前都要 O(n) 查找位置那总代价还是 O(n)这时候用平衡树、哈希表之类的结构可能更合适。选型这件事永远是需求优先。7. 常见问题排查链表代码写崩了怎么定位以下是常见问题速查表也是我过去几年里被问过最多的问题症状可能原因排查思路程序崩溃 segmentation fault访问了 NULL 指针或野指针检查循环条件打印节点地址确认是否有节点next为NULL但没有处理插入后链表顺序不对头插/尾插/指定位置插入逻辑混乱画图走一遍代码确认prev-next和temp-next的赋值顺序链表遍历之后 head 丢了遍历时直接改了 head 值遍历使用临时指针temp head不要动原 head删除节点后链表断了前一个节点的 next 没有指向被删节点的 next用prev-next temp-next;代替prev temp-next;程序运行时间长了内存暴涨动态分配的节点没有 free用 valgrind/ASan 检查泄漏位置确认 free 和 malloc 配对反转链表后只剩两个节点三指针中next保存时机不对每步先保存next current-next再修改current-next判断链表是否有环时死循环快慢指针移动条件处理不当确认fast ! NULL fast-next ! NULL这里边最常见的恐怕还是删除节点后链表断裂的问题。很多人删完节点直接temp temp-next但此时temp已经被free了temp-next访问的是已释放的内存程序崩溃或者在极端情况下修到了别的进程的内存。所以我说写完删除节点的函数一定要在脑海里或者画图走一遍确认每个节点的指针在删除前后都指向正确的位置。8. 一次完整的链表项目实践通讯录管理系统8.1 需求拆解与结构设计讲了这么多理论来一个完整的实践项目把链表串起来用一遍。这个项目是很多学校的C语言课程设计用链表实现一个简单的通讯录。功能包括添加联系人、删除联系人、查找联系人、修改联系人和按姓名排序。先定义通讯录的数据结构这里我直接用一个双链表因为经常需要向前遍历按姓名排序时前后交换节点方便typedef struct Contact { char name[50]; char phone[20]; struct Contact* prev; struct Contact* next; } Contact;8.2 核心功能的实现逻辑添加联系人时不从头插也不从尾插而是按照姓名字典序插入这样通讯录天然有序查找和展示都方便。插入的核心逻辑就是在链表中找到合适的位置然后进行双向链表的指针修改。代码如下void addContact(Contact** head, const char* name, const char* phone) { Contact* newNode (Contact*)malloc(sizeof(Contact)); strcpy(newNode-name, name); strcpy(newNode-phone, phone); newNode-prev NULL; newNode-next NULL; if (*head NULL) { *head newNode; return; } // 如果新节点应该插在头节点前面 if (strcmp(newNode-name, (*head)-name) 0) { newNode-next *head; (*head)-prev newNode; *head newNode; return; } Contact* temp *head; // 找到第一个比新节点名字大的节点 while (temp-next ! NULL strcmp(temp-next-name, newNode-name) 0) { temp temp-next; } // 插入到 temp 后面 newNode-next temp-next; if (temp-next ! NULL) { temp-next-prev newNode; } newNode-prev temp; temp-next newNode; }这里strcmp是字符串比较函数按字典序比较。这个插入逻辑涵盖了四种情况链表为空、插在头部、插在中间、插在尾部。判断条件temp-next ! NULL strcmp(temp-next-name, newNode-name) 0表示只要下一个节点存在并且下一个节点的名字比新节点的名字小就继续往后走。循环结束时要么temp-next为空新节点比所有现有节点名字都大插在尾部要么temp-next-name大于等于新节点的名字插在中间。8.3 从项目中学到什么这个项目虽然简单但把链表的增删改查、排序、遍历、内存释放全部覆盖了。更重要的是它能帮助你养成“先画图再写代码”的习惯。很多初学者写链表经常一个函数调半天就是因为心里没有链表的内存图。写链表代码之前先把要操作的节点和指针变化在纸上画出来代码写起来就是照着图填语句准确率会大幅提升。做完这个项目后你可以试着把它升级比如改成按电话号码查找增加分组管理的功能或者把数据持久化到文件里重启程序还能恢复。这些扩展都会逼迫你去深入思考链表和实际需求的结合方式。9. 我对链表学习路径的几点心得写代码这件事光看不写是永远学不会的。链表尤其如此因为它的核心是内存和指针的抽象思维这种能力只能通过亲手实现来建立。我的建议路径是先用单链表实现一遍增删改查再用双链表实现一遍然后用循环链表解决约瑟夫环问题最后理解和模仿内核链表的设计。每一步都在前一步的基础上增加新的复杂度走得比较稳。调试链表代码强烈建议打印大法配合指针地址一起看。比如遍历时不仅打印data顺便把temp和temp-next的地址也打出来你能非常直观地看到链表的走向和指针之间的关系往往一眼就能定位断链的位置。有时候看代码看了半天没发现问题一打印地址就明白了。最后说一句链表是理解很多复杂数据结构的基础。树、图这些更复杂的结构本质上都是链表节点的多向延伸。你把链表的指针操作练得滚瓜烂熟了后面学二叉树、平衡树、图遍历难度都会断崖式下降。这个基本功值得你花时间好好打。