单链表详解：从数组痛点、核心操作到性能实测

1. 从一个线上事故说起：数组用得好好的，为什么要换链表

大概几个月前，我们团队负责的一个数据处理服务在高峰期突然崩溃，查日志发现是某个模块在写入一组动态增长的数据时，发生了越界访问。当时用的就是最常见的动态数组，业务代码里不断往数组末尾追加数据，靠语言自带的内存管理自动扩容，看上去没有任何问题。但在那次事故里，扩容触发的多次内存拷贝和指针失效，加上多线程并发读取，直接导致了一个隐蔽的野指针。事后排查花了整整两天，本质原因只有一个：我们用数组去解决一个并不适合数组的问题——频繁在中间插入、删除，还要动态增长。

这不是说数组不好，而是提醒我们，数据结构选型如果只凭“习惯”而不是“场景”，迟早要还债。也是在那个阶段，我开始认真地重新梳理链表这种最基础、也最容易被低估的数据结构。

链表的核心价值其实很朴素：数据不要求连续存放，每个节点单独分配内存，通过指针把前后节点串起来。这样插入和删除不需要搬移大量元素，只需要修改相邻节点的指针。听起来很简单，但真正动手实现时，你会遇到指针悬空、头节点缺失、内存泄漏等一系列问题。这篇博文就围绕单链表展开，先用数组的痛点说明为什么需要链表，再逐步拆解节点的定义、头节点的设计、遍历插入删除等核心操作，最后结合性能实测和调试经验，帮你把链表的底子打扎实。

2. 数组的痛点与链表的破局：连续内存带来的“刚性”

2.1 固定大小数组的硬伤：容量不够了怎么办

如果你写过一段时间代码，一定见过这样的定义：

c复制int arr[100];
int count = 0;

然后往里面塞数据，塞着塞着就超过了100。最常见也最莽撞的做法是把100改成10000，但问题并没有消失，只是推迟了。更麻烦的是，固定大小数组一旦定义，内存就固定了，无论你用了1个还是100个元素，都占着那么大块地方。对于嵌入式环境或内存敏感的系统，这种浪费很粗暴。

也有人说，那我用动态数组，像很多高级语言里的可变长数组。确实，动态数组在你的语言层面看起来可以无限增长，但底层逻辑仍然是：当容量不够时，重新申请一块更大的连续内存，把旧数据逐个拷贝过去，再释放旧内存。每次扩容都是O(n)的搬移成本，而且搬移之后，所有之前指向数组内部元素的指针都可能失效，因为内存地址变了。

2.2 中间插入和删除：数组的“搬砖”成本

真正让我下定决心改用链表的场景，是需要在序列的中间频繁插入和删除。假设用数组维护一个按优先级排序的任务列表，每次新任务到达时，要插到对应位置。数组插入操作在逻辑上很简单：

c复制for (int i = size; i > pos; i--) {
    arr[i] = arr[i - 1];
}
arr[pos] = new_element;
size++;

这段代码把从pos开始的所有元素都向后挪一格。如果列表长度是10万，而插入位置在第5个，你得搬移99995个元素。删除操作同理，向前搬移。这种操作在数组里是无解的，因为你必须维护“连续”这个契约。

而链表怎么处理？链表的每个节点在内存中完全独立，只要用指针把前后节点连起来，那么“插入”就是先创建一个新节点，再把新节点的前驱指针和后继指针分别指向相应节点，最后让原来的前驱节点的next指向新节点。整个过程只改动两个指针，时间复杂度O(1)。这个本质差异，是链表存在的最大理由。

2.3 链表的代价：多存一个指针，多了一些不确定性

当然，天下没有免费的午餐。链表用额外的指针字段换来了插入删除的灵活性。每个节点除了存储数据，还要存指向下一个节点的地址。这意味着同样的数据量，链表在内存占用上天然比数组多出一个指针空间。更关键的是，链表的节点分散在内存各处，无法像数组那样利用CPU缓存预读，遍历性能往往比数组差。所以链表的适用场景很明确：插入删除频繁、数据规模动态变化大、不需要频繁随机访问下标。如果你的需求是高频遍历、按下标快速访问，数组依然更合适。

