链表

学习笔记

链表

一、数据结构概念

1.1 什么是数据结构

同一个数据，用不同的数据结构去存，读写效率会差很多。 > 所以"选择合适的数据结构"是程序设计的第一步。

1.2 常见数据结构的分类

数据结构按"数据元素之间是否是一对一的关系"，大致分成两类：
数据结构 ├── 线性表（一对一）：数组、链表、栈、队列 └── 非线性表（一对多/多对多）：树、图

本节的链表属于线性表。

二、线性表

2.1 概念

（1）线性表

线性表：数据元素之间是一对一的先后关系——除了第一个和最后一个，每个元素只有一个前驱、一个后继。
就像一条线串起来的一串珠子：
[元素1] → [元素2] → [元素3] → ... → [元素n]
首元素和尾元素之外的每个元素，都只有一个前驱、一个后继。
常见线性表：
| 线性表 | 存储方式 | | — | — | | 数组 | 连续内存，靠下标访问 | | 链表 | 分散内存，靠指针串联 | | 栈 | 先进后出（LIFO） | | 队列 | 先进先出（FIFO） |

2.2 存取数据性能对比

💡 一句话总结： > - 数组：查得快（按下标直接取），插删慢（要搬家）； > - 链表：查得慢（要顺着指针找），插删快（只改指针）。

2.3 为什么需要链表

数组的两个痛点，链表正好解决：

数组大小固定：定义时要定死长度，太大浪费、太小不够；链表按需申请节点。 2. 数组插删要搬家：在中间插入一个元素，后面所有元素都要后移；链表只改指针。

代价是：链表失去了"按下标直接访问"的能力，查第 k 个元素要从头走 k 步。

三、单向链表

3.1 链表的结构

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

┌─────────┬─────────┐   
│  data   │  next   │   
└─────────┴─────────┘  
``` - **数据域 `data`**：存本节点要保存的值； - **指针域 `next`**：存"下一个节点的地址"。    
整条链表靠 `next` 一个接一个串起来：    
``` head    
| v[1] --> [2] --> [3] --> NULL ```    
> 末尾节点的 `next` 指向 `NULL`（空），表示"链表到此结束"。    
### 3.2 单向链表的代码实现：结构体 + 指针    
```cpp struct Node {    
int data;      // 数据域    
Node *next;    // 指针域，指向下一个节点 };

3.3 遍历链表

for (Node *p = head; p != nullptr; p = p->next) cout << p->data << ' '; cout << endl;}

3.4 插入节点 ★重点

单向链表的插入只有一种通用操作：在节点 p 之后插入一个新节点。不管插在头部、中间还是尾部，都用同一个函数：

Node *node = new Node;   
node->data = x;   
node->next = p->next;   // ① 新节点先接上 p 的后继    
p->next = node;         // ② 再让 p 指向新节点 }

连线过程（图里 [n] 就是代码里的新节点 node）：
插入前，p 指向 b：
[p] --> [b] --> [c]
① node->next = p->next：新节点先接上后继 b

 | [n]  
 ``` **② `p->next = node`**：p 改指向新节点    
 ``` [p] --> [n] --> [b] --> [c] ```    
 > ⚠️ **顺序不能反**：必须先执行 ①（node 接上后继），再执行 ②（p 指向 node）。 > 如果先执行 `p->next = node`，p 和 b 之间的连线就断了，b 后面的整段会**丢失**：    
 ``` [p]          [b] --> [c]     ← b 后面整段失联    
| v[n]   ← 还没接上 b ``` #### 一个函数覆盖所有插入位置    
 `insertNode(x, p)` 是**通用插入**——头插、中间插、尾插**不需要单独写**，只是 `p` 不同：    
 | 想插到哪里 | p 是谁 | 说明 | | --- | --- | --- | | 头部 | 虚拟头节点（一个不存数据的头） | `insertNode(x, 虚拟头)` | | 中间 | 某个中间节点 p | `insertNode(x, p)` | | 尾部 | 最后一个节点 | `insertNode(x, 尾节点)`，此时 `node->next` 自动为 `NULL` |    
 > 💡 所以插入**只有 `insertNode` 一种**，会这一个函数，头、中、尾都能插。    
 ### 3.5 删除节点 ★重点    
 单向链表删除节点，用的是"**搬值 + 跳过**"的技巧：拿到要删的节点 p 后，把下一个节点的值搬进 p，再让 p 跳过下一个节点并删除它。这样**不需要找到前驱**，O(1) 时间就能删掉。    
 ```cpp // 删除节点 p（不需要知道前驱） void deleteNode(Node *p) {    
p->data = p->next->data;   // ① 把下一个节点的值搬到 p Node *tmp = p->next;       // ② 记下下一个节点    
p->next = p->next->next;   // ③ p 跳过下一个节点    
delete tmp;                // ④ 释放下一个节点 }

连线过程（q 是 p 的下一个节点）：
删除前：
[p] --> [q] --> [b]
① p->data = p->next->data：把 q 的值搬到 p（p 的值变成 q 的值）
②③ p->next = p->next->next：p 跳过 q，直接指向 b

[p] --------> [b]
④ delete tmp：释放 q

效果：p 原来的值没了，p 的位置现在存的是原来 q 的值——等效于删掉了 p。
⚠️ 这个写法要求 p 的后面至少还有一个节点（p->next 不能为 NULL），否则 p->next->data 会出错。所以它不能删除最后一个节点（删尾节点得从头遍历找前驱，O(n)）。但它能删除头节点——因为 head 指针不动，只是把头节点的值换成了后继的值。

