第十八章 数据存储结构

本章要点

在数据结构总览中我们建立了一个核心认知：数据结构 = 物理存储方式 + 逻辑组织规则。 本章聚焦物理存储层——数据在内存中到底怎么放。

那么，数据结构到底是用来干什么的？不管它叫什么名字、长什么样，它最终只做四件事：

• 增：往数据集合里加入新元素
• 删：从数据集合里移除某个元素
• 改：修改某个位置或某个条件下的元素值
• 查：根据位置或值找到目标元素

增、删、改、查，就是数据结构的基本核心操作。 任何数据结构——无论是你已经熟悉的数组，还是本章将要学习的链表，以及后续章节会遇到的栈、队列、树、哈希表——归根结底，都是围绕这四个操作来设计和优化的。

不同的存储方式，这四个操作的效率天差地别。同一个“查“，数组上 O(1)，链表上 O(n)；同一个“增“，数组中间插入要搬移大量元素，链表只需改两个指针。正是这种效率差异，决定了每种数据结构适合什么场景、不适合什么场景。理解了它们各自的增删改查特性，你才能在面对实际问题时做出正确的选型。

从物理存储的角度，常见方式可以概括为两类：连续存储和非连续存储（链式存储）。

本章深入剖析这两种存储方式的实现细节和操作效率。

具体涵盖：

• 连续存储——数组的增删改查：以数据结构的视角重新审视数组，逐一分析查、改、增、删四种操作的时间复杂度
• 非连续存储——链表：本节还将跳脱出单/双的具体形式，探讨链式存储的本质——记录前后节点信息，自由组合前驱后继
  • 单链表：节点只记后继指针，覆盖增（头插/尾插）、删、查、改全部 CRUD 操作
  • 双链表：节点同时记前驱和后继，可双向遍历；已知节点地址时 O(1) 删除，同样覆盖完整 CRUD
• 链式存储的本质：单链表和双链表只是链式存储的两种实现，核心是“记录节点之间的关系信息“

学完本章，你将彻底理解“连续 vs 链式“两种存储方式各自的优势和代价，并且不被单/双链表的具体形式所局限。

一、连续存储——数组的增删改查

1.1 以数据结构的视角看数组

第三章已经学习了数组的基础语法——声明、初始化、用下标访问。现在换一个角度：把数组当作连续存储的代表结构，分析它的四种核心操作——增、删、改、查。

之所以从这里开始，是因为数组是 C 语言中最基础、最常用的数据存储方式。理解了数组的 CRUD 操作及其复杂度，再看链式存储时就能自然地理解“为什么需要另一种存储方式“。

数组的本质是连续存储——所有元素紧挨着放在一块连续的内存中。首元素的地址称为基地址，任意元素 arr[i] 的地址可以通过公式精确计算：

&arr[i] = 基地址 + i × sizeof(元素类型)

这个公式是数组一切特性的根源。它带来了 O(1) 随机访问，也带来了插入和删除时的搬移代价。

1.2 查（Read / Search）—— 数组最擅长的操作

数组的“查“分为两种情况：按下标访问和按值查找。两者的效率天差地别。

按下标访问 —— O(1)

int arr[5] = {10, 20, 30, 40, 50};
int x = arr[2];   // 一步定位到第三个元素，值 = 30
arr[3] = 99;      // 一步定位到第四个元素，修改为 99

借助“基地址 + 下标 × 元素大小”的寻址关系，编译器可以用固定数量的地址运算定位目标元素。具体会生成几条机器指令取决于平台和优化，复杂度分析只关心运算次数不随数组长度增长，因此按下标访问是 O(1)。

这是数组的核心优势，也是它区别于链表的最根本特征。链表要实现“找第 i 个元素“，必须从头走 i 步。

按值查找（无序数组）—— O(n)

int arr[5] = {10, 20, 30, 40, 50};
int target = 30;
int index = -1;
for (int i = 0; i < 5; i++)    // 必须逐个比较
{
    if (arr[i] == target)
    {
        index = i;
        break;                  // 找到了，可以提前退出
    }
}

数据没有排序，目标值可能在任何位置。最好情况（第一个就是）：1 次比较，O(1)。最坏情况（在最后一个或不存在）：n 次比较，O(n)。平均情况：n/2 次比较，O(n)。时间复杂度取最坏情况——O(n)。

按值查找（有序数组 + 二分查找）—— O(log n)

如果数组是有序的，就可以使用二分查找。在讲代码之前，先用一个你已经熟悉的场景来理解它的思想。

回忆一下第一章的猜数游戏：程序在 1~100 之间随机选了一个数，你来猜。最高效的猜法是什么？不是从 1 开始逐个往上试——那太慢了。而是每次猜中间值：

• 第一次猜 50。程序说“猜小了“——你立刻知道答案在 51~100，一半的数字被排除了。
• 第二次猜 75（51~100 的中间）。程序说“猜大了“——答案在 51~74，又排除了一半。
• 第三次猜 62（51~74 的中间）。如果还不对，继续缩窄范围……

你每猜一次，候选范围就缩小一半。100 个数字，最多猜 7 次一定能找到——因为 2⁷ = 128 > 100。这就是二分查找的核心思想：在一个有序的序列中，每次取中间位置的值和目标比较，根据比较结果将搜索范围缩小一半，直到找到目标或范围为空。

二分查找之所以高效，是因为它没有“遍历“——它从不逐个检查元素，而是像猜数一样，每次一刀切掉一半的候选区域。把这个思路翻译成 C 代码，就是下面这个样子（假设数组按从小到大排列；若按降序排列，需调换分支中的比较方向）：

// 在有序数组 arr 中查找 target，返回下标，未找到返回 -1
int binary_search(int arr[], int n, int target)
{
    int left = 0, right = n - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;   // 找中间位置
        if (arr[mid] == target)
            return mid;                         // 找到了
        else if (arr[mid] < target)
            left = mid + 1;                     // target 在右半部分
        else
            right = mid - 1;                    // target 在左半部分
    }
    return -1;  // 没找到
}

函数一开始用 left 和 right 标记当前的搜索范围——最初是整个数组，left = 0，right = n - 1。

循环的每一步，先计算当前范围的中间位置 mid。这里用的是 left + (right - left) / 2 而不是更直观的 (left + right) / 2，是为了防止 left + right 溢出 int 的上限——这是二分查找中一个经典的细节陷阱。

拿到 mid 之后，比较 arr[mid] 和目标值，三种情况：

• 相等——命中目标，直接返回下标 mid。
• arr[mid] 偏小——说明目标在右半部分，把 left 右移到 mid + 1，搜索范围缩小到右半边。
• arr[mid] 偏大——说明目标在左半部分，把 right 左移到 mid - 1，搜索范围缩小到左半边。

