---

前言

在上一篇博客中，我们聊了最基础的数据结构——数组，它凭借连续内存的优势，实现了高效的随机访问，但也有着插入、删除效率低、长度固定（静态数组）的致命缺点。那么问题来了：如果我们需要频繁添加、删除数据（比如聊天记录、购物车商品），数组显然不够用，这时候该用什么数据结构呢？

答案就是今天的主角——「链表（Linked List）」。

链表和数组是数据结构初阶的“黄金搭档”，它们互补长短：数组擅长“查询”，链表擅长“删改”。很多新手刚接触链表时，会被“指针”“节点”这些概念吓住，但其实只要用生活中的例子类比，再配合简单的实操，就能轻松吃透它。

今天这篇博客，依旧延续“通俗解读+实操落地”的风格，从“是什么、底层逻辑、优缺点、适用场景，到Python实操练习”，一步步拆解链表的核心知识点，哪怕是零基础，也能彻底搞懂链表，学会在合适的场景中使用它。

---

一、先搞懂：链表到底是什么？

数组是“一排整齐的抽屉”，所有元素连续存储，靠下标定位；而链表，更像是「一串糖葫芦」—— 每个山楂都是一个“数据节点”，山楂之间靠竹签连接，不用整齐排列，只要能通过竹签找到下一个山楂，就可以串成一串。

官方定义很简洁：链表是由若干个“节点”组成的线性表，每个节点包含“数据域”（存储数据）和“指针域”（存储下一个节点的地址），节点之间通过指针连接，无需占用连续的内存空间。

我们用一个生活中的例子再强化理解：假设你有一串钥匙，每把钥匙上都刻着下一把钥匙的存放位置——你要找最后一把钥匙，不需要把所有钥匙都摆出来，只要从第一把钥匙开始，顺着刻的位置一步步找，就能找到目标。这里的“每把钥匙”就是链表的“节点”，“刻的位置”就是“指针域”，“钥匙串”就是整个链表。

举一个C/C++/Python中的简单类比（后续会写完整实操代码）：

C:

# 用结构体模拟链表节点（数据域存值，指针域存下一个节点的地址）
#include <stdio.h>
#include <stdlib.h>  // 用于malloc函数分配内存

// 定义链表节点结构体（C语言无类，用结构体实现节点）
typedef struct ListNode {
    int val;                // 数据域：存储具体数据（与Python版本val对应）
    struct ListNode* next;  // 指针域：存储下一个节点的地址（默认NULL，代表没有下一个节点）
} ListNode;

// 创建3个节点，串联成一个简单链表：1 → 2 → 3
int main() {
    // 1. 分配内存创建节点（C语言需手动为节点分配内存，替代Python的类实例化）
    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    
    // 2. 给每个节点的数据域赋值（对应Python中ListNode(1)的传参）
    node1->val = 1;
    node2->val = 2;
    node3->val = 3;
    
    // 3. 串联节点（修改指针指向，与Python中node1.next = node2逻辑一致）
    node1->next = node2;  // 节点1的指针指向节点2
    node2->next = node3;  // 节点2的指针指向节点3
    node3->next = NULL;   // 尾节点的指针置为NULL，明确无下一个节点
    
    // 可选：释放内存（避免内存泄漏，新手可先了解）
    free(node1);
    free(node2);
    free(node3);
    node1 = NULL;
    node2 = NULL;
    node3 = NULL;
    
    return 0;
}

C++:

# 用C++类模拟链表节点（替代C语言结构体，封装数据域和指针域）
#include <iostream>  // C++标准输出头文件，替代C语言stdio.h

// 定义链表节点类（C++用类实现，比结构体更具封装性，对应原C语言结构体功能）
class ListNode {
public:
    int val;                // 数据域：存储具体数据（与原C语言val对应）
    ListNode* next;         // 指针域：存储下一个节点的地址（默认NULL，代表无下一个节点）

    // 构造函数（替代C语言手动赋值，初始化节点，简化节点创建）
    ListNode(int x) : val(x), next(NULL) {}
};

// 创建3个节点，串联成一个简单链表：1 → 2 → 3
int main() {
    // 1. 用new创建节点（C++用new分配内存，替代C语言malloc，自动调用构造函数赋值）
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    
    // 2. 串联节点（修改指针指向，逻辑与原C语言、Python代码完全一致）
    node1->next = node2;  // 节点1的指针指向节点2
    node2->next = node3;  // 节点2的指针指向节点3
    node3->next = NULL;   // 尾节点的指针置为NULL，明确无下一个节点
    
    // 可选：释放内存（用delete替代C语言free，避免内存泄漏，新手可先了解）
    delete node1;
    delete node2;
    delete node3;
    node1 = NULL;
    node2 = NULL;
    node3 = NULL;
    
    return 0;
}

