困难通用7 分钟2,567 字

链表的概念与实现

链表:像手拉手接龙一样灵活的数据结构

想象一下,课间活动时,小朋友们一个接一个拉着前面同学的衣服,连成一列长长的“火车”。第一个小朋友没有拉任何人,最后一个小朋友后面没有人。如果你想加入一个新小朋友,只需要让他拉住前一个小朋友的衣服,再让后面小朋友拉住他——完全不需要所有人都重新排队。这和数组的“搬动整个储物柜”相比,是不是方便多了?

在计算机里,这种结构就叫 链表(Linked List)​ 。它是一群 节点(Node)​ 手拉手串起来的序列。每个节点有两个“口袋”:一个装自己的数据,另一个装一个 指针​​,指向下一个节点。最后一个节点的指针指向“空”(NULL 或 None),表示后面没人了。

链表的示意图(单向链表):

     Head
       |
       v
    +------+      +------+      +------+
    | 10   |      | 20   |      | 30   |
    | next |---->| next |---->| next |----> NULL
    +------+      +------+      +------+

头指针 指向第一个节点,就像整列火车的“车头”,通过它我们能访问整条链。

为什么叫“链表”?——比数组“自由”在哪?

对比项 数组 链表
存储方式 内存中连续一块 节点分散在各处,靠指针连接
大小固定 创建时定死,扩容麻烦 动态增长,随时插入新节点
随机访问 直接通过下标取,O(1) 必须从头一个一个找,O(n)
插入/删除(已知位置) 需要移动后面所有元素,O(n) 只改相邻指针,O(1)
额外内存 几乎没有 每个节点多一个指针(双向链表两个)

生活的例子​​:如果你想在课间操队形中间加一个人,

  • 用数组:所有人后退一步,空出位置 → 大家都要动。
  • 用链表:让新同学拉住前面同学,后面的同学再拉住新同学 → 只动三个人。

链表的“骨骼”:节点和指针

每个节点像一块乐高积木,有两个部分:

  • data​​:存放实际数据,可以是数字、文字、甚至一个对象。
  • next​​:存放指向下一个节点的“箭头”(指针)。

在代码中,我们会先定义节点结构(C++ 用 struct 或 class,Python 用 class)。

生活中的比喻​​:节点就像火车车厢,data 是车厢里装的货物,next 是连接下一节车厢的挂钩。挂钩只能指向下一节,不能往回指(单向链表)。

链表的三种常见“队形”

  • 单向链表​​:每个节点只有指向下一个的指针。查找只能从头到尾。
  • 双向链表​​:每个节点有两个指针,一个指向前一个,一个指向后一个。可以双向查找,但每个节点多占一个指针空间。
  • 循环链表​​:最后一个节点的 next 指向第一个节点,形成一个环。常用来实现“轮询”任务。

本文重点讲最基础的 单向链表​​。

链表的“体操”:基本操作详解

1. 创建链表——从空集开始

一开始,链表是空的——头指针指向 NULL。我们要往里面加节点。

2. 插入节点——学会三个位置

头部插入:​ 新节点变成新的头,它的 next 指向原来的头。

尾部插入:​ 需要先找到最后一个节点(它的 next 是 NULL),然后让最后一个节点的 next 指向新节点。

中间插入:​ 比如要在节点B和C之间插入新节点X,需要先找到B,然后让 X 的 next 指向 C,再让 B 的 next 指向 X。​​顺序很重要!​ 如果先改了 B 的 next,就找不到 C 了。

3. 删除节点——断开“挂钩”

删除头部:​ 直接把头指针指向第二个节点,再释放原来的头节点。

删除中间或尾部:​ 需要找到要删除节点的​前一个节点​,让它跳过要删除的节点,直接指向后一个节点。然后释放被删除的节点(C++ 中手动 delete,Python 自动回收)。

4. 遍历与查找——一步一步走

从 head 开始,用一个指针 cur 依次指向每个节点,直到 cur 为 NULL。查找某个值也是同样的方式,一边走一边比较。