每轮循环，搜索范围缩小一半。10000 个元素的数组，最多只需要约 14 次比较。这就是 O(log n) 的威力。

💡 高效二分查找的前提是数据有序且支持随机访问。 普通链表不能 O(1) 定位到中间元素，即使勉强套用二分思路，也得不到数组上 O(log n) 的时间复杂度。

1.3 改（Update）—— 按下标修改 O(1)

“修改“是指把某个位置的值替换为新值。如果知道下标，和按下标访问完全一样：

arr[2] = 99;   // 把下标为 2 的元素改为 99，O(1)

如果不知道下标、只知道“要把值为 30 的元素改成 99“，那就得先查找——查找的复杂度 O(n) 决定了整体复杂度。

1.4 增（Insert）—— 数组最吃亏的操作

“插入“是指在数组的某个位置加入一个新元素。因为数组要求元素连续存放，插入意味着要把插入点之后的所有元素向后移一格，给新元素腾出空间。

在末尾插入 —— O(1)

int arr[100] = {10, 20, 30};   // 当前有 3 个元素
int size = 3;
arr[size] = 40;                 // 直接在末尾写入
size++;                         // 元素个数 +1

末尾还有空位时，直接在 arr[size] 处写入，一步完成——O(1)。这是数组插入的唯一高效场景。

在开头或中间插入 —— O(n)

// 在下标 index 处插入 value。
// 前置条件：index 在 [0, *size] 内，并且数组至少还有一个空位。
void insert_at(int arr[], int *size, int index, int value)
{
    // (1) 从最后一个元素开始，每个元素向后移一格
    for (int i = *size; i > index; i--)
    {
        arr[i] = arr[i - 1];
    }
    // (2) 在腾出的空位写入新值
    arr[index] = value;
    // (3) 元素个数 +1
    (*size)++;
}

参数 size 声明为指针，因为函数内部需要修改调用方的元素计数变量。*size 同时也是搬移的起点——当前有多少个有效元素，搬移就从最后一个有效元素的后面开始。

搬移是插入的核心。循环从 *size（末尾的后一个位置）开始，从后往前逐个把元素向后挪一格：arr[i] = arr[i - 1]。为什么必须从后往前？假设从前往后——先把 arr[index] 赋值给 arr[index+1]，那原来 arr[index+1] 的值就被覆盖了，再也找不回来。从最后一个元素开始往后挪，每个值在被覆盖之前都已经搬到了安全位置，不会丢失数据。

腾出空位后，arr[index] = value 把新值写入。最后 (*size)++ 让元素计数加一。注意这里的括号——*size++ 会被解析为 *(size++)（先拿到 size 指向的值，再把指针本身加一），而不是我们想要的“把 *size 的值加一“，所以必须写成 (*size)++。

时间复杂度分析：最坏情况是在下标 0 插入——所有 n 个元素都要向后移一格，O(n)。平均情况：插在中间，搬移 n/2 个元素，也是 O(n)。

完整示例

#include <stdio.h>

void insert_at(int arr[], int *size, int index, int value)
{
    for (int i = *size; i > index; i--)
        arr[i] = arr[i - 1];
    arr[index] = value;
    (*size)++;
}

int main(void)
{
    int arr[100] = {10, 20, 30, 40, 50};
    int size = 5;

    printf("插入前：");
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");   // 输出：10 20 30 40 50

    insert_at(arr, &size, 2, 99);   // 在下标 2 插入 99

    printf("插入后：");
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");   // 输出：10 20 99 30 40 50

    return 0;
}

💡 数组空间不够时怎么办？

上面的示例假设数组容量 100 足够大。如果容量不够，需要使用 realloc 扩展空间（动态数组），这在第十章已讲过。但即使用了 realloc，插入时的搬移代价依然存在——realloc 解决了“容量“问题，解决不了“搬移“问题。

1.5 删（Delete）—— 插入的逆操作

“删除“是指把某个位置的元素移除。和插入相反——插入是“往后移、腾空位”，删除是“往前移、填空位“。

// 删除下标 index 处的元素；前置条件：index 在 [0, *size) 内
void delete_at(int arr[], int *size, int index)
{
    // (1) 从 index+1 开始，每个元素向前移一格
    for (int i = index; i < *size - 1; i++)
    {
        arr[i] = arr[i + 1];
    }
    // (2) 元素个数 -1
    (*size)--;
}

删除的搬移方向和插入相反。插入时从后往前搬，是为了给新元素腾空间；删除时是从前往后搬，用后面的元素覆盖前面的空位。循环从 index 开始，依次执行 arr[i] = arr[i + 1]——把 index + 1 及其后的所有元素逐个向前拉一格。从前往后是安全的，因为我们是”拉后面的覆盖前面的”，前面的值本来就是要丢弃的。

最后 (*size)-- 让有效元素计数减一。注意，原最后一个位置（arr[*size]）的值并没有被清除，只是不再属于有效范围——下次插入新元素时会直接覆盖它，所以不影响正确性。

时间复杂度分析：最坏情况是删除下标 0——所有元素都要向前移一格，O(n)。删除最后一个元素（下标 size-1）：不需要搬移，size-- 一步完成，O(1)。

1.6 数组 CRUD 总结

数组的增删瓶颈在于搬移数据——这是“连续存放“必须付出的代价。链表正是为了解决这个问题而诞生的。

二、非连续存储——链表

2.1 什么是链式存储

数组要求所有元素连续存放，插入删除就得”大搬家”。链式存储换了一个完全不同的思路：让每个元素自己记住”前后的元素在哪里”，用指针把分散在各处的数据串联起来。

那么，”分散在各处”的数据是怎么来的？答案在第十章——malloc。数组的存储空间由编译器在栈上一次性分配（int arr[5]），大小写死、位置固定。而链式存储的每一个节点都是在需要时通过 malloc 在堆上逐个独立申请的——你不知道会有多少个节点、每个节点会分配在哪个地址，唯一能把它们组织起来的手段，就是在每个节点里存一个指向下一个节点的指针。

这就是链式存储和 malloc 的关系：malloc 提供了”按需、分散、独立”创建节点的能力，指针提供了把这些散落的节点串联成一条链的能力。 二者缺一不可。

链表由若干节点（Node）组成，每个节点包含两部分：

• 数据域：存储实际的数据值。
• 指针域：存储一个或多个指针，记录其他节点的地址。

链表的”头”负责保存整条链的入口，后续节点通过各自的指针域一级一级串下去；对于本章介绍的非循环链表，最后一个节点的后继指向 NULL，表示链表结束。

在 C 语言里，链式存储常见有两种组织方式：

• 不带头节点：head 直接指向第一个存有数据的节点；空链表时 head == NULL。这种写法少一个节点，但插入、删除第一个节点时经常要单独处理，因为链表入口本身会变。
• 带头节点：先准备一个不存有效数据的节点作为 head，真实数据从 head->next 开始；空链表时 head->next == NULL。这种写法多一个头节点，但链表入口稳定，头插、尾插、删除第一个数据节点和删除中间节点都更容易统一。