Python：

# 用类模拟链表节点（数据域存值，指针域存下一个节点）
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 数据域：存储具体数据
        self.next = next  # 指针域：存储下一个节点的地址（默认None，代表没有下一个节点）

# 创建3个节点，串联成一个简单链表：1 → 2 → 3
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node1.next = node2  # 节点1的指针指向节点2
node2.next = node3  # 节点2的指针指向节点3

这些段代码虽然简单，但已经包含了链表的核心：节点由“数据+指针”组成，通过指针串联，形成一个完整的链表。和数组不同，这三个节点在内存中可以是分散的，只要指针指向正确，就能找到所有节点。

---

二、底层逻辑：为什么链表删改效率这么高？

新手最关心的问题：同样是存数据，为什么链表的插入、删除比数组快？核心原因就在于「非连续存储」—— 链表不需要占用连续的内存空间，也不需要通过下标定位，删改数据时，只需要修改“指针的指向”，无需移动其他元素。

我们对比数组和链表的“插入操作”，一眼就能看懂差异：

• 数组插入：比如在数组[1,2,3,4]的中间插入5，需要把3、4往后移动一位，腾出位置给5，元素越多，移动的越多，效率越低（时间复杂度O(n)）；

• 链表插入：比如在链表1→2→3的中间插入5，只需要做两步：① 新建节点5；② 把节点1的指针从指向节点2，改成指向节点5，再把节点5的指针指向节点2，无需移动任何其他节点（时间复杂度O(1)）。

用一张通俗的图理解（文字描述替代）：

插入前：1 → 2 → 3

插入后：1 → 5 → 2 → 3

整个过程，只修改了两个指针的指向，和链表的长度无关——哪怕链表有10万个节点，插入一个新节点，也只需要修改两个指针，这就是链表删改效率高的底层逻辑。

同样，链表的删除操作也是如此：比如删除链表1→5→2→3中的节点5，只需要把节点1的指针，从指向节点5改成指向节点2，节点5就会被“遗弃”（后续由垃圾回收机制清理），同样无需移动其他节点。

这里要注意一个细节：链表的“查询效率低”。因为链表没有下标，要找某个节点，必须从“头节点”（第一个节点）开始，顺着指针一步步遍历，直到找到目标节点（时间复杂度O(n)）。比如要找链表1→2→3→4中的节点4，必须依次经过1、2、3，才能找到4——这也是链表的致命缺点，和数组的“随机访问”形成鲜明对比。

---

三、链表的核心分类（初阶必掌握）

链表有很多种分类，但初阶阶段，我们只需要掌握「3种最基础的链表」，后续复杂链表（比如红黑树的底层链表），都是基于这3种扩展的。

1. 单链表（最常用，重点掌握）

我们前面举的例子，都是单链表——每个节点只有一个指针域，只能指向“下一个节点”，不能反向遍历。就像一串糖葫芦，只能从第一个山楂，顺着竹签吃到最后一个，不能倒着吃。

核心特点：

• 结构最简单，实现成本最低，日常开发中最常用；

• 只能单向遍历（从头节点到尾节点），尾节点的指针域为NULL（没有下一个节点）；

• 插入、删除效率高（O(1)），查询效率低（O(n)）。

适用场景：大多数需要频繁删改、很少随机查询的简单场景（比如简单的任务队列）。

2. 双链表

双链表解决了单链表“不能反向遍历”的问题——每个节点有两个指针域，一个指向“下一个节点”，一个指向“上一个节点”。就像一条双向车道，既能往前走，也能往回走。

核心特点：

• 可以双向遍历，查询某个节点的前驱节点（上一个节点）时，效率更高（O(1)）；

• 结构比单链表复杂，每个节点需要额外存储一个指针，内存开销略大；

• 删改效率依旧很高（O(1)），查询效率还是O(n)（整体遍历依旧需要逐个查找）。

适用场景：需要双向遍历的场景（比如浏览器的前进后退功能、双向队列）。

3. 循环链表

循环链表的特点是「尾节点的指针域，不指向None，而是指向头节点」，形成一个闭环。就像一个环形跑道，没有起点和终点，顺着指针能一直循环遍历。

核心特点：

• 可以循环遍历，适合需要“循环访问所有节点”的场景；

• 结构简单，基于单链表或双链表就能实现（单链表循环、双链表循环）；

• 注意避免“死循环”（遍历时分清终止条件）。

适用场景：循环队列、约瑟夫环问题等需要循环访问的场景（初阶阶段了解即可）。

---

四、链表的优缺点：和数组对比，一目了然

