提到“数据结构”和“链表”这两个词，但凡学过编程的人应该都不会陌生。我记得自己刚接触链表的时候，总觉得它比数组绕：数组一片连续的内存按顺序摆好，想访问哪个下标直接就去了，多痛快。链表倒好，每个节点里除了数据还得塞一个“指向下一个节点的指针”，访问某个节点还得从头一个个摸过去，乍一看完全是“自找麻烦”。
直到后来自己动手写代码、被各种内存问题折磨过，才真正理解链表在解决什么问题。这篇文章是“链表”系列的第一篇，打算从头把链表的底层逻辑、基本操作、多语言实现、常见坑点全部梳理一遍。写给正在准备考研数据结构的人、期末复习数据结构的人、以及刚入门算法想弄清楚链表到底怎么回事的人。内容尽量用大白话讲清楚原理，再配合可以直接抄的代码和实验思路，让你看完就能上手自己写一遍。
1. 先搞懂链表到底在解决什么问题
在动手写代码之前，先把链表为什么存在这件事想明白。很多人学的第一个数据结构是数组，但数组有几个天生的短板，链表恰恰是为补上这些短板而出现的。
1.1 数组的甜与痛
数组的优点十分直观：内存连续、按下标随机访问是O(1)时间。缺点也藏在这一片连续内存里。第一，数组的长度在创建时就固定了，想动态扩展得手动申请一块更大的内存再拷贝数据。第二，在数组中间插入或删除一个元素，需要把后面的元素逐个往后挪或往前挪，最坏情况是O(n)的时间成本。
举一个“排队”的例子。假设有一排人按顺序站好，每人都站在固定的编号上，这就是数组。突然有人想插队到第3个人后面，后面所有人必须往后挪一步腾位置；突然中间有人走了，后面的人又得补齐空位。这个挪动过程就是O(n)的操作，人少还好，几百万条数据就非常难受了。
1.2 链式存储的核心思想
链表换个思路解决问题：不要求所有数据都在连续内存里，每个数据元素单独占据一个小块，这个小块就是“节点”。节点里分为两部分：数据域存放实际的数据，指针域存放“下一个节点在哪里”的地址。多个节点通过指针域串起来，就像一条铁链，所以叫链表。
生活化类比是“寻宝游戏”：你在第1张纸条上得到一条线索，线索告诉你第2张纸条藏在衣柜里；从衣柜里找到第2张纸条，上面又告诉你第3张纸条藏在抽屉里。你想拿到第5张纸条，必须从第1张开始一张张找下去，因为纸条之间只有单向线索，没有“跳跃”能力。这就是单链表。
1.3 头指针、头节点、尾节点，术语先分清
链表里有几个基本概念如果不搞清楚，后面写代码很容易懵：
- 头指针：指向链表第一个节点的指针变量，它本身不是节点，只是一个“入口地址”。链表操作基本都要从头指针开始。
- 头节点：也不是存储实际数据的节点，它是链表第一个节点之前附加的一个“哨兵节点”。带头节点的链表比不带头节点的链表在某些操作上更省心，尤其是插入和删除的位置正好在头部时。
- 尾节点：最后一个节点，它的指针域指向NULL，表示“后面没有了”。遍历链表的终止条件就是判断指针是否为NULL。
注意：很多教材和考试题会区分“带头节点”和“不带头节点”。不带头节点的空链表用头指针=NULL表示；带头节点的空链表是只有一个头节点，头节点的next为NULL。这两种模型写法有差异，考试踩坑概率极高，建议从一开始就选一种作为默认写法，我后面代码统一用带头节点的写法。
2. 链表家族：几个常见形态得认识全
很多同学学到链表，觉得只有一种“单链表”，其实链表是一个家族，不同形态对应不同场景。
2.1 单链表：最基础、没有回头路
单链表的每个节点只有一个next指针，指向后继节点。只能从头到尾单向遍历，想找前一个节点？没有存，只能重新从头走一遍。单链表的特点是结构最简单，面试笔试、考研数据结构里最常考的就是它，核心操作包括遍历、插入、删除、逆序、合并。
2.2 双向链表：多一个前驱指针
双向链表每个节点既有next指针也有prev指针，节点之间可以双向走动。代价是多一个指针域，每个节点多占用一个指针大小的内存，但“找前驱”从O(n)变成O(1)。实际工程中双向链表更常用，比如Java的LinkedList底层就是双向链表，LRU缓存算法也常用双向链表配合哈希表实现。
2.3 循环链表：尾尾相连绕一圈
循环链表把最后一个节点的next指针指向第一个节点，形成一个环。单循环链表和双向循环链表都存在。循环链表的好处是从任意位置出发都能遍历整条链表，而且尾节点和头节点之间是“打通”的。典型应用有约瑟夫环问题、操作系统的进程调度轮转队列等。
2.4 带头节点与不带头节点怎么选
我用一个对比表格把带头节点和不带头节点的差异列出来，备考的人可以直接背这个表：
| 对比维度 | 带头节点 | 不带头节点 |
|---|---|---|
| 空链表表示 | 头节点的next为NULL | 头指针为NULL |
| 在头部插入节点 | 不需要修改头指针，只需改头节点next | 需要修改头指针指向新节点 |
| 在头部删除节点 | 不需要修改头指针 | 需要修改头指针指向新节点 |
| 代码统一性 | 插入、删除逻辑统一，不用单独判断头部情况 | 头部操作必须特殊处理 |
| 考试/面试常见程度 | 王道、408真题出现比例很高 | 有些教材默认不带头节点 |
我的建议是初学阶段直接用带头节点的单链表练手，能省掉很多边界判空头疼问题。理解了带头节点的写法之后，再看不带头节点的写法，会发现只是头指针处理方式不同而已。
3. 单链表核心操作：建、查、插、删
这一节是整篇文章的核心，代码我统一用C语言写，原因很简单：考研数据结构、期末数据结构实验绝大多数学校默认C语言，而且C语言的指针能把链表的“地址跳转”表达得最直白。写完C版再对比Java/Python，你会发现思路完全一致，只是换了一层语法包装。
3.1 节点结构怎么定义
C语言里用结构体定义节点：
#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; // 数据域 struct Node *next; // 指针域，指向下一个节点 } Node; // 创建一个新节点 Node* createNode(int data) { Node* node = (Node*)malloc(sizeof(Node)); node->data = data; node->next = NULL; return node; }注意这里的写法：结构体内部要引用自身类型，所以必须写struct Node *next，不能省略struct关键字。最后用typedef ... Node把struct Node重命名成Node，这样后面写代码少几个字。
3.2 创建链表：头插法和尾插法
创建链表有两种最基础的插入策略，这也是考试常考的“头插法”和“尾插法”：
头插法：每次新节点都插入到头节点之后。特点是最终链表的节点顺序和输入顺序正好相反，可以用来实现链表逆序。
Node* createListByHead(int arr[], int n) { Node* head = createNode(0); // 头节点，不存数据 for (int i = 0; i < n; i++) { Node* newNode = createNode(arr[i]); newNode->next = head->next; // 新节点先指向原第一个节点 head->next = newNode; // 头节点指向新节点 } return head; }演示一下：输入1、2、3，最终链表从头到尾是3、2、1。因为每个新节点都被插到了头部，后插入的反而排前面。
尾插法：新节点插到链表末尾，需要维护一个尾指针tail，每插入一个节点就更新尾指针。最终节点顺序和输入顺序一致。
Node* createListByTail(int arr[], int n) { Node* head = createNode(0); Node* tail = head; // 刚开始尾指针指向头节点 for (int i = 0; i < n; i++) { Node* newNode = createNode(arr[i]); tail->next = newNode; // 尾节点的next指向新节点 tail = newNode; // 新节点成为新尾节点 } return head; }头插法有个很实用的小技巧：如果拿到一条不带头节点的单链表，想倒序一下，很多人会新建一条链表再用头插法重新插入一遍，空间复杂度O(n)。其实原地逆序法只需要三个指针就能完成，后面第4节会详细讲。
3.3 遍历链表：打印每个节点的数据
链表的遍历逻辑是所有操作的基础。代码很短，但考察点很细：
void printList(Node* head) { Node* p = head->next; // 跳过不存数据的头节点 while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); }这里有两个关键点。第一，遍历的起点：如果带头节点，必须从head->next开始，否则头节点的数据会被打印出来。第二，循环条件：用p != NULL时，最后一个节点被处理完以后p变成NULL才退出。如果你写的是p->next != NULL，那么最后一个节点不会进入循环体，等于漏处理一个节点。这个差异就是期末考试填空题和面试手写代码最爱挖的坑。
3.4 插入节点：核心原则是“先连后断”
单链表插入有三种情况：头节点后插入、中间插入、尾节点后插入。其实核心套路一模一样，我先给出通用代码：
// 在节点pos之后插入新节点newNode void insertAfter(Node* pos, Node* newNode) { newNode->next = pos->next; // 第一步：新节点先指向pos的后继 pos->next = newNode; // 第二步：pos的next指向新节点 }这个两行代码的fun顺序极其重要，很多人第一次写会写成：
pos->next = newNode; newNode->next = pos->next;那就有意思了：先让pos的next指向newNode，结果newNode->next = pos->next就等于newNode->next = newNode，自己指向自己，链表就断了。
记住口诀“先连后断”：先把新节点和后面的节点连上，再把前驱节点的指针改过来。这和生活中换链条是一个道理，你得先把新链环扣好再接上旧链环，不能先把旧链环卸下来再装新的，那样链条就散了。
3.5 删除节点：必须先找到前驱
单链表删除节点没有太聪明的办法，因为要知道被删节点的前驱是谁，才能把前驱的next指向被删节点的后继。但单链表节点没存前驱信息，所以只能从头遍历，找到待删除节点的前驱节点。删除节点的通用步骤：
- 从
head开始遍历，找到满足p->next == target的节点p，p就是要删除节点的前驱。 - 让
p->next = target->next，跳过target。 - 释放target节点的内存。
对应代码：
void deleteNode(Node* head, int value) { Node* p = head; while (p->next != NULL && p->next->data != value) { p = p->next; } if (p->next == NULL) { printf("没有找到值为%d的节点\n", value); return; } Node* target = p->next; p->next = target->next; // 跳过待删除节点 free(target); // 释放内存 }如果删除的是不带头节点的链表的第一个节点，情况就特殊了：必须直接修改头指针head = head->next。带头节点的写法能避免这种特殊分支判断，这也是我坚持带头节点写法的原因。
3.6 删除链表：释放全部节点防内存泄漏
很多同学创建了链表却忘了最后释放，C语言下后果就是内存泄漏。完整的释放函数是：
void destroyList(Node* head) { Node* p = head; while (p != NULL) { Node* next = p->next; // 先记下下一个节点 free(p); // 再释放当前节点 p = next; } }注意必须先保存p->next再free(p)，因为free之后当前节点的内存已经被回收，再访问p->next是非法读取。
4. 进阶操作：逆序、合并有序链表、快慢指针
掌握了基本操作以后，接着往下走，这部分是考研数据结构、算法面试里的高频考点，也是“链表1”里最能体现思维深度的内容。
4.1 单链表逆序：三指针迭代法
单链表逆序的基本思路是“原地反转箭头方向”。用三个指针：prev指向当前节点的前驱，current指向当前节点，next保存当前节点的后继。每走一步，就把current->next从后继改成前驱。
Node* reverseList(Node* head) { Node* prev = NULL; Node* current = head; while (current != NULL) { Node* next = current->next; // 先保存后继 current->next = prev; // 箭头反转 prev = current; // 前驱后移 current = next; // 当前节点后移 } return prev; // prev最终指向原链表的尾节点，也就是新链表头 }这个代码是对不带头节点链表操作的，如果传入的是带头节点链表，返回的是新的第一个真实节点，使用时要注意。我建议考试时直接画一个三个节点的小链表在纸上，手动模拟每轮循环中三个指针的变化，比背代码可靠得多。
逆序操作的时间复杂度O(n)，空间复杂度O(1)，不需要申请额外空间，这也是面试官爱考它的原因。
4.2 合并两个有序的单链表
“合并两个有序的单链表”也是高频考题，热度词列表里专门有它。两条链表都是升序排列，要求合并后依然有序。思路是双指针逐一比较，谁小接谁：
Node* mergeTwoLists(Node* head1, Node* head2) { Node dummy; // 栈上哨兵节点，避免处理头指针 Node* tail = &dummy; Node* p1 = head1; Node* p2 = head2; while (p1 != NULL && p2 != NULL) { if (p1->data <= p2->data) { tail->next = p1; p1 = p1->next; } else { tail->next = p2; p2 = p2->next; } tail = tail->next; } // 剩下没遍历完的部分直接接上 tail->next = (p1 != NULL) ? p1 : p2; return dummy.next; }合并的时间复杂度O(n+m)，空间复杂度O(1)，只用常数个指针就完成了。除了迭代法，也可以用递归，递归代码更短但理解门槛更高，面试时迭代法往往更稳妥。
4.3 快慢指针：找中间节点、倒数第k个节点
链表不能随机访问，想找中间节点如果“先数长度，再走一半”，需要两次遍历。快慢指针只需要一次：快指针每次走两步，慢指针每次走一步。快指针到末尾时，慢指针正好到中间。
找中间节点的代码：
Node* findMiddle(Node* head) { Node* slow = head; Node* fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }找倒数第k个节点同理：快指针先走k步，然后快慢指针一起走，快指针走到空时，慢指针就是倒数第k个节点。快慢指针在链表类算法题里的出镜率极高，值得好好掌握。
5. 多语言实现对比：C、C++、Java、Python
链表的思路是同一套，但不同语言写出来的代码风格差异很大。我把自己写过的各语言版本心得整理了一下，方便不同技术栈的人参考。
5.1 C语言：结构体+指针的经典组合
C语言里链表是最原汁原味的，因为指针就是地址，next指针直观地保存了下一个节点的地址，调试器里你能直接看到地址值。但C语言的问题是没有内存自动回收，创建节点的malloc和删除节点的free必须自己配对管理，漏一个free就是内存泄漏，多free一次就是非法操作。
5.2 C++：用new和delete管理，还能玩引用
C++写链表和C很像，节点通常用struct定义，但构造方式更简洁：
struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; Node* head = new Node(0); Node* newNode = new Node(42);区别在于C++可以用构造函数初始化节点，创建操作一行搞定。另外C++结构体默认访问权限是public，直接访问成员没问题。C++里链表还可以用std::list直接用现成容器，但在考研手写题里必须能手写实现。
5.3 Java：引用传递模拟指针
Java没有指针概念，但对象引用本质上就是一个“安全的指针”。Java写链表节点：
class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } }Java不用手动管理内存，new出来的节点没引用后由垃圾回收器自动处理。但这也意味着链表删除节点时，只需要断开引用，并不需要也不能手动释放内存。Java的LinkedList底层就是双向链表，面试题却常让你自己手写单向链表实现。
5.4 Python：最简洁，但底层是对象引用
Python写链表表面看最简单，因为不用写结构体和指针语法：
class Node: def __init__(self, data): self.data = data self.next = None但Python的每个变量都是对象引用，next保存的是“对下一个Node对象的引用”。Python里创建节点不需要手动分配/释放内存，语言层面全部代劳了，但代价是链表节点的内存开销比C大很多——每个Node对象都有完整对象头。
Python单链表逆序的写法很简洁：
def reverse_list(head): prev = None curr = head while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt return prev5.5 各语言对比速查表
| 语言 | 节点定义方式 | 内存管理 | 代码复杂度 | 适用场景 |
|---|---|---|---|---|
| C | struct + 指针 | malloc/free手动管理 | 高，但最贴近底层 | 考研笔试、嵌入式、操作系统内核 |
| C++ | struct + 指针/引用 | new/delete管理 | 中等 | 算法竞赛、工程开发 |
| Java | class + 对象引用 | 自动垃圾回收 | 中低 | 面试算法题、Java开发 |
| Python | class + 对象引用 | 自动垃圾回收 | 低 | 快速原型、学习概念 |
顺带提一句，网上经常有人把“Pandas里的DataFrame/Series”也叫“数据结构”，这和计算机里的“链表”完全是两回事。当时我看到有很多人在搜“pandas数据结构创建”，那是数据分析领域的DataFrame和Series，属于另一个方向的知识。学链表时如果混淆了这两类概念，思路会乱，这里说清楚。
6. 实战应用与避坑总结
学了链表，很多人第一反应是“这有什么用？”。其实链表在工程里无处不在，尤其在嵌入式领域和基础软件领域，是绕不开的核心技能。
6.1 嵌入式里链表怎么用
嵌入式系统中链表最常见的用途包括任务队列管理、按键扫描缓冲、内存池管理等。嵌入式链表和桌面程序的链表有个重要区别：不能频繁使用动态内存分配，因为嵌入式环境内存小、分配不稳定会引发系统风险。所以嵌入式里常常预先创建一个静态节点池，再手动管理节点分配和回收。
一个嵌入式链表代码示例的典型结构是：
typedef struct os_node { struct os_node *next; void *data; } os_node_t; os_node_t node_pool[64]; // 固定大小的节点池 os_node_t *free_list; // 空闲链表每次需要节点时从free_list取一个，用完还回去，而不是调用malloc/free。这种静态分配方式在实时系统中非常常见，时间成本可确定，内存碎片也可控。如果在项目里见过这种写法，就明白为什么链表绝不是“纸上谈兵”。
6.2 考研和期末复习链表的正确姿势
考研数据结构里链表是必考内容，408统考经常把链表操作和动态规划、排序结合出综合题。期末考试的实验报告也总少不了“单链表的基本操作实验”。结合我自己的备考经验，复习建议如下：
- 必须能徒手写：创建（头插法、尾插法）、遍历、插入、删除、逆序、合并有序链表，这六种操作应当形成肌肉记忆。
- 必须理解复杂度：单链表的查找、插入、删除在已知位置和未知位置时时间复杂度不同，这个细节考试很喜欢考。
- 必须会画图：遇到指针操作的题，先在草稿纸上画链表，标出prev、current、next，再看代码逻辑，效率远高于空想。
- 重视做题练手：洛谷B3631单向链表是很经典的练手题，能帮你把链表的插入、删除、查询操作落实到真实场景里。另外《大话数据结构》和《数据结构与算法分析:Java语言描述》这两本书也适合对照阅读，前者轻松入门，后者Java版适合代码级理解。
6.3 常见问题与排查技巧速查表
链表代码的调试往往是新手最头疼的部分。把常见的报错和问题整理成表，可以直接对照排查：
| 问题现象 | 可能原因 | 排查与修复 |
|---|---|---|
| 访问空指针导致程序崩溃 | 对NULL节点继续访问->data或->next | 遍历循环里加判空，删除节点后不要继续用旧指针 |
| 打印链表时死循环、程序卡死 | 链表成环，尾节点next没有置NULL | 检查创建和插入时新节点next是否初始化为NULL |
| 打印出来少一个节点 | 循环条件写成了p->next != NULL | 改为p != NULL |
| 插入后链表顺序乱了 | 插入两行代码顺序写反 | 先连新节点与后继，再改前驱next |
| 删除头节点后链表找不到 | 没有更新头指针 | 不带头节点的链表删除头部节点时必须head=head->next |
| 程序跑完内存没释放 | 创建链表后忘记调用销毁函数 | 写完创建代码马上写destroyList，养成配对习惯 |
| 释放内存后崩溃 | free后继续访问已释放节点 | 释放后立即把指针置为NULL，即“悬空指针”或“悬挂指针” |
6.4 调试链表的两个核心技巧
最后分享两个我实际调试链表时觉得最好用的方法。
第一个是“打印大法”。在关键步骤打印当前节点的地址和数据，比如遍历时打印p的值和p->data，插入后打印整条链表，能非常直观地看出指针指向是否出了问题。不要觉得打印低级，它在调试链表时效率真的高。
第二个是“画小样例”。想不清指针变化时，拿纸笔把3个节点的链表画出来，节点画成方框，指针画成箭头，一步一步模拟代码执行。我面试手撕链表题之前，也是先在草稿纸上画好图再写代码，错误率低很多。
链表这个主题想一次讲完内容太多，这篇以基础为主——从数组的痛点讲起，梳理了链表的核心定义、链表家族的主要形态、单链表的基本操作、逆序和合并等进阶操作，以及多语言实现差异和常见问题排查。掌握了这些，链表的基础才算真正打牢。
我个人实际操作中的体会是，学链表最大的障碍不是代码语法，而是“心里没有图”。只要脑子里始终有“节点方框加箭头”的画面，任何链表操作都不难。下一篇可以再深入聊一聊双向链表的实战、循环链表实现约瑟夫环、以及链表排序等内容，不过先把这篇里的代码亲手敲一遍，比看多少遍教程都管用。