四、双向链表

4.1 双向链表的概念

单向链表只能从前往后走，想找某个节点的前驱就得从头再走一遍。双向链表给每个节点多加一个指针 pre，指向前一个节点，于是前后都能走。

┌──────┬──────┬──────┐   
│ pre  │ data │ next │   
└──────┴──────┴──────┘

pre：指向前一个节点； - next：指向后一个节点。
串联起来（<--> 表示两个方向都能走）：

[1] <--> [2] <--> [3]

4.2 双向链表的代码实现：结构体 + 指针

int data; Node *pre;    // 指向前一个节点    
Node *next;   // 指向后一个节点    
Node(int x) : data(x), pre(nullptr), next(nullptr) {}};

4.3 创建链表（头插法）

    if (n == 0) return nullptr;   
    Node *head = new Node(arr[0]);   
    for (int i = 1; i < n; i++) {   
       Node *node = new Node(arr[i]);   
node->next = head;   // 新节点接上原头    
head->pre = node;    // 原头的 pre 接上新节点    
head = node;         // 头指针前移    
    }   
    return head;  
}

头插法得到的链表顺序和输入顺序相反（输入 1 2 3 4 → 输出 4 3 2 1）。

4.4 插入节点 ★重点

在节点 p 之后插入值为 x 的新节点：

if (p == nullptr) return;   
Node *node = new Node(x);   
node->next = p->next;       // ① node 接上 p 的后继    
if (p->next != nullptr)     // ② 原后继的 pre 接上 node（若存在）    
p->next->pre = node;    // ③ p 接上 node node->pre = p; p->next = node;          // ④ node 接上 p }

连线过程（图里 [n] 就是新节点 node，[b] 是 p 的后继）：
插入前：
[p] <--> [b]
插入后：
[p] <--> [n] <--> [b]
其中维护了四条指针：

node->next = b（node 接上后继 b） 2. b->pre = node（b 的前驱改指 node） 3. p->next = node（p 的后继改指 node） 4. node->pre = p（node 的前驱指向 p）

💡 双向链表插入要维护四条指针，比单向链表麻烦，但换来"能往回走"的能力。

4.5 删除节点 ★重点

双向链表删除节点，要分三种情况处理：头节点、尾节点、中间节点。

// ① p 是头节点    
 if (p == *head_ref) {   
*head_ref = p->next;              // 头指针后移    
if (*head_ref != nullptr)         // 新头的 pre 置空    
         (*head_ref)->pre = nullptr;   
      delete p;   
      return;   
  }    
// ② p 是尾节点    
 if (p->next == nullptr) {   
p->pre->next = nullptr;           // 前驱的 next 置空    
     delete p; return;   
 }    
// ③ p 是中间节点（掉包法）    
Node *tmp = p->next; p->data = tmp->data;                  // 把后继的值搬到 p p->next = tmp->next;                  // p 跳过后继    
if (tmp->next != nullptr)             // 后继的后继的 pre 接上 p    tmp->next->pre = p; delete tmp;  
}

连线过程：
情况① 删除头节点 p：
删除前： head --> [p] <--> [b]删除后： head --> [b] （b 的 pre 置空）
情况② 删除尾节点 p：
删除前： [t] <--> [p] --> NULL删除后： [t] --> NULL
情况③ 删除中间节点 p（掉包法）：
删除前： [t] <--> [p] <--> [b] ① p->data = b->data 把 b 的值搬进 p② p->next = b->next p 跳过 b③ 删除 b 删除后： [t] <--> [p] <--> ... p 里现在存的是原来 b 的值

💡 参数为什么是 Node **head_ref：删头节点时要修改 head 指针本身，所以传它的地址（二级指针）。

4.6 遍历链表

while (head != nullptr) {   
    cout << head->data << " ";   
    head = head->next;   
}   
cout << endl;}

4.7 完整示例

把创建、插入、删除、遍历串起来，看整体效果：

int arr[] = {1, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]);    
// 1、创建链表（头插法，结果逆序）    
Node *head = createList(arr, n); cout << "创建链表: ";    
printList(head);           // 4 3 2 1    
// 2、在节点 2 后插入 5 Node *p = head->next->next;   // 找到节点 2 insertNode(5, p); cout << "插入5后: ";    
printList(head);           // 4 3 2 5 1    
// 3、删除头结点 4 deleteNode(&head, head); cout << "删除头结点后: ";    
printList(head);           // 3 2 5 1    
// 4、删除尾节点 1 Node *tail = head; while (tail->next != nullptr) tail = tail->next; deleteNode(&head, tail); cout << "删除尾节点后: ";    
printList(head);           // 3 2 5    
// 5、删除中间节点 2（掉包法）    
Node *node = head->next; deleteNode(&head, node); cout << "删除第二个节点后: ";    
printList(head);           // 3 5    
return 0;}

输出结果依次为：4 3 2 1 → 4 3 2 5 1 → 3 2 5 1 → 3 2 5 → 3 5。 > 最后一步删除节点 2（值 2）用的是掉包法：把后继 5 的值搬进来，再删掉后继，所以剩下 3 5。

如果觉得文章对你有用，请随意赞赏

链表

https://www.mcoi.com.cn/archives/wei-ming-ming-wen-zhang-1QQphZcb

作者

Bob

发布于

2026-08-23

更新于