链表和数组是初阶数据结构的“互补搭档”，单独说优缺点没有意义，结合数组对比，才能更清晰地知道什么时候该用链表、什么时候该用数组。

1. 链表的核心优点

• 插入、删除效率极高：无需移动元素，只修改指针指向，时间复杂度O(1)（初阶重点关注单链表的表头/表尾删改，中间删改需先遍历找到节点，整体还是O(n)，但核心删改操作本身是O(1)）；

• 动态扩容，无需固定长度：链表的节点可以动态创建，只要有内存，就能一直添加节点，无需像静态数组那样提前定义长度，也不会出现内存溢出或浪费的情况；

• 内存利用率高：无需占用连续的内存空间，零散的内存碎片也能被利用（数组需要连续内存，哪怕有足够的总内存，但没有连续的空间，也无法创建数组）。

2. 链表的明显缺点

• 查询效率低：没有下标，无法随机访问，只能从头节点依次遍历，元素越多，查询越慢，时间复杂度O(n)；

• 内存开销略大：每个节点除了存储数据，还需要额外存储指针（单链表一个指针，双链表两个指针），相比数组，多了一部分内存开销；

• 实现复杂：相比数组，链表需要手动定义节点、管理指针指向，容易出现“空指针”“野指针”“死循环”等问题，新手入门难度略高。

补充：数组 vs 链表（初阶核心对比表）

对比维度	数组	链表（单链表）
存储方式	连续内存	非连续内存（节点+指针）
查询效率	高（O(1)，随机访问）	低（O(n)，只能遍历）
插入/删除效率	低（O(n)，需移动元素）	高（O(1)，仅修改指针）
长度特性	静态数组固定，动态数组自动扩容	动态扩容，无需固定长度
内存开销	小（仅存储数据）	大（数据+指针）

---

五、链表的适用场景：什么时候该用链表？

结合链表的优缺点和与数组的对比，链表的适用场景核心原则是：数据量不固定、需要频繁插入/删除、很少随机查询。

举几个日常开发和学习中的常见场景：

1. 频繁删改的线性数据：比如聊天记录（随时发送消息、删除消息，不需要随机查询某条消息的位置，只要按顺序查看）、购物车商品（添加、删除商品频繁，查询时按顺序浏览即可）；

2. 动态扩容需求强烈的场景：比如日志记录（日志数量不确定，会不断新增，不需要频繁查询历史日志）、任务队列（随时添加任务、执行任务（删除），无需固定队列长度）；

3. 内存碎片化严重的场景：比如嵌入式开发（内存空间有限，碎片化严重，无法分配连续内存给数组，链表的非连续存储特性更适配）；

4. 复杂数据结构的基础：比如栈、队列的底层实现（可以用链表实现，解决数组长度固定的问题）、哈希表的冲突解决（链地址法）、树和图的底层连接（节点之间的关联的本质是链表指针）。

反例：如果需要频繁随机查询（比如排行榜，经常查询第n名的分数），就不适合用链表，应该选择数组。

---

六、新手必避的5个链表坑

链表的入门难度比数组略高，新手很容易在“指针”“节点”上踩坑，总结了5个最常见的坑，避开这些，你的链表学习会更顺畅，写代码时也能减少报错。

1. 空指针异常（最常见）：访问了“空节点”的指针域或数据域。比如链表的尾节点next是NULL，你却试图访问tail->next->val，就会报错（C++中会触发空指针访问错误）；解决方法：操作指针前，先判断节点是否为NULL。

2. 忘记修改指针指向：插入、删除节点时，只修改了一个指针，导致链表“断裂”。比如插入节点时，只改了前一个节点的next，没改新节点的next，就会导致后续节点丢失。

3. 混淆单链表和双链表的遍历逻辑：单链表只能单向遍历（从头到尾），双链表可以双向遍历，但新手容易在双链表中写错指针指向（比如把prev写成next）。

4. 遍历链表时死循环：循环链表中，没有设置正确的终止条件；或者修改指针时，不小心让某个节点的next指向了前面的节点（比如让尾节点next指向头节点，遍历时分不清终止条件）。

5. 误以为链表所有删改都是O(1)效率：只有“已知前驱节点”的删改，效率才是O(1)；如果需要先遍历找到目标节点（比如删除链表中间某个指定值的节点），整体效率还是O(n)——因为遍历占了主要时间。

---

七、新手实操：3个C/C++/Python单链表练习（附完整代码）

学链表，光看概念和理论没用，必须动手写代码——实操一遍，比背10遍指针逻辑都管用。下面3个练习，从简单到复杂，覆盖单链表的核心操作（遍历、插入、删除），新手可以直接复制代码运行，跟着理解每一步的逻辑。

提示：

