链式表示

真题练习

链表的基础操作（插入、删除等）是线性表学习的核心，也常用于算法设计题中的结点操作。

单链表定义

线性表的 链式表示 通常指的是使用 链表 来实现线性表。链表 是由一系列 结点 组成的，每个 结点 都包含一个 数据元素 和一个指向下一个 结点 的 指针。这种结构允许我们 动态地插入 和 删除元素，而不需要移动其他元素。

本页代码采用动态分配方式创建单链表结点，即使用 C 语言的 malloc() 或 C++ 的 new。这类动态申请的空间通常来自 进程的堆，各结点的地址不要求连续，如下图所示。链式存储的本质要求是由链接域表达逻辑次序，并不是所有链表实现都必须采用同一种内存分配方式。

由于堆的这种 动态内存分配 特性，单链表 具备如下优点：

• 链表大小可以动态变化：链表的 结点 是在需要时 动态分配 的，因此在使用过程中不需要提前分配固定大小的存储空间，可以随时 插入 或 删除 结点。
• 插入和删除方便：已知目标位置的前驱结点时，可以在 $O(1)$ 时间内插入或删除后继结点；若需要先按逻辑位置查找前驱，整体仍为 $O(n)$。顺序表在对应位置操作时可能需要移动大量元素。
• 无需预估数据大小：链表可以灵活地增长，而顺序表需要预先定义一个固定大小，或者使用 动态数组 实现，但重新分配和拷贝的开销可能会很大。

数组（顺序表）与链表不同，其相邻元素必须 连续 存储。若数组作为函数局部变量定义，例如 int a[N]，它通常位于 进程的栈；动态数组也可以位于堆区，但连续存储这一结构特征不变。

由于数组在内存中的存储是 连续 的，这有利于程序的 空间局部性，当访问一个元素时，相邻的元素也会被加载到 CPU 缓存 中，这提高了访问速度。 此外，通过数组的起始地址和一个偏移，我们可以快速地定位到某个数组元素在内存中的地址，实现 随机访问。

相比而言，链表 则不具备以上特性，链表 的缺点如下：

• 随机访问较慢：链表不支持直接通过索引随机访问，必须从头部开始逐个遍历结点，直到找到所需结点，所以按位置访问需要 $O(n)$ 时间。
• 空间开销较大：除了 数据元素 的存储外，每个 结点 还需要额外的空间存储一个 指针，这增加了 链表 的存储开销。

基本操作

链表 的基本操作需要熟练掌握，并且能够手写代码。

数据结构定义

可以使用如下结构体来描述 单链表 中的 结点：

// 链表定义
typedef struct Node {
    int data;
    struct Node *next;
} Node;

其中结构体中包含两个元素，一个是 数据，另一个 指向下一个结点的指针。 通过这种方式，链表 可以在内存中以非连续的方式存储数据，每个 结点 通过 指针 连接起来。

在这个例子中，data 的类型是 int，意味着这个 链表 用于存储整数。但是，你可以根据需要更改 data 的类型，例如 float、char 或者自定义的结构体类型，以存储不同类型的数据。

next 指针的作用是 连接链表中的各个结点。它存储了下一个结点的内存地址。通过 next 指针，我们可以从一个结点访问到下一个结点，从而遍历整个链表。

初始化链表

在 初始化 链表时我们需要为其创建一个 头结点，并将 头结点 的 next 设置为空。

// 初始化
Node* init_linkedlist() {
    Node *head = (Node *)malloc(sizeof(Node));  // 创建头结点
    if (head == NULL) exit(1);  // 内存分配失败
    head->next = NULL;  // 初始为空链表
    return head;
}

头结点 的目的在于 简化空链表的处理 和 统一链表的操作：

• 引入 头结点 后，即使链表为空，头指针 也始终指向 头结点。
• 通过引入 头结点，可以使链表的第一个 结点（实际数据 结点）的操作与其他 结点 的操作保持一致。

判空

如果 头指针 的 next 为空的话，说明 单链表 为空：

bool is_empty(Node *head) {
    return head->next == NULL;
}

插入

对于在 链表 的一个 结点 p 之后插入一个新 结点 n 可以抽象如下操作：

插入已有结点

void insert_node_after(Node *p, Node *n) {
    Node *q = p->next;
    n->next = q;
    p->next = n;
}

插入一个值