本教程的数据结构部分统一采用带头节点的实现。原因很朴素：初学阶段最容易出错的是“第一个节点要不要特殊处理”。头节点像一个固定的入口和哨兵，让 head 本身一直存在，很多操作都能从“修改某个节点的 next”这一条规则出发。

链式存储的核心取舍：牺牲了随机访问（想找第 N 个？必须从头数过去），换来了插入删除的灵活性（只改指针，不搬数据）和动态增长的弹性（不需要提前声明大小，来一个数据 malloc 一个节点）。需要频繁增删、或数据量事先不确定的场景下，这个取舍是值得的。

2.2 连续存储 vs 链式存储：初步对比

在深入链表的具体实现之前，先对两种存储方式做一个宏观对比：

• 连续存储（数组）：所有元素紧挨着放在一块连续的内存中。知道首地址和元素大小，任意元素的位置可以精确算出来——首地址 + 下标 × sizeof(元素)。这是数组 O(1) 随机访问的物理基础，也是”改”和”按下标查”极快的原因。但正因为要求连续，中间插入和删除需要搬移元素。
• 链式存储（链表）：每个节点独立 malloc，散落在内存各处，通过指针串联。节点地址没有规律，找第 N 个必须从头走 N 步。但也正因为不要求连续，插入和删除只需改指针，不需要搬移任何数据。此外，链表的大小是动态的——不像数组那样必须在编译时定死长度。

连续存储带来了随机访问，也带来了搬移代价和固定大小。链式存储失去了随机访问，却换来了插入删除的灵活和动态增长的弹性。 这就是数组和链表所有差异的根源。

链表的变体取决于节点记录多少关系信息。接下来逐一讲解最主流的两种：单链表（节点只记后继）和双链表（节点同时记前驱和后继）。本章所有链表代码都使用带头节点的非循环链表。

2.3 单链表

单链表是链式存储最简单、最基础的形式。它的规则只有一条：每个节点只记录自己后面那个节点的地址。在带头节点的单链表里，head 是固定存在的入口节点，不保存有效数据；第一个真实数据节点是 head->next。后续节点一个记着一个，最后一个的指针指向 NULL，表示“后面没有了“。

用图来看就是这样一条单向的链：

节点结构定义

要把上面那张图变成 C 代码，第一步是定义“节点长什么样“。一个节点需要两样东西：存数据的空间，和一个指向下一个节点的指针。用结构体来描述：

typedef struct Node
{
    int data;           // 数据域：存放数据（这里以 int 为例）
    struct Node *next;  // 指针域：指向下一个同类型的节点
} Node;

这段代码在内存中造出来的东西长这样：

• int data;：数据域。这里以 int 为例存整数，实际开发中可以换成任何你需要的类型。
• struct Node *next;：指针域。注意这里写的是 struct Node * 而不是 Node *——因为 typedef 到花括号结束时才生效，在结构体内部编译器还不认识 Node 这个简称。next 存的是“下一个节点的地址“，没有下一个节点时就指向 NULL。

💡 为什么指针域的类型是 struct Node *？

因为 next 要指向的是另一个同类型的节点。一个节点内部包含一个指向同类型节点的指针——这在 C 语言中称为自引用结构。编译器只需要知道 struct Node * 是一个指针类型，不需要知道 struct Node 的全部细节就能处理它，所以这种自引用语法是合法的。

创建节点

有了节点类型，下一步就是“造节点”。创建节点的过程是：通过 malloc 向 C 运行库的内存分配器申请一块内存，再填写数据和指针。

Node *create_node(int data)
{
    // (1) 申请内存
    Node *new_node = malloc(sizeof *new_node);
    // (2) 检查是否申请成功
    if (new_node == NULL)
    {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    // (3) 填写数据域
    new_node->data = data;
    // (4) 指针域初始化为 NULL
    new_node->next = NULL;
    // (5) 返回这个新节点的地址
    return new_node;
}

函数的任务是：向堆申请一个 Node 大小的内存块，填好数据和指针，然后把这个节点的地址返回给调用者。

malloc(sizeof *new_node) 按变量本身取 sizeof——这样即使以后把 new_node 的类型从 Node * 改成别的，sizeof 也会自动跟上，不容易漏改。malloc 返回的是 void *，在 C 语言中可以自动转换为任何对象指针类型，不需要强制转换；关键是确保 #include <stdlib.h> 已经包含，否则编译器可能对 malloc 做出错误的假设。

malloc 在内存不足时会返回 NULL，必须检查。虽然实际环境中很少真的内存耗尽，但养成每次检查的习惯是专业程序员的基本素养——未定义行为往往就从一次未检查的 NULL 开始。

接下来填写节点内容。new_node->data = data 把传入的数据写入数据域，-> 运算符用于通过指针访问结构体成员。new_node->next = NULL 把指针域初始化为空——新节点刚创建还没有“下家“，暂时指向 NULL，等插入链表时由调用方来更新这个指针。

一切就绪后，return new_node 把新节点的地址返回出去。

初始化头节点

带头节点的链表在使用前，要先准备并初始化这个固定入口。头节点本身不保存有效数据，所以只需要把 next 设为 NULL：

void init_list(Node *head)
{
    head->next = NULL;
}

初始化之后，head->next == NULL 表示空链表；一旦插入第一个数据节点，head->next 就指向它。

2.3.1 插入操作

单链表的插入有两种基本方式：头插法（插在链表最前面）和尾插法（插在链表最后面）。两种方式的实现思路和使用场景不同，逐一来看。

头插法——每次插在链表最前面

头插法的思路很简单：让新节点指向当前第一个数据节点，然后让头节点指向新节点。头节点本身不变，变的是 head->next。

过程图解：

void insert_at_head(Node *head, int data)
{
    // (1) 创建一个新节点
    Node *new_node = create_node(data);
    // (2) 新节点的 next 指向当前第一个数据节点
    new_node->next = head->next;
    // (3) 头节点的 next 指向新节点
    head->next = new_node;
}

步骤分解：

• 参数 Node *head：传入固定存在的头节点。如果链表为空，head->next 的值就是 NULL，此时步骤②等价于 new_node->next = NULL，结果正确。

上图完整展示了头插法的三个步骤：创建新节点 → 新节点接住原第一个数据节点 → 头节点指向新节点。注意步骤②中，head->next 存的是原第一个数据节点的地址，赋值后 new_node->next 就指向它；步骤③让 head->next 改为指向新节点，新节点成为第一个数据节点。顺序不能反——必须先让新节点接住后面的链，再修改头节点，否则原链表就丢失了引用。

调用方式（非常重要）：

Node head;                          // 头节点，不保存有效数据
init_list(&head);                    // 空链表：head.next == NULL
insert_at_head(&head, 20);            // 链表: 20
insert_at_head(&head, 10);            // 链表: 10 → 20
insert_at_head(&head, 5);             // 链表: 5 → 10 → 20

注意：带头节点后，调用者不需要接收返回值。head 这个入口节点始终存在，插入函数只修改 head.next 或后续节点的 next。

尾插法——每次插在链表最后面

尾插法的思路是：先找到链表的最后一个节点（next 指向 NULL 的那个），然后把新节点挂在它后面。

过程图解：

void insert_at_tail(Node *head, int data)
{
    // (1) 创建新节点
    Node *new_node = create_node(data);

    // (2) 从头节点开始，遍历找到最后一个节点
    Node *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }

    // (3) 将最后一个节点的 next 指向新节点
    p->next = new_node;
}