3. 单链表的核心结构：搞清楚节点和指针，就成功了一半

3.1 节点的定义：数据域和指针域

在C语言里，一个最简单的单链表节点可以这样定义：

c复制typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

这里的data保存实际值，next保存下一个节点的地址。你可能会问，为什么next必须是指向struct ListNode的指针，而不能直接存一个ListNode结构体？因为结构体里如果直接包含另一个结构体，就会变成无限递归嵌套，编译器根本没办法确定大小。而指针的大小是固定的，所以用指针来引用下一个节点，这是链表能够“链”起来的根本。

注意，这里的data用了int，实际项目中完全可以是任意类型，比如一个指向业务对象的指针。如果你用的是Java、Python这类带引用类型和垃圾回收的语言，其实底层也是类似思路，只不过指针被包装成了“引用”，内存管理由虚拟机代劳，但原理没什么区别。

3.2 头节点 vs 头指针：这个细节搞不清，后面代码全是坑

创建链表时，首先要区分两个概念：头指针和头节点。头指针是一个指向第一个节点的指针变量，它本身不存储业务数据，只用来定位链表的起点。而头节点是一个额外的、不存数据的节点，它位于真正的首节点之前。很多教材和项目里会刻意创建一个带头节点的链表。

为什么要有头节点？想象一下，如果链表为空，头指针就指向NULL，此时你要在头部插入一个新节点，需要修改头指针的值。而如果不带头节点，你只能通过传入“指向头指针的指针”来实现。这个细节让很多初学者崩溃：

c复制// 不带头节点，在头部插入节点，必须传二级指针
void insertHead(ListNode **head, int val) {
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = val;
    newNode->next = *head;
    *head = newNode;
}

如果只是传一级指针ListNode *head，在函数内部修改head，返回后依然指向原来的地址，因为参数是值传递。而如果使用一个固定的头节点，那么无论链表是否为空，头节点始终存在，所有插入删除操作都只需要通过头节点的next来调整，就不用动头节点本身。这样代码会更统一，边界条件也少很多。

3.3 尾节点的判定：最后一个节点的next必须指向NULL

单链表的结构决定了它必须有一个终点。最后一个节点的next如果不置为NULL，遍历就无法终止，会直接越界访问内存，轻则读到脏数据，重则段错误。所以创建节点之后，务必养成习惯：新节点初始化时next = NULL。然后当你把一个节点挂在链表尾部时，也要确保原尾节点的next指向这个新节点，而新节点的next保持NULL。

我在初期写代码时，经常忘记给新节点初始化next，结果遍历到尾节点时，next里面是随机值，循环直接跑到非法地址。排查了很久才发现是malloc出来的内存没有清零导致的。所以强烈建议，节点创建函数里，一开始就把data和next都赋值：

c复制ListNode* createNode(int val) {
    ListNode *node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL) {
        // 处理内存分配失败
        return NULL;
    }
    node->data = val;
    node->next = NULL;
    return node;
}

每次malloc之后都要检查是否为NULL，这在内存较小的环境下尤其重要。

4. 手写单链表：从初始化到反转，六个核心操作一次讲透

4.1 初始化带头节点的链表：让代码统一起来

我建议初学者使用带头节点的写法，省心。初始化函数如下：

c复制typedef struct LinkedList {
    ListNode *head; // 头节点，不存数据
    int length;
} LinkedList;

void initList(LinkedList *list) {
    list->head = (ListNode*)malloc(sizeof(ListNode));
    if (list->head == NULL) {
        list->length = 0;
        return;
    }
    list->head->data = 0;       // 头节点数据无所谓
    list->head->next = NULL;    // 空链表
    list->length = 0;
}