C语言中没有原生的链表结构，我们用「结构体」模拟节点，手动管理指针指向和内存分配（malloc分配、free释放），贴合初阶学习的核心（理解节点和指针）。

C++/Python中没有原生的链表结构，我们用「类」模拟节点，手动管理指针指向和内存分配，贴合初阶学习的核心（理解节点和指针）。

练习1：单链表遍历（打印所有节点的值）

核心逻辑：从头节点开始，顺着next指针，逐个访问节点，打印数据，直到节点为NULL/None（尾节点之后）。

C:

# 1. 定义链表节点结构体（C语言无类，用结构体模拟节点，替代Python的类）
#include <stdio.h>
#include <stdlib.h>  // 用于malloc分配内存、free释放内存

// 链表节点结构体：包含数据域和指针域，与Python的ListNode类功能一致
typedef struct ListNode {
    int val;                // 数据域：存储具体数据（对应Python中的self.val）
    struct ListNode* next;  // 指针域：存储下一个节点的地址（对应Python中的self.next）
} ListNode;

// 2. 定义单链表遍历函数（对应Python的traverse_linkedlist函数）
void traverse_linkedlist(ListNode* head) {
    ListNode* current = head;  // 从头部节点开始遍历（对应Python中的current = head）
    // 终止条件：当前节点为空（遍历到尾节点之后），C语言用!=NULL替代Python的is not None
    while (current != NULL) {
        // C语言用printf输出，替代Python的print，保持输出格式一致
        printf("%d → ", current->val);  // 指针操作需用->，替代Python的.
        current = current->next;        // 移动到下一个节点，指针赋值
    }
    printf("NULL\n");  // 打印尾节点之后的空指针，更直观，与原输出格式一致
}

// 3. 测试代码（创建链表+遍历，与Python测试场景完全一致，确保功能可验证）
int main() {
    // 创建节点，串联成链表：1 → 2 → 3 → 4（C语言需用malloc手动分配内存）
    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
    
    // 给每个节点的数据域赋值（对应Python中ListNode(1)的传参初始化）
    node1->val = 1;
    node2->val = 2;
    node3->val = 3;
    node4->val = 4;
    
    // 串联节点（修改指针指向，对应Python中的node1.next = node2）
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = NULL;  // 尾节点指针置为NULL，明确无下一个节点
    
    // 调用遍历函数，输出：1 → 2 → 3 → 4 → NULL（与原Python代码输出一致）
    traverse_linkedlist(node1);
    
    // 释放内存，避免内存泄漏（C语言关键步骤，Python自动垃圾回收，无需手动操作）
    free(node1);
    free(node2);
    free(node3);
    free(node4);
    // 置空指针，避免野指针（C语言安全规范，新手需重点注意）
    node1 = NULL;
    node2 = NULL;
    node3 = NULL;
    node4 = NULL;
    
    return 0;
}

C++：

# 1. 复用链表节点类（与前文示例一致）
#include <iostream>
using namespace std;

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 2. 定义单链表遍历函数
void traverse_linkedlist(ListNode* head) {
    ListNode* current = head;  // 从头部节点开始遍历
    while (current != NULL) {  // 终止条件：当前节点为空（遍历到尾节点之后）
        cout << current->val << " → ";  // 打印当前节点的值，C++用cout输出
        current = current->next;  // 移动到下一个节点
    }
    cout << "NULL" << endl;  // 打印尾节点之后的空指针，更直观
}

// 3. 测试代码（创建链表+遍历）
int main() {
    // 创建节点，串联成链表：1 → 2 → 3 → 4（用new创建节点，调用构造函数赋值）
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = NULL;
    
    // 调用遍历函数，输出：1 → 2 → 3 → 4 → NULL
    traverse_linkedlist(node1);
    
    // 释放内存，避免内存泄漏（C++需手动释放new分配的内存）
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    node1 = NULL;
    node2 = NULL;
    node3 = NULL;
    node4 = NULL;
    
    return 0;
}

Python:

# 1. 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 数据域
        self.next = next  # 指针域

# 2. 定义单链表遍历函数
def traverse_linkedlist(head):
    current = head  # 从头部节点开始遍历
    while current is not None:  # 终止条件：当前节点为空（遍历到尾节点之后）
        print(current.val, end=" → ")  # 打印当前节点的值
        current = current.next  # 移动到下一个节点
    print("None")  # 打印尾节点之后的空指针，更直观

# 3. 测试代码（创建链表+遍历）
if __name__ == "__main__":
    # 创建节点，串联成链表：1 → 2 → 3 → 4
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    
    # 调用遍历函数，输出：1 → 2 → 3 → 4 → None
    traverse_linkedlist(node1)