步骤分解：

上图完整展示了尾插法的三个阶段：创建新节点 → 找到最后一个节点 → 将最后节点的 next 指向新节点。代码里 Node *p = head 和 while (p->next != NULL) p = p->next 共同完成第二阶段：p 每轮检查 p->next，只要后面还有节点就前进一步；直到 p->next == NULL 时停下，此时 p 就是最后一个节点。空链表时循环一次也不进，p 停在头节点，第三阶段的 p->next = new_node 等价于 head->next = new_node，逻辑完全统一。

中间插入——插在某个节点之后

头插和尾插解决的是链表两端的插入；实际使用中还常常需要“把新节点插到某个已有节点之后”。例如链表为 10 → 20 → 30，希望把 25 插到 20 后面，结果应为 10 → 20 → 25 → 30。

过程图解：

void insert_after(Node *head, int target, int data)
{
    // (1) 找到第一个 data == target 的节点
    Node *p = head->next;
    while (p != NULL && p->data != target)
    {
        p = p->next;
    }
    if (p == NULL) return;

    // (2) 创建新节点
    Node *new_node = create_node(data);

    // (3) 新节点接住 p 原来的后继
    new_node->next = p->next;

    // (4) p 指向新节点
    p->next = new_node;
}

中间插入的关键仍然是顺序：先让新节点接住后面的链，再让前一个节点指向新节点。如果先执行 p->next = new_node，原来 p->next 指向的后续节点就丢失了引用。带头节点并不改变中间插入的本质，它只是让头部插入也能使用同一类“改链接”的思路。

💡 头插法 vs 尾插法的选择

头插法的优点是快——不需要遍历，时间复杂度 O(1)。缺点是插入的顺序和数据出现的顺序是反的：你先插 10 再插 20，链表是 20→10。

尾插法的优点是保持顺序——先插 10 再插 20，链表是 10→20。但每次都要遍历到末尾，时间复杂度 O(n)（n 是当前链表长度）。如果频繁尾插，可以考虑维护一个尾指针来避免遍历——后面的双链表和链式队列就会采用这个思路。

2.3.2 删除操作

删除节点的思路是：找到要删除的节点，让它的前一个节点绕过它直接指向它的后一个节点，然后释放它的内存。

void delete_node(Node *head, int data)
{
    // (1) 从头节点开始找目标节点的前一个节点
    Node *p = head;
    while (p->next != NULL && p->next->data != data)
    {
        p = p->next;
    }

    // (2) 找到了，执行删除
    if (p->next != NULL)
    {
        Node *temp = p->next;           // 暂存要删除的节点
        p->next = temp->next;           // 绕过它
        free(temp);                     // 释放内存
    }
}

带头节点后，删除逻辑不再分”删除第一个数据节点”和”删除中间节点”两种大分支。因为头节点可以充当第一个数据节点的前驱：如果要删的是第一个数据节点，循环一开始 p == head，直接让 head->next = temp->next 即可。

代码的核心逻辑是：找到目标节点的前一个节点 p，修改 p->next 让它绕过目标。这个 p 可能是头节点，也可能是普通数据节点。

上图完整展示了单链表删除的三个步骤：找前驱 → 绕过目标 →释放内存。步骤①中，while 循环检查 p->next->data 而不是 p->data——这是单链表删除的关键设计。因为单链表没有 prev 指针，如果检查 p->data，p 会停在目标节点本身，无法修改前驱的链接；检查 p->next->data 则让 p 停在目标前面，随后通过修改 p->next 就能绕过目标。步骤②中，temp = p->next 暂存目标节点地址，然后 p->next = temp->next 让前驱跳过目标直接指向后继——不搬移任何数据，只改一个指针。步骤③ free(temp) 释放目标节点内存，删除完成。

2.3.3 查找操作

链表中查找一个值，思路和数组的线性查找一样——从头到尾逐个比较。但因为链表没有下标，不能直接跳到第 N 个元素，只能沿着 next 指针一步一步往后走。

// 在链表中查找值为 data 的节点，返回节点地址；未找到返回 NULL
Node *find_node(Node *head, int data)
{
    Node *p = head->next;                 // 从第一个数据节点开始
    while (p != NULL && p->data != data)  // 遍历比较
    {
        p = p->next;                      // 没找到就前进
    }
    return p;                             // 找到返回地址，未找到返回 NULL
}

用一个行走指针 p 从 head->next 出发，每走一步检查 p->data 是否等于目标值。相等就返回 p（目标节点的地址）；走到 p == NULL 说明链表里没有这个值，返回 NULL。

调用者拿到返回值后，先判断是否为 NULL——非 NULL 就是找到了，可以读取 p->data；NULL 就是没找到。时间复杂度 O(n)，最坏情况下目标在末尾或不存在，需要走遍整个链表。

2.3.4 修改操作

修改就是“找到 → 覆盖“。先调用 find_node 定位目标节点，然后直接改写它的数据域。

// 将值为 old_data 的节点的数据域改为 new_data
// 返回 true 表示修改成功，false 表示未找到
bool update_node(Node *head, int old_data, int new_data)
{
    Node *p = find_node(head, old_data);  // (1) 先查找
    if (p == NULL) return false;          // (2) 没找到，返回 false
    p->data = new_data;                   // (3) 找到，覆写数据域
    return true;
}

找到目标节点后，p->data = new_data 一次赋值就完成了修改——O(1)。但算上查找的时间，整体还是 O(n)。这和数组“已知值再修改“的场景一样：瓶颈在查找，不在修改本身。

如果已知节点地址（比如遍历过程中顺手改），修改只是 O(1)。这在实际开发中很常见——先 find_node 拿到地址，后续反复修改同一节点时直接通过地址操作，不需要再次查找。

💡 查 vs 改 vs 删的共性：三个操作的核心都是先找到目标节点。查找直接返回地址，修改在找到后覆写数据，删除在找到前驱后改指针。理解了这个共性，链表的操作就不再是零散的几个函数，而是一个统一的模式。