这里额外加了一个length字段，用处很大。调试时你可以随时比对预期长度和实际节点数量，防止插入删除逻辑出错。另外，如果要统计链表长度，有了这个字段就是O(1)操作，而不是每次遍历O(n)。

4.2 头插法与尾插法：构建链表最常用的两种方式

头插法：把新节点插到头节点之后，也就是新节点变成第一个有效节点。代码很简洁：

c复制void insertAtHead(LinkedList *list, int val) {
    ListNode *newNode = createNode(val);
    if (newNode == NULL) return;
    newNode->next = list->head->next;
    list->head->next = newNode;
    list->length++;
}

注意顺序：先把新节点的next指向当前第一个节点，再把头节点的next指向新节点。如果先改头节点的next，就会丢失原链表的起点。这个顺序错误，是我见过最频繁的链表写错原因之一。

尾插法：需要先遍历到链表的最后一个节点，然后让最后一个节点的next指向新节点。如果没有length或尾指针，时间复杂度是O(n)。如果经常需要尾插，可以额外维护一个尾指针，让插入复杂度降为O(1)。

c复制void insertAtTail(LinkedList *list, int val) {
    ListNode *newNode = createNode(val);
    if (newNode == NULL) return;
    ListNode *cur = list->head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
    list->length++;
}

头插法和尾插法构造出的链表顺序是相反的。如果你用头插法依次插入1,2,3，最终链表顺序是3,2,1。这一点在处理输入数据时很关键，很多新手精心构造的测试数据，最后遍历出来顺序不对，其实就是头插的锅。

4.3 遍历与查找：单链表的“单向奔赴”

遍历链表很简单，从head->next开始，只要cur不为NULL，就处理data，然后cur = cur->next。查找某个值的第一个位置，逻辑一样：