新手常犯的“坑”

  1. 忘记更新指针导致链表断裂 比如在中间插入时,如果先改了前一个节点的 next,后面的节点就找不到了。正确顺序:先设置新节点的 next 指向后一个节点,再改前一个节点的 next。
  2. 头指针丢失 如果在插入或删除头部时,没有正确更新 head,整个链表就丢了。比如在 Python 中插入头部要返回新 head,否则外面还是旧的 head。
  3. 空指针访问 比如遍历到最后一个节点后,你还想访问 cur->next,但 cur 是 NULL,程序会崩溃。务必先判断是否为 NULL。
  4. 内存泄漏(C++)​ 用 new 创建的节点,不再使用时必须 delete。否则程序运行久了,内存越占越多。
  5. 死循环 如果某个节点的 next 不小心指向了前面节点,遍历时会永远跑不完。检查代码,确保不会形成意外的环。

完整可运行的代码示例

下面用 C++ 和 Python 分别实现完整的链表操作,包含所有主要功能,代码中每行变量定义都有中文注释。

C++ 完整代码

cpp
#include <iostream>
using namespace std;

// 定义节点结构体
struct Node {
    int data;   // 数据域,存放数值(比如考试成绩:95分)
    Node* next; // 指针域,指向下一个节点(像挂钩)

    // 构造函数,方便创建节点时赋初值
    Node(int val) : data(val), next(nullptr) {}
};

// 打印链表:从头开始输出每个节点的值
void printList(Node* head) {
    Node* cur = head;  // cur 是当前遍历到的节点指针
    while (cur != nullptr) {
        cout << cur->data << " -> ";
        cur = cur->next;
    }
    cout << "nullptr" << endl;
}

// 在链表头部插入新节点(新同学插到第一个位置)
void insertAtHead(Node* &head, int val) {
    Node* newNode = new Node(val);  // 新建一个节点,数据为 val
    newNode->next = head;           // 新节点的 next 指向原来的头
    head = newNode;                 // 头指针更新为新节点
}

// 在链表尾部插入新节点(新同学站到队伍最后)
void insertAtTail(Node* &head, int val) {
    Node* newNode = new Node(val);  // 新建节点
    if (head == nullptr) {          // 如果链表是空的
        head = newNode;             // 新节点就是头节点
        return;
    }
    Node* cur = head;               // 从头开始找最后一个节点
    while (cur->next != nullptr) {  // 只要还有下一个节点就继续
        cur = cur->next;
    }
    cur->next = newNode;            // 最后一个节点的 next 指向新节点
}

// 删除链表中第一个值等于 val 的节点
void deleteValue(Node* &head, int val) {
    if (head == nullptr) return;    // 空链表,没东西可删

    if (head->data == val) {        // 要删除的是头节点
        Node* temp = head;          // 暂存旧头节点地址
        head = head->next;          // 头指针后移
        delete temp;                // 释放旧头节点内存
        return;
    }

    // 找要删除节点的前一个节点
    Node* cur = head;               // cur 从头开始
    while (cur->next != nullptr && cur->next->data != val) {
        cur = cur->next;            // 一直走到要删除节点的前一个
    }
    if (cur->next != nullptr) {     // 说明找到了那个节点
        Node* toDelete = cur->next; // toDelete 指向要删除的节点
        cur->next = cur->next->next;// 前一个节点跳过被删节点,连到后一个
        delete toDelete;            // 释放被删节点内存
    }
    // 如果没找到,什么也不做
}

// 释放整个链表(防止内存泄漏)
void deleteList(Node* head) {
    Node* cur = head;
    while (cur != nullptr) {
        Node* temp = cur;
        cur = cur->next;
        delete temp;
    }
}

int main() {
    Node* head = nullptr;  // 一开始是空链表,头指针指向空

    // 插入几个节点:10, 20, 30 依次加到尾部
    insertAtTail(head, 10);
    insertAtTail(head, 20);
    insertAtTail(head, 30);
    // 在头部插入 5
    insertAtHead(head, 5);

    cout << "链表:";
    printList(head);  // 输出:5 -> 10 -> 20 -> 30 -> nullptr

    // 删除值为 20 的节点
    deleteValue(head, 20);
    cout << "删除20后:";
    printList(head);  // 输出:5 -> 10 -> 30 -> nullptr

    // 程序结束前释放所有节点,养成良好的习惯
    deleteList(head);
    head = nullptr;
    return 0;
}