void insert_value_after(Node *n, int value) {
    Node *p = malloc(sizeof(Node));
    p->data = value;
    Node *q = n->next;
    n->next = p;
    p->next = q;
}

当然，如果我们想插入一个实际值 value 的话，你需要通过 Node *p = malloc(sizeof(Node)); p->data = value; 来创建一个新 结点，然后再将新创建的 结点 通过以上函数插入。

在实际考察 插入 操作的过程中，可能会涉及到三种情况：在 链表 头部插入、在 链表 尾部插入 或 在任意位置插入。

头部插入

void insert_after_head(Node *head, int value) {
    // 调用上文定义的插入函数
    insert_value_after(head, value);
}

尾部插入

void insert_after_tail(Node *head, int value) {
    // 找到链表的尾部结点
    Node *tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    // 在该位置插入
    insert_value_after(tail, value);
}

按逻辑位置插入

// 在链表的下标 pos 处插入（从 0 开始计数），返回值 bool 表示插入是否成功
bool insert_at_pos(Node *head, int pos, int value) {
    if (pos < 0) return false;
    Node *p = head;
    int i = 0;
    // 找到插入位置的前驱；pos == 0 时前驱就是头结点
    while (p && i < pos) {
        p = p->next;
        i++;
    }
    if (!p) return false;

    insert_value_after(p, value);
    return true;
}

删除

假设指针 p 指向 链表 中的某个 结点，如果我们想删除 p 的下一个 结点 的话，可以通过如下代码：

void delete_node_after(Node *p) {
    Node *q = p->next;
    // 需要判断 q 是否存在
    if (q) {
        // 设置 p 的下一个结点跳过 q
        p->next = q->next;
        // 释放 q 的空间
        free(q);
    }
}

如果我们想删除 单链表 中的第 pos 个 结点 的话，可以通过如下代码：

// 返回 true 表示删除成功，返回 false 表示删除失败。
bool delete(Node *head, int pos) {
    if (pos < 0) return false;
    Node *p = head;
    int i = 0;
    while (p->next && i < pos) {  // 找到下标为 pos 的数据结点的前驱
        p = p->next;
        i++;
    }
    // p->next 不存在说明下标 pos 越界
    if (!p->next) return false;

    // 删除下一个结点
    Node *q = p->next;
    p->next = q->next;
    free(q);
    return true;
}

查找

如果要查找 链表 中是否有 结点 存储有 value 的值的话，可以通过如下函数：

// 返回 0 表示未找到
int Find(Node *head, int value) {
    Node *p = head->next;
    int i = 1;
    // 遍历链表判断是否有结点值域 value 相同
    while (p) {
        if (p->data == value) return i;
        p = p->next;
        i++;
    }
    return 0;
}

清空

清空 链表 需要删除 链表 中的每一个 结点，并且将 链表 设置为空，可以通过如下函数：

void ClearList(Node *head) {
    Node *p = head->next, *q;
    head->next = NULL;
    // 遍历每个结点，并且 free 结点
    while (p) {
        q = p->next; // 暂存下一个结点
        free(p);
        p = q;
    }
}

其他链式实现

双向链表

在 双向链表 中，每个节点包含三个部分：数据、前驱指针 prev、后继指针 next。

typedef struct DNode {
    ElementType data;
    struct DNode *prev;  // 指向前驱节点
    struct DNode *next;  // 指向后继节点
} DNode;

双向链表 主要具备以下优势：

• 可以 双向遍历，支持从任意节点向前或向后查找。
• 插入和删除 某个节点时，不需要再查找其前一个节点（与单链表相比更方便）。

插入操作

假设插入 s 到 p 前：

原来：
... ⟷ pre ⟷ p ⟷ ...

插入后：
... ⟷ pre ⟷ s ⟷ p ⟷ ...

具体操作步骤如下：

// 假设 p 是链表中的某个节点，s 是新建节点
s->prev = p->prev;      // 步骤①：新节点 s 的前驱是 p 的前驱
s->next = p;            // 步骤②：新节点 s 的后继是 p
p->prev->next = s;      // 步骤③：p 原前驱节点的 next 改为 s
p->prev = s;            // 步骤④：p 的前驱改为 s

删除操作

假设删除节点 p：

... ⟷ prev ⟷ p ⟷ next ⟷ ...
        ↓ 删除 p
... ⟷ prev ⟷ next ⟷ ...

具体操作步骤如下：