练习2：单链表插入（在指定下标插入节点）

核心逻辑：找到插入位置的前驱节点（上一个节点），修改前驱节点的next指向新节点，新节点的next指向原前驱节点的下一个节点；注意处理“插入到表头”“插入到表尾”“下标越界”三种特殊情况。

C：

# 1. 复用链表节点结构体（和练习1一致，C语言用结构体模拟节点）
#include <stdio.h>
#include <stdlib.h>  // 用于malloc分配内存、free释放内存

// 链表节点结构体：与练习1完全一致，可直接复用
typedef struct ListNode {
    int val;                // 数据域：存储具体数据
    struct ListNode* next;  // 指针域：存储下一个节点的地址
} ListNode;

// 2. 单链表插入函数（在指定下标index插入值为val的节点）
// 返回值为ListNode*，用于处理插入表头后头节点变化的情况
ListNode* insert_node(ListNode* head, int index, int val) {
    // 特殊情况1：插入到表头（index=0），新节点成为新的头节点
    // C语言用malloc手动分配节点内存，替代C++的new
    ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
    if (new_node == NULL) {  // 额外增加内存分配失败判断，C语言安全规范
        printf("内存分配失败，插入失败\n");
        return head;
    }
    new_node->val = val;     // 给新节点数据域赋值，替代C++构造函数
    new_node->next = NULL;   // 初始化新节点指针域为NULL，避免野指针

    if (index == 0) {
        new_node->next = head;  // 新节点的next指向原头节点，与原逻辑一致
        return new_node;        // 返回新的头节点，更新链表头部
    }
    
    // 找到插入位置的前驱节点（index-1位置的节点）
    ListNode* current = head;   // 当前遍历节点，从表头开始
    ListNode* prev = NULL;      // 前驱节点，初始为空（指向当前节点的上一个节点）
    int count = 0;              // 记录当前遍历到的下标，用于定位插入位置
    
    // 遍历找到index-1位置的节点，同时判断下标是否越界
    while (current != NULL && count < index) {
        prev = current;         // 先记录当前节点为前驱节点
        current = current->next;// 移动到下一个节点，指针操作需用->
        count++;                // 下标计数自增
    }
    
    // 特殊情况2：下标越界（count < index，说明遍历到尾节点仍未到指定下标）
    if (count < index) {
        printf("下标越界，插入失败\n");  // C语言用printf输出，替代C++的cout
        free(new_node);         // 释放未使用的新节点，避免内存泄漏
        new_node = NULL;        // 置空指针，避免野指针
        return head;            // 插入失败，返回原头节点，链表不变
    }
    
    // 正常插入：修改指针指向，完成节点插入（核心逻辑与原代码一致）
    prev->next = new_node;     // 前驱节点的next指向新节点
    new_node->next = current;  // 新节点的next指向原前驱节点的下一个节点
    return head;                // 表头未变，返回原头节点
}

// 3. 测试代码（与原测试场景一致，确保功能可验证，适配C语言语法）
int main() {
    // 原链表：1 → 2 → 3 → 4，用malloc创建节点并串联（替代C++的new）
    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
    
    // 给每个节点赋值，初始化指针域，替代C++构造函数
    node1->val = 1;
    node1->next = node2;
    node2->val = 2;
    node2->next = node3;
    node3->val = 3;
    node3->next = node4;
    node4->val = 4;
    node4->next = NULL;  // 尾节点指针置为NULL，明确无下一个节点
    
    // 在index=2插入值为5的节点，插入后：1 → 2 → 5 → 3 → 4
    ListNode* new_head = insert_node(node1, 2, 5);
    
    // 遍历验证（复用练习1的遍历逻辑，简化实现，便于快速验证结果）
    void traverse(ListNode* head) {
        ListNode* current = head;
        while (current != NULL) {
            printf("%d → ", current->val);
            current = current->next;
        }
        printf("NULL\n");
    }
    traverse(new_head);  // 调用遍历函数，打印插入后的链表
    
    // 释放内存，避免内存泄漏（C语言关键步骤，逐节点释放）
    ListNode* temp;
    current = new_head;  // 从新头节点开始释放
    while (current != NULL) {
        temp = current;          // 先保存当前节点
        current = current->next; // 移动到下一个节点
        free(temp);              // 释放当前节点内存，替代C++的delete
        temp = NULL;             // 置空临时指针，避免野指针
    }
    new_head = NULL;  // 置空头指针，避免野指针
    
    return 0;
}

C++:

# 1. 复用节点类（和练习1一致，C++用类模拟链表节点，封装数据域和指针域）
#include <iostream>
using namespace std;