c复制ListNode* findNode(LinkedList *list, int val) {
    ListNode *cur = list->head->next;
    while (cur != NULL) {
        if (cur->data == val) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

单链表只能从前往后走，所以按下标访问一个元素，也必须从头开始计数，时间复杂度O(n)。数组是O(1)，这是数组最大的优势之一。如果你需要频繁按下标随机访问，就别用单链表。

4.4 删除指定节点：前驱节点是灵魂

删除一个节点，核心问题是找到它的前驱节点。因为你要让前驱的next指向被删节点的next，才能把被删节点从链中摘除。如果删除的是第一个有效节点，它的前驱是头节点。以下是按值删除第一个匹配节点：

c复制int deleteByValue(LinkedList *list, int val) {
    ListNode *prev = list->head;
    ListNode *cur = list->head->next;
    while (cur != NULL) {
        if (cur->data == val) {
            prev->next = cur->next;
            free(cur);
            list->length--;
            return 1;
        }
        prev = cur;
        cur = cur->next;
    }
    return 0; // 没找到
}

这里prev永远指向cur的前一个节点。初始化时prev在头节点，cur在第一个有效节点。找到后，直接让prev->next = cur->next，再释放cur。这个过程中，千万注意不要提前释放cur，否则cur->next就访问不到了。最好先保存next指针，再free。

还有一种很常见的面试题变体：不给你头节点，只给你指向某个节点的指针，要求删除它。这题很多老手也容易犯错。如果这个节点不是尾节点，解法是把后一个节点的数据拷贝到当前节点，然后让当前节点的next指向后下一个节点，再释放后一个节点。实际上“狸猫换太子”，并没有真正删除当前节点，而是删除了它的后继。如果删除的是尾节点，就必须从头遍历找前驱了。这说明链表的操作灵活，但边界条件非常多。

4.5 反转单链表：指针改向的经典演练

反转链表是链表题里最基础的入门级，也是检验你对指针操作熟练度的尺子。迭代法思路很直白：三个指针，pre指向前一个节点，cur指向当前节点，nex保存cur的下一个节点。每一步让cur->next指向pre，然后整体右移。

c复制void reverseList(LinkedList *list) {
    if (list->head->next == NULL) return;
    ListNode *pre = NULL;
    ListNode *cur = list->head->next;
    ListNode *nex = NULL;
    while (cur != NULL) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    list->head->next = pre;
}

注意最后要更新头节点的next为原来的尾节点。反转之后，原来链表的尾节点成了第一个有效节点，所以它就是新的链头。画图理解最直观：每次循环，把当前节点的箭头指向左边，然后三个指针整体向右移动。等cur为空时，pre正好停在新的链头。

这里还要提醒一下，反转不会改变节点的数据，只改变next指向。如果节点里还有其他字段，比如业务ID，都不受影响。

4.6 内存释放：链表不会自己消失

动态分配的节点如果不用了，必须释放。而且因为节点是一路靠next串起来的，释放时也要一步步来。一个常见的错误是：

c复制// 错误示范
while (cur != NULL) {
    free(cur);      // cur释放后，cur->next已经不可访问
    cur = cur->next;
}

正确做法是保存next再free：

c复制void clearList(LinkedList *list) {
    ListNode *cur = list->head->next;
    while (cur != NULL) {
        ListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    list->head->next = NULL;
    list->length = 0;
    free(list->head);
    list->head = NULL;
}

用C语言写链表，内存泄漏和野指针是最大的敌人。每次malloc都要对应一次free，每次free之后都要避免再次访问那块内存。如果在Java或Go里，垃圾回收器会帮我们省掉很多事，但理解内存生命周期依然重要。

5. 实测对比：链表和数组在常见场景下的性能差距到底有多大

5.1 测试设计：数据量、操作类型、运行环境

为了不空谈理论，我专门做了一个简单的基准测试。环境是普通的开发机，语言用C，编译器默认优化级别。测试数据是10万个整数。分别测三个场景：依次尾插、在头部插入、按下标随机访问。数组和链表各跑一遍，取多次平均。

5.2 头部插入：链表完胜，数组拉了跨

数组在头部插入，需要把后面的所有元素都往后移一到一位，10万个元素意味着每次插入都要搬移约10万个数据。插入1万次，总搬移量达到上亿级别。链表在头部插入只需要修改两个指针，不管链表多长，时间都是常数级。实测结果如下：

尾插数组有优势，因为它是连续内存，直接写尾部即可；链表如果没有尾指针，每次要遍历到尾节点，消耗O(n)。这也解释了为什么有些链表实现会额外维护尾指针。

5.3 随机访问：数组的绝对领域

随机访问按下标取元素，数组是直接用地址偏移计算，CPU一条指令就完成了。链表需要从头一个个跳，10万次随机访问差异已经很明显，如果数据量变成百万级，差距还会放大几个数量级。所以在需要大量随机访问的场景，用链表就是自找麻烦。

5.4 缓存命中率：一个容易被忽略的隐性差距

现代CPU读取内存时，会把相邻地址的数据一次性加载到缓存行。数组的元素连续存放，遍历时可以最大限度地利用缓存预读，所以即使同样是遍历，数组往往比链表快得多。链表节点可能分散在各处，导致每次访问都可能发生缓存未命中，那种“跑起来明显卡顿”很多时候就是从这里来的。这也是为什么很多高性能场景宁可用动态数组+标记数组来模拟删除，也不愿意用链表。

但实际业务中，如果你的核心操作是大量中间插入删除，而且数据规模很大，链表的优势会盖过缓存劣势。选择数据结构，从来不是比谁的理论复杂度更漂亮，而是比谁在你实际的访问模式下更适配。

6. 调试链表的通用思路：断点、画图、边界检查，一个不能少

6.1 空指针与野指针：崩溃的最常见根源

初学者写完链表程序，最常见的崩溃就是空指针。比如遍历时没判断cur是否为NULL，直接访问cur->data。还有一种更隐蔽的野指针：节点被free之后，另一个指针仍然指向它，再次访问就是随机内存，可能当时能跑，也可能偶尔崩溃，非常难查。解决办法很笨但有效：每次操作后，检查链表能否完整从头遍历到尾；释放内存之后，立刻把指针置NULL。

c复制free(cur);
cur = NULL; // 避免悬空

6.2 画图大法：纸上推演插入删除的每一步

链表调试不像数组那样直观，但它的逻辑其实非常适合画图。我强烈建议，在纸上画几个方块代表节点，方块里写数据，箭头代表next指针。然后模拟插入、删除、反转的每一步，最后再对照代码看。你会发现很多“想当然”的错误，比如忘记更新前驱的next，或者反转时丢失了链表头，都能在画图时被直观暴露出来。这也是我每次教新人时必推的方法——别急着敲代码，先画图。

6.3 边界条件检查表：空链表、单节点、头尾节点

链表操作最容易出错的永远是边界条件。我给自己定了一张检查清单，每次写完一个操作，都逐项套一遍：

• 链表为空时，操作是否还能正常运行？
• 链表只有一个节点时，插入、删除、反转是否正常？
• 操作的是头节点、尾节点，还是中间节点？
• 删除最后一个节点之后，链表是否能回到空状态？
• 反转后头节点是否正确更新？

有了这张清单，很多隐藏的bug在提交前就被拦下了。理论上，链表只要处理好NULL和头尾边界，剩下的就是循环逻辑细节。

6.4 防御性打印：定位问题时的临时辅助函数

遇到复杂链表问题，我经常临时写一个打印函数，把每个节点的地址和data都打出来，再打印每个节点的next地址。这样能直接看出链表在哪一步断开了，或者是否存在两个节点指向同一个next。等确认没问题再把打印去掉。尤其在排查两个链表是否交叉、是否有环时，打印地址往往比单看数据更有效。

7. 从单链表到后续扩展：这只是链表的起点

7.1 循环链表：解决“回到起点”的问题

单链表的尾节点next为NULL，所以走到尽头就停了。如果让尾节点的next指向头节点，就变成了循环链表。在实际业务中，循环链表很适合实现循环队列、轮询调度的任务列表。约瑟夫环这样的经典算法，用循环链表非常优雅。作为练习，你可以自己把上一节的单链表改成循环链表，注意区分空表、头节点和尾节点的判定条件。

7.2 双向链表：多一个指针，少一些等待

双向链表的每个节点额外带一个prev指针，可以反向遍历。这使得删除给定节点时，不需要从头找前驱，直接通过prev就能找到。代价是每个节点多一个指针，内存开销更大，且插入删除时修改的指针数量翻倍。在标准库里，很多有序容器底层的实现都用了双向链表，就是因为需要频繁在节点间前后来回移动。

7.3 跳表：让链表也能“跳”着找

如果觉得链表查找O(n)太慢，还有一个有意思的扩展——跳表。它是在链表节点上增加多层索引，让高层节点跳过若干底层节点，从而把查找复杂度降低到O(log n)。跳表实现起来比平衡树简单，很多内存数据库用它做有序集合的索引。理解了单链表的指针操作之后，再看跳表会容易很多，因为你已经熟练掌握了多层指针的指向关系。

7.4 学完链表，你真正收获了什么

学习链表，表面上是掌握一种数据结构，实际上是训练自己理解“通过指针或引用操作内存”。数组思维是把内存当作一个连续的大抽屉，链表思维则是把内存当作一个个独立的小盒子，用线串起来。这种思维转换，会让你以后理解树、图、哈希表时更快，因为它们本质上也都是“节点+指针”的变体。

眼下这篇算是链表的第一篇，重点在单链表。你把它吃透了，后面不管是循环链表、双向链表还是跳表，都会觉得顺理成章。我个人的体会是，链表代码写得越多，就越觉得“把细节处理好”比“背下算法步骤”重要得多。单链表看着简单，但能一次通过的人真不多，愿你写的时候也像我一样，多画图、多检查边界、多思考为什么。