p->prev->next = p->next;  // 步骤①：前驱的 next 指向 p 的后继
p->next->prev = p->prev;  // 步骤②：后继的 prev 指向 p 的前驱
free(p);                  // 步骤③：释放 p 节点

静态链表

静态链表 实际上就是用 顺序表（一个结构体数组）来模拟 链表。结构体中包含两个元素：data 和 next，其中 data 存储数据，next 存储下一个元素的下标（相当于指针的作用）：

#define MAXSIZE 100

typedef struct {
    ElementType data;
    int next;
} SNode;

SNode list[MAXSIZE];

静态链表 使用 next == -1 作为其结束的标志。静态链表 的各种操作和 动态链表 基本一致，只需要修改指针，不需要移动元素。

循环链表

循环链表（Circular Linked List）是一种特殊的 链表 结构，其 最后一个节点的指针指向头节点，使得整个 链表 形成一个 环状结构。因此，从任何一个节点开始遍历，只要不断沿着指针走，就一定会回到起点。

循环链表 可分为两种类型：

类型	说明
单向循环链表	每个结点只有一个 next 指针，最后一个结点的 next 指向头结点
双向循环链表	每个结点有 prev 和 next，首尾相连，前后都可以循环遍历

链表操作的前置条件与边界

带头结点的单链表中，头结点不属于逻辑数据序列。若当前长度为 $L$，在第 $i$ 个逻辑位置插入应满足 $1\le i\le L+1$；删除、按位查找第 $i$ 个元素则必须满足 $1\le i\le L$。插入或删除前通常先定位到第 $i-1$ 个结点：当 $i=1$ 时，这个前驱正是头结点。把“第 $i$ 个结点”与“数组下标为 $i$”直接等同，是链表题最常见的偏一错误。

任务	需要先定位的结点	关键链接顺序	时间
在 $p$ 后插入 $s$	前驱 $p$	先令 $s$ 的后继为 $p$ 的原后继，再令 $p$ 的后继为 $s$	已知 $p$ 时 $O(1)$
删除 $p$ 的后继 $q$	前驱 $p$	先保存 $q$，令 $p$ 跳过 $q$，再释放 $q$	已知 $p$ 时 $O(1)$
按序号插入或删除	从头结点走到前驱	走 $i-1$ 条逻辑边后再改链	最坏 $O(L)$
尾插	尾结点	维护尾指针时直接追加；否则先遍历到尾	分别为 $O(1)$、$O(L)$

指针赋值顺序不是书写习惯，而是正确性条件。若在插入时先覆盖 $p$ 的后继而没有保存原后继，原链的后半段会失去唯一入口；若删除后先释放 $q$ 再读取其后继，就会访问已经失效的存储。双链表插入、删除也必须同时维护正反两个方向的链接，带头尾哨兵时可减少首尾结点的分支判断。

几种“看似方便”的做法的适用范围

单链表有一种“删除给定结点”的技巧：把后继的数据复制到当前结点，再删除后继。它只在给定结点不是尾结点、且允许改变该结点所代表逻辑元素时才能使用；尾结点没有后继，且带有外部引用或记录身份时不能随意复制数据，因此考试中的通常删除操作仍应寻找前驱。

循环链表遍历也不能沿用普通链表的“指针为空”结束条件，因为它永远不会遇到空指针。若由头结点出发，应在回到头结点时停止；若由某个数据结点出发，则通常用“至少执行一次”的循环并在再次回到起点时停止。静态链表中的游标只是数组下标，申请、释放结点还需要维护空闲链表，不能把值为 $-1$ 的游标误当成可访问的位置。

原地反转为何只需常数辅助空间

单链表原地反转可维护三个角色：已反转部分的首结点、当前待处理结点和当前结点的原后继。每轮先保存原后继，再把当前结点的后继改为已反转部分，最后整体前移到下一个待处理结点。每条链接恰好改写一次，时间为 $O(L)$、额外空间为 $O(1)$；带头结点时循环结束还要把头结点后继改为新的首结点。

这里“先保存原后继”不可省略，因为链接一旦反向，原来的后续链就无法再沿当前指针找到。空表和只有一个数据结点时不需要特别翻转，但仍应保证头结点语义不变。若题目要求反转的是某一段，还要先保存该段前驱和原首结点，反转结束后分别接回新首和新尾，不能让局部反转断开其余链表。