2.3.5 遍历操作

遍历就是沿着指针把每个节点都访问一遍。最常见的使用场景是打印链表内容和释放整个链表。

打印链表

void print_list(Node *head)
{
    Node *p = head->next;        // (1) 从第一个数据节点开始
    while (p != NULL)            // (2) 只要没有走到末尾
    {
        printf("%d → ", p->data); // (3) 打印当前节点的数据
        p = p->next;              // (4) 移动到下一个节点
    }
    printf("NULL\n");             // (5) 打印结尾标志
}

遍历的核心是一个“行走指针“ p，它从第一个数据节点（head->next）出发，每次沿着 next 走到下一个节点，直到 next 为 NULL 时停下。头节点不保存有效数据，所以出发时要跳过它。

循环体内，每走到一个节点，先打印它的数据域 p->data，然后执行 p = p->next 前进一步。就像沿着线索逐个访问，直到末尾。循环结束后打印 NULL 作为链表结束的标志。

释放整个链表

链表是 malloc 创建的，用完后必须逐个释放，否则造成内存泄漏。

void free_list(Node *head)
{
    Node *p = head->next;
    while (p != NULL)
    {
        Node *temp = p;     // (1) 记住当前节点
        p = p->next;        // (2) 先前进到下一个节点
        free(temp);         // (3) 再释放之前记住的节点
    }
    head->next = NULL;      // (4) 头节点保留，链表重新变空
}

释放链表的关键在于顺序：必须先拿到下一个节点的地址，再释放当前节点。如果反过来——先 free(p) 再访问 p->next——就是在读已经释放的内存，属于未定义行为，后果不可预料。

所以代码用一个 temp 暂存当前要释放的节点：temp = p，然后 p = p->next 先前进到下一个节点，最后 free(temp) 安全释放。就像一个接力——每次把当前节点交给 temp，自己先跨到下一步，再放手前一个。循环走完一遍，所有数据节点占用的内存都归还给系统。最后把 head->next 重新设为 NULL，头节点保留，链表回到空状态。头节点通常由调用方在栈上创建，不在这里释放。

2.3.6 时间复杂度分析

学完了单链表的全部操作，现在逐一分析每个操作的效率。不要只记结论——跟着代码看清楚“为什么是这个复杂度“。

（1）创建节点 —— O(1)

Node *create_node(int data)
{
    Node *new_node = malloc(sizeof *new_node);       // 一次内存分配
    if (new_node == NULL) { fprintf(stderr, "内存分配失败\n"); exit(EXIT_FAILURE); }
    new_node->data = data;                          // O(1)：一次赋值
    new_node->next = NULL;                          // O(1)：一次赋值
    return new_node;                                // O(1)
}

在常见的数据结构分析模型中，一次固定大小的 malloc 记作 O(1)，所以此函数相对于链表长度是 O(1)。实际分配器的耗时由实现决定，语言标准不保证 malloc 必然是常数时间。

（2）头插法 —— O(1)

void insert_at_head(Node *head, int data)
{
    Node *new_node = create_node(data);   // O(1)
    new_node->next = head->next;         // O(1)：接住原第一个数据节点
    head->next = new_node;               // O(1)：头节点指向新节点
}

关键在 new_node->next = head->next 和 head->next = new_node 这两行——只改两个指针的指向，不涉及任何遍历或搬移。链表有 10 个节点还是 10 万个节点，头插的工作量完全一样——O(1)。

对比数组在头部插入：所有元素要向后移一格，O(n)。

（3）尾插法 —— O(n)

void insert_at_tail(Node *head, int data)
{
    Node *new_node = create_node(data);   // O(1)
    Node *p = head;
    while (p->next != NULL)             // ← 这里决定了复杂度
        p = p->next;                    // 每走一步 O(1)，总共走 n 步
    p->next = new_node;                  // O(1)
}

while 循环从头节点一直走到最后一个节点：链表有 n 个数据节点，最坏就要走 n 步。因此尾插是 O(n)。如果像后面的链式队列那样维护一个尾指针，尾插也可以做到 O(1)——多存一个指针，省掉每次遍历。

对比数组在尾部插入（有空间余裕时）：直接写 arr[size] = x，O(1)。

（4）中间插入 —— 已知前驱 O(1)，按值查找后 O(n)

void insert_after(Node *head, int target, int data)
{
    Node *p = head->next;
    while (p != NULL && p->data != target)   // O(n)：先找到插入位置
        p = p->next;
    if (p == NULL) return;

    Node *new_node = create_node(data);      // O(1)
    new_node->next = p->next;                // O(1)：接住后继
    p->next = new_node;                      // O(1)：前驱指向新节点
}

如果已经拿到了要插入位置的前驱节点地址，真正的插入动作只需要改两个指针，是 O(1)。但本例按值 target 查找插入位置，需要先遍历链表，整体就是 O(n)。链表的优势在于“不搬移数据”，不是“自动知道位置在哪里”。

（5）删除节点 —— O(n)

void delete_node(Node *head, int data)
{
    // 从头节点开始找目标节点的前驱：while 循环是 O(n)
    Node *p = head;
    while (p->next != NULL && p->next->data != data)  // ← 遍历查找
        p = p->next;                                   // 最坏走 n 步

    if (p->next != NULL)                               // 找到了
    {
        Node *temp = p->next;
        p->next = temp->next;                          // O(1)：绕过
        free(temp);                                    // O(1)：释放
    }
}

删除分两阶段：查找目标 → 执行删除。查找需要遍历，最坏走 n 步（O(n)）；找到后改一个指针、一次 free（O(1)）。总复杂度 O(n)，瓶颈在查找。

关键洞察：删除的指针操作本身是 O(1)（不搬数据），但前提是已经取得所需链接信息。单链表删除需要目标节点的前驱；头节点让“第一个数据节点”也拥有一个稳定前驱，因此删除代码不用再为它单独分支。数组删除即使知道下标，也要把后面所有元素前移——还是 O(n)。

（5）遍历和释放 —— O(n)

void print_list(Node *head)
{
    Node *p = head->next;
    while (p != NULL) { printf("%d ", p->data); p = p->next; } // 走 n 步，O(n)
}

void free_list(Node *head)
{
    Node *p = head->next;
    while (p != NULL) { Node *t = p; p = p->next; free(t); }  // 走 n 步，O(n)
    head->next = NULL;
}

两个函数都是从头走到尾，每节点访问一次——O(n)。

小结：

和数组的核心区别：数组的 O(n) 来自搬移数据，链表的 O(n) 来自遍历寻址。尾部操作的全面对比（包括和双链表的三方对比）见第十九章 总结与对比。

2.3.7 完整示例