// 链表节点类（与练习1完全一致，可直接复用）
class ListNode {
public:
    int val;                // 数据域：存储具体数据
    ListNode* next;         // 指针域：存储下一个节点的地址
    // 构造函数：初始化节点，替代Python中__init__方法
    ListNode(int x) : val(x), next(NULL) {}
};

// 2. 单链表插入函数（在指定下标index插入值为val的节点）
// 返回值为ListNode*，用于处理插入表头后头节点变化的情况
ListNode* insert_node(ListNode* head, int index, int val) {
    // 特殊情况1：插入到表头（index=0），新节点成为新的头节点
    ListNode* new_node = new ListNode(val);  // C++用new创建节点，自动调用构造函数
    if (index == 0) {
        new_node->next = head;  // 新节点的next指向原头节点，与Python逻辑一致
        return new_node;        // 返回新的头节点，更新链表头部
    }
    
    // 找到插入位置的前驱节点（index-1位置的节点）
    ListNode* current = head;   // 当前遍历节点，从表头开始
    ListNode* prev = NULL;      // 前驱节点，初始为空（指向当前节点的上一个节点）
    int count = 0;              // 记录当前遍历到的下标，用于定位插入位置
    
    // 遍历找到index-1位置的节点，同时判断下标是否越界
    // C++中判断节点非空用!=NULL，替代Python中的is not None
    while (current != NULL && count < index) {
        prev = current;         // 先记录当前节点为前驱节点
        current = current->next;// 移动到下一个节点，指针操作需用->
        count++;                // 下标计数自增
    }
    
    // 特殊情况2：下标越界（count < index，说明遍历到尾节点仍未到指定下标）
    if (count < index) {
        cout << "下标越界，插入失败" << endl;  // C++用cout输出，替代Python的print
        delete new_node;        // 释放未使用的新节点，避免内存泄漏（C++需手动管理内存）
        return head;            // 插入失败，返回原头节点，链表不变
    }
    
    // 正常插入：修改指针指向，完成节点插入（核心逻辑与Python一致）
    prev->next = new_node;     // 前驱节点的next指向新节点
    new_node->next = current;  // 新节点的next指向原前驱节点的下一个节点
    return head;                // 表头未变，返回原头节点
}

// 3. 测试代码（与Python测试场景一致，确保功能可验证）
int main() {
    // 原链表：1 → 2 → 3 → 4，用new创建节点并串联
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = NULL;  // 尾节点指针置为NULL，明确无下一个节点
    
    // 在index=2插入值为5的节点，插入后：1 → 2 → 5 → 3 → 4
    ListNode* new_head = insert_node(node1, 2, 5);
    
    // 遍历验证（复用练习1的遍历逻辑，简化实现，便于快速验证结果）
    void traverse(ListNode* head) {
        ListNode* current = head;
        while (current != NULL) {
            cout << current->val << " → ";
            current = current->next;
        }
        cout << "NULL" << endl;
    }
    traverse(new_head);  // 调用遍历函数，打印插入后的链表
    
    // 释放内存，避免内存泄漏（C++关键步骤，新手需重点注意）
    ListNode* temp;
    current = new_head;  // 从新头节点开始释放
    while (current != NULL) {
        temp = current;          // 先保存当前节点
        current = current->next; // 移动到下一个节点
        delete temp;             // 释放当前节点内存
    }
    new_head = NULL;  // 置空指针，避免野指针
    temp = NULL;      // 置空临时指针
    
    return 0;
}

Python:

# 1. 复用节点类（和练习1一致）
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 2. 单链表插入函数（在指定下标index插入值为val的节点）
def insert_node(head, index, val):
    # 特殊情况1：插入到表头（index=0），新节点成为新的头节点
    new_node = ListNode(val)
    if index == 0:
        new_node.next = head  # 新节点的next指向原头节点
        return new_node  # 返回新的头节点
    
    # 找到插入位置的前驱节点（index-1位置的节点）
    current = head
    prev = None  # 前驱节点，初始为空
    count = 0    # 记录当前遍历到的下标
    
    # 遍历找到index-1位置的节点，同时判断下标是否越界
    while current is not None and count < index:
        prev = current
        current = current.next
        count += 1
    
    # 特殊情况2：下标越界（count < index，说明遍历到尾节点仍未到指定下标）
    if count < index:
        print("下标越界，插入失败")
        return head
    
    # 正常插入：修改指针指向
    prev.next = new_node  # 前驱节点的next指向新节点
    new_node.next = current  # 新节点的next指向原前驱节点的下一个节点
    return head  # 返回原头节点（表头未变）