Python 完整代码

python
# 定义节点类
class Node:
    def __init__(self, data):
        self.data = data      # 数据域,比如存放零食数量:5包
        self.next = None      # 指针域,初始化为空

# 打印链表
def print_list(head):
    cur = head                # cur 指向当前节点
    while cur:                # 只要不是 None 就继续
        print(cur.data, end=" -> ")
        cur = cur.next        # 移动到下一个节点
    print("None")

# 头部插入(新同学站第一个)
def insert_at_head(head, val):
    new_node = Node(val)      # 创建一个新节点
    new_node.next = head      # 新节点指向原来的头
    return new_node           # 返回新头节点(注意:原 head 已变)

# 尾部插入(新同学站最后)
def insert_at_tail(head, val):
    new_node = Node(val)      # 创建新节点
    if head is None:          # 如果链表为空
        return new_node       # 新节点就是头节点
    cur = head
    while cur.next:           # 走到最后一个节点
        cur = cur.next
    cur.next = new_node       # 最后一个节点指向新节点
    return head               # 头节点没变,返回原头

# 删除第一个值为 val 的节点
def delete_value(head, val):
    if head is None:          # 空链表直接返回
        return None
    if head.data == val:      # 如果要删的是头节点
        return head.next      # 新头就是原头的下一个
    cur = head
    # 找到要删节点的前一个节点
    while cur.next and cur.next.data != val:
        cur = cur.next
    if cur.next:              # 找到了
        cur.next = cur.next.next  # 跳过要删的节点
    return head               # 头节点没变,返回原头

# 测试
head = None
head = insert_at_tail(head, 10)
head = insert_at_tail(head, 20)
head = insert_at_tail(head, 30)
head = insert_at_head(head, 5)

print("链表:", end="")
print_list(head)  # 5 -> 10 -> 20 -> 30 -> None

head = delete_value(head, 20)
print("删除20后:", end="")
print_list(head)  # 5 -> 10 -> 30 -> None

Python 中,每个变量都是对象的引用,“指针”实际上就是引用。不需要手动释放内存,Python 的垃圾回收会自动处理。但注意,函数返回新头节点时,外部一定要用返回值更新 head。

链表在生活中的应用

  • 音乐播放列表​​:上一曲、下一曲很自然用双向链表实现。
  • 浏览器前进/后退​​:浏览记录可以用链表(或双向链表)实现。
  • 操作系统的任务调度​​:使用循环链表实现时间片轮转。
  • 游戏中的组合技​​:例如格斗游戏中的“连招”序列,可以用链表存储一连串动作。
  • 在线排队系统​​:新人加入队伍末尾(尾部插入),排到的人离开(头部删除)。

总结要点

  • 链表由节点组成,节点包含数据和一个(或多个)指针。
  • 插入和删除节点只需要修改指针,时间复杂度 O(1)(已知位置的前提下)。
  • 随机访问必须从头遍历,时间复杂度 O(n)。
  • 链表克服了数组大小固定和插入删除效率低的缺点,但牺牲了快速访问的能力。
  • 每个节点多存储一个指针,内存开销比数组大。
  • 编程时要小心指针操作:避免丢失节点、形成死循环、内存泄漏。

链表是很多高级数据结构(如栈、队列、图)的基础。学会了链表,你就能自己动手实现更多有意思的结构啦!

接下来可以学习什么?​

  • 动态数组(ArrayList / vector):它结合了数组的快速访问和链表的灵活扩展。
  • 双向链表:可以向前向后走,操作更灵活。
  • 循环链表:特别适合做“轮播”或“循环队列”。
  • 栈和队列:可以用链表轻松实现。

加油,你的数据结构和算法之路会越走越宽!

同类知识点