将以上所有代码组合成一个可以编译运行的程序，验证单链表的各项操作：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// ========== 节点类型定义 ==========
typedef struct Node
{
    int data;
    struct Node *next;
} Node;

// ========== 初始化头节点 ==========
void init_list(Node *head)
{
    head->next = NULL;
}

// ========== 创建数据节点 ==========
Node *create_node(int data)
{
    Node *new_node = malloc(sizeof *new_node);
    if (new_node == NULL)
    {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

// ========== 头插法 ==========
void insert_at_head(Node *head, int data)
{
    Node *new_node = create_node(data);
    new_node->next = head->next;
    head->next = new_node;
}

// ========== 尾插法 ==========
void insert_at_tail(Node *head, int data)
{
    Node *new_node = create_node(data);
    Node *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = new_node;
}

// ========== 插在指定节点之后 ==========
void insert_after(Node *head, int target, int data)
{
    Node *p = head->next;
    while (p != NULL && p->data != target)
    {
        p = p->next;
    }
    if (p == NULL) return;

    Node *new_node = create_node(data);
    new_node->next = p->next;
    p->next = new_node;
}

// ========== 删除节点 ==========
void delete_node(Node *head, int data)
{
    Node *p = head;
    while (p->next != NULL && p->next->data != data)
    {
        p = p->next;
    }
    if (p->next != NULL)
    {
        Node *temp = p->next;
        p->next = temp->next;
        free(temp);
    }
}

// ========== 查找节点 ==========
Node *find_node(Node *head, int data)
{
    Node *p = head->next;
    while (p != NULL && p->data != data)
        p = p->next;
    return p;
}

// ========== 修改节点 ==========
bool update_node(Node *head, int old_data, int new_data)
{
    Node *p = find_node(head, old_data);
    if (p == NULL) return false;
    p->data = new_data;
    return true;
}

// ========== 打印链表 ==========
void print_list(Node *head)
{
    Node *p = head->next;
    while (p != NULL)
    {
        printf("%d → ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

// ========== 释放链表 ==========
void free_list(Node *head)
{
    Node *p = head->next;
    while (p != NULL)
    {
        Node *temp = p;
        p = p->next;
        free(temp);
    }
    head->next = NULL;
}

// ========== 主函数 ==========
int main(void)
{
    Node head;
    init_list(&head);

    // 测试尾插法
    insert_at_tail(&head, 10);
    insert_at_tail(&head, 20);
    insert_at_tail(&head, 30);
    printf("尾插后：");
    print_list(&head);   // 输出: 10 → 20 → 30 → NULL

    // 测试中间插入
    insert_after(&head, 20, 25);
    printf("插入25：");
    print_list(&head);   // 输出: 10 → 20 → 25 → 30 → NULL

    // 测试头插法
    insert_at_head(&head, 5);
    printf("头插后：");
    print_list(&head);   // 输出: 5 → 10 → 20 → 25 → 30 → NULL

    // 测试删除
    delete_node(&head, 20);
    printf("删除20：");
    print_list(&head);   // 输出: 5 → 10 → 25 → 30 → NULL

    // 删除第一个数据节点
    delete_node(&head, 5);
    printf("删除5：");
    print_list(&head);   // 输出: 10 → 25 → 30 → NULL

    // 测试查找
    Node *found = find_node(&head, 30);
    if (found != NULL)
        printf("找到节点，data = %d\n", found->data);  // 输出: 找到节点，data = 30

    // 测试修改
    if (update_node(&head, 10, 99))
    {
        printf("修改10→99：");
        print_list(&head);   // 输出: 99 → 30 → NULL
    }

    // 释放链表
    free_list(&head);

    return 0;
}

运行输出：

尾插后：10 → 20 → 30 → NULL
插入25：10 → 20 → 25 → 30 → NULL
头插后：5 → 10 → 20 → 25 → 30 → NULL
删除20：5 → 10 → 25 → 30 → NULL
删除5：10 → 25 → 30 → NULL
找到节点，data = 30
修改10→99：99 → 25 → 30 → NULL

2.4 双链表

什么是双链表

单链表有一个明显的局限：只能单向行走。每个节点只有指向“后面“的指针，没有指向“前面“的指针。如果你已经走到了某个节点，突然想回退一步看看前一个节点——对不起，单链表做不到。删除某个节点时，也必须先找到它的前驱节点——因为你需要修改前驱节点的 next。

双链表在单链表的基础上给每个数据节点增加了一个前驱指针，指向它的前一个节点。带头节点的双链表中，第一个数据节点的 prev 指向头节点。这样一来：

• 从任意一个节点，既可以向前走（next），也可以向后走（prev）。
• 给定一个节点的地址，可以直接删除它，不需要遍历找前驱。
• 维护头、尾指针时，可以在链表两端高效地插入和删除；本节只保存头节点，因此尾插仍需遍历。

双链表的特点：

节点结构定义

双链表的节点在单链表基础上增加了 prev 指针域：

typedef struct DNode
{
    int data;            // 数据域
    struct DNode *prev;  // 前驱指针：指向前一个节点
    struct DNode *next;  // 后继指针：指向后一个节点
} DNode;

双链表节点比单链表多了一个 prev 指针域。data 负责存数据，和单链表相同。next 是后继指针，指向后一个节点，和单链表的 next 功能一样——最后一个节点的 next 指向 NULL。prev 是新加入的前驱指针，指向前一个节点；如果是第一个数据节点，它的 prev 指向头节点，头节点自己的 prev 则为 NULL。有了这两个指针，任意节点都能同时访问它前后两个邻居，正着走用 next，反着走用 prev。

单链表用一个指针串起一条链，双链表用两个指针串起一条“双向链“——正着走用 next，反着走用 prev。

创建节点

void init_d_list(DNode *head)
{
    head->prev = NULL;
    head->next = NULL;
}

DNode *create_d_node(int data)
{
    DNode *node = malloc(sizeof *node);
    if (node == NULL)
    {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    node->data = data;
    node->prev = NULL;   // 新节点暂时没有前驱
    node->next = NULL;   // 新节点暂时没有后继
    return node;
}

init_d_list 初始化头节点，它的职责和单链表的头节点一样——不存有效数据，只作为链表入口。不同的是双链表头节点多了一个 prev 字段，这里也设为 NULL，表示头节点之前没有别的节点。

create_d_node 和单链表的 create_node 几乎一样，唯一的区别是新节点多了一个 prev 指针需要初始化。新创建的节点还没有“邻居“，所以 prev 和 next 都设为 NULL，等插入链表时由调用方来建立双向连接。

2.4.1 插入操作

双链表的插入同样分为头插法和尾插法。双链表因为可以双向遍历，维护一个尾指针会让尾插变得高效。但为了降低学习曲线，这里先介绍只维护头节点、不维护尾指针的基本版本。

头插法

头插法需要维护两个方向的指针：新节点 → 原第一个数据节点（next），以及原第一个数据节点 → 新节点（prev）。同时，新节点的 prev 要指向头节点。

void insert_at_head(DNode *head, int data)
{
    DNode *new_node = create_d_node(data);  // (1) 创建新节点

    new_node->prev = head;                 // (2) 新节点前驱指向头节点
    new_node->next = head->next;           // (3) 新节点后继指向原第一个数据节点
    if (head->next != NULL)
    {
        head->next->prev = new_node;       // (4) 原第一个数据节点回指新节点
    }
    head->next = new_node;                 // (5) 头节点指向新节点
}

创建新节点之后，需要建立三个方向的连接：新节点到头节点（prev）、新节点到原第一个数据节点（next）、以及原第一个数据节点回指新节点（prev）。

首先，new_node->prev = head——作为新的第一个数据节点，它的前驱就是头节点。然后 new_node->next = head->next——让新节点的 next 接住原来的第一个数据节点（如果链表为空，head->next 是 NULL，结果也正确）。接下来是关键的一步：如果原来不是空链表，原第一个数据节点的 prev 必须回指新节点（head->next->prev = new_node），否则原第一个节点的前驱还指着别处，双向链就断了。最后 head->next = new_node 让头节点指向新节点，完成插入。

注意这几步的顺序：必须先让新节点的 prev 和 next 各就各位，再修改外部节点指向新节点。如果反过来先改 head->next，原来的第一个数据节点就丢失了引用，再也找不回来。

尾插法

void insert_at_tail(DNode *head, int data)
{
    DNode *new_node = create_d_node(data);  // (1) 创建新节点

    // (2) 从头节点开始，遍历找到最后一个节点
    DNode *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }

    // (3) 建立双向连接
    p->next = new_node;                    // 旧尾节点的后继指向新节点
    new_node->prev = p;                    // 新节点的前驱指向旧尾节点
}

尾插的第一步和单链表一样——用 p 指针从头节点出发，沿着 next 一路走到最后一个节点（p->next == NULL 时停下）。空链表时循环不执行，p 就停在头节点。

找到尾节点后，建立双向连接：p->next = new_node 让旧尾节点（或头节点）的 next 从 NULL 改为指向新节点；new_node->prev = p 让新节点的 prev 指回去，完成双向绑定。空链表时 p 是头节点，所以 p->next = new_node 等价于 head->next = new_node，new_node->prev = p 就是指向头节点——逻辑完全统一。

中间插入

双链表中间插入同样可以描述为“插到某个已有节点之后”。和单链表相比，它多维护一个反向链接：新节点不仅要通过 next 指向后继，还要通过 prev 指向前驱；如果后继存在，后继的 prev 也必须改为新节点。

void insert_after(DNode *head, int target, int data)
{
    // (1) 找到第一个 data == target 的节点
    DNode *p = head->next;
    while (p != NULL && p->data != target)
    {
        p = p->next;
    }
    if (p == NULL) return;

    // (2) 创建新节点
    DNode *new_node = create_d_node(data);

    // (3) 新节点先接住前驱和后继
    new_node->prev = p;
    new_node->next = p->next;

    // (4) 后继回指新节点
    if (p->next != NULL)
    {
        p->next->prev = new_node;
    }

    // (5) 前驱指向新节点
    p->next = new_node;
}

这里的顺序和头插法完全一致：先把新节点自己的 prev、next 设置好，再修改旁边节点的链接。若 p 原本是尾节点，p->next == NULL，则步骤④跳过，步骤⑤直接把新节点挂到尾部；因此这段代码也自然兼容“插在最后一个节点之后”的情况。

2.4.2 删除操作

双链表删除的一个巨大优势是：找到了目标节点后，可以直接删除它，不需要再遍历找前驱——因为前驱就记录在 prev 里。

void delete_node(DNode *head, int data)
{
    DNode *p = head->next;                  // (1) 从第一个数据节点开始
    while (p != NULL && p->data != data)    // (2) 遍历查找目标节点
    {
        p = p->next;
    }

    if (p == NULL) return;                  // (3) 没找到，直接返回

    // (4) 前驱跳过 p；前驱可能是头节点
    p->prev->next = p->next;
    if (p->next != NULL)
    {
        p->next->prev = p->prev;            // 后继反向跳过 p
    }

    // (5) 释放目标节点
    free(p);
}

和单链表不同，双链表的遍历直接找目标节点本身，而不是找它的前驱——因为目标节点自己就存了 prev，删除时不需要通过前驱来间接访问。

遍历从头节点的下一个（第一个数据节点）开始，逐个检查 p->data == data。如果走到末尾（p == NULL）都没找到，说明链表中没有这个值，直接返回。

找到目标节点后，执行“跳过“操作——让前驱和后继越过目标节点直接相连。p->prev->next = p->next 让前驱的 next 跳过 p，指向 p 的后继。这行对第一个数据节点也成立——此时 p->prev 就是头节点，所以不需要特殊处理。如果 p 不是尾节点，还需要让后继的 prev 回指 p->prev，完成双向的“绕过“。

最后 free(p) 释放目标节点。注意 free 必须在所有链接修改完成之后——因为修改链接时需要读取 p->prev 和 p->next，如果先释放了 p，这些指针就变成了野指针。

💡 和单链表删除对比

单链表删除时，需要找到目标节点的前驱（while (p->next != NULL && p->next->data != data)）。双链表因为每个数据节点都存了前驱的地址，所以直接找到目标节点本身即可，然后通过 prev 拿到前驱。这使得代码逻辑更清晰。

2.4.3 查找操作

双链表的正向查找和单链表完全一样——从 head->next 出发，沿 next 逐个比较。但因为多了 prev 指针，双链表还能反向查找：如果知道目标靠近尾部，可以先走到末尾再沿 prev 往回找。

// 正向查找（和单链表相同）
DNode *find_d_node(DNode *head, int data)
{
    DNode *p = head->next;
    while (p != NULL && p->data != data)
        p = p->next;
    return p;
}

// 反向查找：先从 tail 出发沿 prev 向前
// 适用于目标靠近链表尾部的场景
DNode *find_d_node_reverse(DNode *tail, int data)
{
    DNode *p = tail;
    while (p != NULL && p->data != data)
        p = p->prev;
    return p;
}

正向和反向查找的时间复杂度都是 O(n)——prev 指针让遍历方向自由了，但不会让查找更快（除非你知道目标靠近哪一端，选择从近端出发可以减少步数，但最坏情况不变）。

2.4.4 修改操作

双链表的修改和单链表完全一样——找到目标节点后，直接覆写 p->data。双链表多出来的 prev 指针只在删除和反向遍历时发挥作用，修改数据域不需要动指针。

bool update_d_node(DNode *head, int old_data, int new_data)
{
    DNode *p = find_d_node(head, old_data);
    if (p == NULL) return false;
    p->data = new_data;     // 只改数据，不动指针
    return true;
}

找到之后，p->data = new_data 一次赋值就是 O(1)。加上查找阶段，整体 O(n)。

2.4.5 遍历操作

// 正向遍历（和单链表完全一样）
void print_forward(DNode *head)
{
    DNode *p = head->next;
    printf("NULL ←→ ");
    while (p != NULL)
    {
        printf("%d ←→ ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

// 反向遍历（先走到尾，再往回走）
void print_backward(DNode *head)
{
    if (head->next == NULL)
    {
        printf("NULL\n");
        return;
    }

    // 先走到最后一个节点
    DNode *p = head->next;
    while (p->next != NULL)
    {
        p = p->next;
    }

    // 从尾向头遍历
    printf("NULL ←→ ");
    while (p != head)
    {
        printf("%d ←→ ", p->data);
        p = p->prev;    // 沿着 prev 往回走
    }
    printf("NULL\n");
}

反向遍历分两段。第一段和单链表尾插法找最后一个节点一样——p 从 head->next 出发，沿着 next 走到末尾（p->next == NULL 时停下），此时 p 就是最后一个数据节点。

第二段从尾向头走。每步打印当前节点的数据，然后 p = p->prev 退回前一个节点。终止条件是 p == head——当 p 退回到头节点时，说明所有数据节点都访问完了，循环结束。头节点本身不存数据，不需要打印。

释放操作和单链表完全相同——沿着 next 逐个 free 即可，不必关心 prev。

2.4.6 时间复杂度分析

双链表的大部分操作和单链表相同：创建 O(1)、头插 O(1)、尾插 O(n)、按值中间插入 O(n)、遍历 O(n)。中间插入如果已经拿到前驱节点地址，真正接入新节点的动作是 O(1)；按值插入仍要先查找位置，所以整体是 O(n)。这里重点分析它和单链表的两个关键差异。

差异一：删除不再依赖前驱

单链表删除时，必须找到目标节点的前驱：

// 带头节点的单链表删除 —— while 检查 p->next->data，为了停在"目标前面"
Node *p = head;
while (p->next != NULL && p->next->data != data) // O(n)
    p = p->next;                                  // p 停在目标前面
if (p->next != NULL)
{
    Node *temp = p->next;
    p->next = temp->next;                           // 绕过目标
    free(temp);
}

双链表每个节点都存了 prev，可以直接定位到目标本身：

// 双链表删除 —— while 检查 p->data，找到目标本身即可
DNode *p = head->next;
while (p != NULL && p->data != data)               // O(n)：查找
    p = p->next;

if (p != NULL)                                     // 找到了
{
    p->prev->next = p->next;                       // O(1)：前驱绕过
    if (p->next != NULL)
        p->next->prev = p->prev;                   // O(1)：后继回指
    free(p);                                       // O(1)
}

两者的查找都是 O(n)，但双链表找到后直接通过 p->prev 获取前驱，不需要像单链表那样“提前停在前面“。在已知节点地址的前提下（比如遍历过程中顺手删除），双链表删除是真正的 O(1)——连遍历找前驱都省了。

差异二：支持反向遍历

// 反向遍历：先处理空链表，再走到末尾并沿 prev 往回走
if (head->next != NULL)
{
    DNode *p = head->next;
    while (p->next != NULL) p = p->next; // O(n)：走到末尾
    while (p != head)
    {
        printf("%d ", p->data);
        p = p->prev;                      // 沿 prev 往回走
    }
}

单链表只能单向走，双链表可以双向走。需要从后往前处理的场景（如撤销操作的历史记录），双链表是自然的选择。

双链表 vs 单链表 vs 数组的总览：

空间开销：双链表每个节点存 prev 和 next 两个指针，比单链表多一个指针。指针的具体字节数取决于平台，不能固定写成 8 字节。额外空间换来了“删除不依赖遍历找前驱”和“双向遍历”——值不值得，要看场景。

三方完整的操作效率对比（包括查找、空间、缓存等所有维度）见第十九章 总结与对比。

2.5 链式存储的本质

单双链表只是实现，不是本质

学完单链表和双链表，很容易产生一个印象：链表就是“有一个 next 指针“或者“有 next 和 prev 两个指针“的结构。但这是一个常见的误解——

单链表和双链表只是链式存储的两种具体实现，链式存储的本质不在“有几个指针“，而在“记录节点之间的关系信息“。

本质是什么

链式存储的核心思想只有一句话：每个节点除了存数据，还携带“其他节点在哪“的信息。

这个“信息“是什么形式，取决于你需要什么：

它们形式各异，但底层逻辑完全一致——节点携带指针，指针表达关系。 单链表和双链表只是这个思想最常用的两种形态。

不被“单“和“双“框住

如果把思维框死在“链表只有单链表和双链表“里，就会错过链式存储的真正威力。链式存储的自由度非常高：

• 可以只记后继（单链表）——最简单，够用就好。
• 可以前驱后继都记（双链表）——每节点多花一个指针的空间，换来双向能力和已知节点时的 O(1) 删除。
• 可以记多个后继——这就是树（一个节点指向多个子节点）。
• 可以记任意节点的关系——这就是图（节点之间任意连线）。

沿着这条线索看，树和图本质上也是链式存储思想的延伸——只不过从“一对一的关系“（每个节点一个后继），变成了“一对多“（树）甚至“多对多“（图）。数据结构从线性到非线性的跨越，正是在指针记录的关系信息上做了扩展。

核心认知：不要把链表等价于“单链表“或“双链表“。链式存储的本质是用指针记录节点间的关系，几个指针、指向谁，都是可以根据需求自由组合的。单/双链表只是这种思想在“一对一线性关系“下的两种最常用实践。

三、本章小结

本章围绕物理存储层——数据在内存中到底怎么放——深入学习了两种最基本的存储方式：

数组——连续存储的代表。CRUD 分析表明：按下标访问 O(1) 是其最大优势；插入和删除因搬移数据而 O(n)。适合“数据量确定、主要操作为读取和遍历“的场景。

单链表——链式存储的基础形态，只记后继。头插 O(1)，但随机访问和尾插需要遍历 O(n)。适合“频繁增删、数据量不确定“的场景。

双链表——在单链表基础上增加前驱指针。指针字段的开销增加，换来双向遍历和已知节点地址时 O(1) 删除；如果只知道值，仍要先用 O(n) 查找。

链式存储的本质——单链表和双链表只是实现形式。核心思想是“每个节点携带其他节点的位置信息“，用指针表达节点间的关系。这个思想延伸出去就是树和图——数据结构从线性到非线性的跨越。

从下一章开始，我们将在连续存储和链式存储的基础上“加规则“，构造出功能各异的抽象数据结构——栈、队列和环形队列。