# 3. 测试代码
if __name__ == "__main__":
    # 原链表：1 → 2 → 3 → 4
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    
    # 在index=2插入值为5的节点，插入后：1 → 2 → 5 → 3 → 4
    new_head = insert_node(node1, 2, 5)
    # 遍历验证
    def traverse(head):
        current = head
        while current:
            print(current.val, end=" → ")
            current = current.next
        print("None")
    traverse(new_head)

练习3：单链表删除（删除指定下标的节点）

核心逻辑：找到删除节点的前驱节点，将前驱节点的next指向删除节点的下一个节点，手动释放删除节点的内存（避免内存泄漏）；同样需要处理“删除表头”“删除表尾”“下标越界”三种特殊情况。

C:

# 1. 复用链表节点结构体（和练习1、2一致，C语言用结构体模拟节点）
#include <stdio.h>
#include <stdlib.h>  // 用于malloc分配内存、free释放内存

// 链表节点结构体：与练习1、2完全一致，可直接复用
typedef struct ListNode {
    int val;                // 数据域：存储具体数据
    struct ListNode* next;  // 指针域：存储下一个节点的地址
} ListNode;

// 2. 单链表删除函数（删除指定下标index的节点）
// 返回值为ListNode*，用于处理删除表头后头节点变化的情况
ListNode* delete_node(ListNode* head, int index) {
    // 特殊情况1：链表为空，无法删除
    if (head == NULL) {
        printf("链表为空，删除失败\n");  // C语言用printf输出，替代Python的print
        return NULL;
    }
    
    // 特殊情况2：删除表头（index=0），新头节点为原头节点的next
    if (index == 0) {
        ListNode* temp = head;  // 保存原头节点，用于后续释放内存（C语言关键步骤）
        ListNode* new_head = head->next;  // 新头节点指向原头节点的下一个节点
        free(temp);             // 释放原头节点内存，避免内存泄漏（替代Python自动垃圾回收）
        temp = NULL;            // 置空指针，避免野指针（C语言安全规范）
        return new_head;        // 返回新的头节点，更新链表头部
    }
    
    // 找到删除节点的前驱节点（index-1位置的节点）
    ListNode* current = head;   // 当前遍历节点，从表头开始
    ListNode* prev = NULL;      // 前驱节点，初始为空（指向当前节点的上一个节点）
    int count = 0;              // 记录当前遍历到的下标，用于定位删除节点
    
    // 遍历找到index-1位置的节点，同时判断下标是否越界
    // C语言用!=NULL替代Python的is not None，指针操作需用->
    while (current != NULL && count < index) {
        prev = current;         // 先记录当前节点为前驱节点
        current = current->next;// 移动到下一个节点
        count++;                // 下标计数自增
    }
    
    // 特殊情况3：下标越界（current为空，说明没有该下标对应的节点）
    if (current == NULL) {
        printf("下标越界，删除失败\n");  // C语言用printf输出，替代Python的print
        return head;            // 删除失败，返回原头节点，链表不变
    }
    
    // 正常删除：修改前驱节点的指针，跳过删除节点（核心逻辑与原代码一致）
    prev->next = current->next;  // 前驱节点的next指向删除节点的下一个节点
    free(current);               // 释放删除节点内存，避免内存泄漏（C语言关键步骤）
    current = NULL;              // 置空指针，避免野指针
    return head;                 // 表头未变，返回原头节点
}

// 3. 测试代码（与原Python测试场景完全一致，适配C语言语法，可直接运行）
int main() {
    // 原链表：1 → 2 → 5 → 3 → 4（复用练习2插入后的链表）
    // C语言用malloc手动分配节点内存，替代Python的类实例化
    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
    
    // 给每个节点赋值，初始化指针域，替代Python的ListNode传参
    node1->val = 1;
    node1->next = node2;
    node2->val = 2;
    node2->next = node5;
    node5->val = 5;
    node5->next = node3;
    node3->val = 3;
    node3->next = node4;
    node4->val = 4;
    node4->next = NULL;  // 尾节点指针置为NULL，明确无下一个节点
    
    // 删除index=2的节点（值为5），删除后：1 → 2 → 3 → 4
    ListNode* new_head = delete_node(node1, 2);
    
    // 遍历验证（复用练习1、2的遍历逻辑，简化实现，便于快速验证结果）
    void traverse(ListNode* head) {
        ListNode* current = head;
        while (current != NULL) {
            printf("%d → ", current->val);
            current = current->next;
        }
        printf("NULL\n");
    }
    traverse(new_head);  // 调用遍历函数，打印删除后的链表
    
    // 释放内存，避免内存泄漏（C语言关键步骤，逐节点释放，替代Python自动回收）
    ListNode* temp;
    current = new_head;  // 从新头节点开始释放
    while (current != NULL) {
        temp = current;          // 先保存当前节点
        current = current->next; // 移动到下一个节点
        free(temp);              // 释放当前节点内存
        temp = NULL;             // 置空临时指针，避免野指针
    }
    new_head = NULL;  // 置空头指针，避免野指针
    
    return 0;
}

C++:

# 1. 复用节点类（和练习1一致）
#include <iostream>
using namespace std;

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 2. 单链表插入函数（在指定下标index插入值为val的节点）
ListNode* insert_node(ListNode* head, int index, int val) {
    // 特殊情况1：插入到表头（index=0），新节点成为新的头节点
    ListNode* new_node = new ListNode(val);  // 用new创建新节点
    if (index == 0) {
        new_node->next = head;  // 新节点的next指向原头节点
        return new_node;  // 返回新的头节点
    }
    
    // 找到插入位置的前驱节点（index-1位置的节点）
    ListNode* current = head;
    ListNode* prev = NULL;  // 前驱节点，初始为空
    int count = 0;          // 记录当前遍历到的下标
    
    // 遍历找到index-1位置的节点，同时判断下标是否越界
    while (current != NULL && count < index) {
        prev = current;
        current = current->next;
        count++;
    }
    
    // 特殊情况2：下标越界（count < index，说明遍历到尾节点仍未到指定下标）
    if (count < index) {
        cout << "下标越界，插入失败" << endl;  // C++用cout输出
        delete new_node;  // 释放未使用的新节点，避免内存泄漏
        return head;
    }
    
    // 正常插入：修改指针指向
    prev->next = new_node;  // 前驱节点的next指向新节点
    new_node->next = current;  // 新节点的next指向原前驱节点的下一个节点
    return head;  // 返回原头节点（表头未变）
}

// 3. 测试代码
int main() {
    // 原链表：1 → 2 → 3 → 4
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = NULL;
    
    // 在index=2插入值为5的节点，插入后：1 → 2 → 5 → 3 → 4
    ListNode* new_head = insert_node(node1, 2, 5);
    // 遍历验证（复用遍历函数）
    void traverse(ListNode* head) {
        ListNode* current = head;
        while (current != NULL) {
            cout << current->val << " → ";
            current = current->next;
        }
        cout << "NULL" << endl;
    }
    traverse(new_head);
    
    // 释放内存
    ListNode* temp;
    current = new_head;
    while (current != NULL) {
        temp = current;
        current = current->next;
        delete temp;
    }
    new_head = NULL;
    temp = NULL;
    
    return 0;
}

Python:

# 1. 复用节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 2. 单链表删除函数（删除指定下标index的节点）
def delete_node(head, index):
    # 特殊情况1：链表为空，无法删除
    if head is None:
        print("链表为空，删除失败")
        return None
    
    # 特殊情况2：删除表头（index=0），新头节点为原头节点的next
    if index == 0:
        new_head = head.next
        return new_head
    
    # 找到删除节点的前驱节点（index-1位置的节点）
    current = head
    prev = None
    count = 0
    
    while current is not None and count < index:
        prev = current
        current = current.next
        count += 1
    
    # 特殊情况3：下标越界（current为空，说明没有该下标对应的节点）
    if current is None:
        print("下标越界，删除失败")
        return head
    
    # 正常删除：修改前驱节点的指针，跳过删除节点
    prev.next = current.next
    return head  # 返回原头节点（表头未变）

# 3. 测试代码
if __name__ == "__main__":
    # 原链表：1 → 2 → 5 → 3 → 4（复用练习2插入后的链表）
    node1 = ListNode(1)
    node2 = ListNode(2)
    node5 = ListNode(5)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node1.next = node2
    node2.next = node5
    node5.next = node3
    node3.next = node4
    
    # 删除index=2的节点（值为5），删除后：1 → 2 → 3 → 4
    new_head = delete_node(node1, 2)
    # 遍历验证
    def traverse(head):
        current = head
        while current:
            print(current.val, end=" → ")
            current = current.next
        print("None")
    traverse(new_head)

---

八、新手学习建议（附链表+数组学习路线）

链表的核心不是“指针”，而是“灵活”——它打破了数组连续存储的限制，用指针串联起零散的节点，解决了数组删改效率低的问题。初阶阶段，不用追求“精通所有链表类型”，只要吃透单链表的核心操作、分清它和数组的适用场景，就是胜利。

数组和链表，是数据结构的“入门基石”，后续我们会聊栈、队列、哈希表等进阶结构，而这些结构，本质上都是基于数组和链表扩展的——把基础吃透，后续的学习会轻松很多。

如果这篇博客对你有帮助，欢迎点赞收藏～ 也可以在评论区留言，说说你学习链表时遇到的困惑（比如指针总是写错、容易出现空指针），我们一起交流、一起进步！