链表（三）任意位置插入与删除

p7（15 分钟）、p8（12 分钟）

先记住两条约定#

位置编号从 1 开始#

位置编号是 1-based。这和前面数组、动态列表的 0-based 下标是两套约定，别混。

合法位置的范围#

以 3 个节点的链表为例：

1
位置 1    →  在开头插入
2
位置 2、3 →  中间插入
3
位置 4    →  在末尾插入
4
位置 5    →  无效位置

长度为 n 的链表，最大合法插入位置是 n+1。

为了简化实现，假定调用者总是给出有效位置，不处理无效或错误情况。

任意位置插入#

核心思路#

1
想在「第 n 个位置」插入
2
→ 先去到「第 (n-1) 个节点」
3
→ ① 先把新节点的链接字段设为第 (n-1) 个节点的链接字段（建立新链路）
4
→ ② 再把第 (n-1) 个节点的链接设为新节点的地址（断开旧链路）

顺序不能反：先建新链路，再断旧链路。

实现#

1
struct node {
2
    int data;
3
    struct node *next;
4
};
5

6
struct node *head;      /* 全局变量 */
7

8
void insert(int data, int n) {
9
    struct node *temp1 = new node;      /* C++ 写法 */
10
    temp1->data = data;
11
    temp1->next = NULL;
12

13
    /* 特殊情况：插到开头 */
14
    if (n == 1) {
15
        temp1->next = head;
16
        head = temp1;
17
        return;                          /* 必须 return */
18
    }
19

20
    /* 其他情况 */
21
    struct node *temp2 = head;
22
    for (int i = 0; i < n - 2; i++) {    /* 循环 n-2 次 */
23
        temp2 = temp2->next;
24
    }
25
    temp1->next = temp2->next;           /* ① 先建新链路 */
26
    temp2->next = temp1;                 /* ② 再断旧链路 */
27
}

循环次数是 n−2#

1
我们要走到「第 (n-1) 个节点」
2
但 temp2 一开始就指向表头（第 1 个节点）
3
所以只需要再走 (n-1) - 1 = n-2 次

1
n = 1  →  走特殊分支，不进循环  →  插到开头
2
n = 2  →  循环 0 次  →  第 (n-1) 个节点就是第 1 个（head）
3
n = 3  →  循环 1 次  →  走到第 2 个节点
4
n = 4  →  循环 2 次  →  走到第 3 个节点

写成 n−1 次会多走一步，越过目标节点。

n == 1 这一支天然覆盖空表#

空表时 head == NULL，temp1->next = head 写入的就是 NULL，然后 return。所以链表为空不用单独处理。

内存分区#

应用程序内存通常分四个部分：

1
代码 / 指令段     所有需要执行的指令                        编译时固定
2
全局变量段        整个程序运行期间都存在的全局变量          编译时固定
3
栈                函数调用执行的所有信息 + 所有局部变量     编译时固定
4
堆 / 自由存储空间  运行时请求的内存（malloc / new）          不固定

前三个部分大小固定，在编译时确定。

head 是全局变量，位于全局变量段，而且任何人都能访问这个变量。

栈帧#

main 开始执行 → 栈中分配一块内存用于 main 的执行，所有局部变量和执行状态保存在此。这块内存叫函数的栈帧。

调用 insert → main 暂停，insert 进栈；insert 有 2 个参数 + 若干局部变量，栈帧会稍大一点。

堆和指针#

new 在堆中创建内存块。用 new 或 malloc 在堆上要内存时，拿不到变量名，访问它的唯一方式是通过一个指针变量——这个指针变量就像遥控器。

函数返回时#

每次函数执行完毕，所有局部变量都会从内存中消失，栈帧的分配与特定的调用相对应。

但堆里的节点不会被清除，除非显式 free / delete。

任意位置删除#

删除要做两件事#

1
① 修正链接，使该节点不再是列表的一部分
2
② 释放该节点所占的空间

只修链接不够。修链接只是把节点从链表里断开，让它没法再被访问，但它仍占着内存。

节点是从动态内存、也就是堆区分配的，在 C/C++ 里用完这块内存后必须显式释放，因为它不会自动被回收。

内存是关键资源，不再需要时不该白白占着。只有释放了，这个节点才真正从内存里消失。

逻辑（一般情况）#

1
要去第 n 个节点，得先到「第 (n-1) 个节点」
2
把第 (n-1) 个节点的链接设为「第 n 个节点的链接」（即第 n+1 个节点）
3
→ 切断这条链接

实现#

这里一共写了三个函数：

insert(value)：总是把值插到列表末尾
print()：打印所有元素
delete(n)：接受要删除节点的位置 n

1
void deleteNode(int n) {
2
    struct node *temp1 = head;
3

4
    /* 特殊情况：删除头节点 */
5
    if (n == 1) {
6
        head = temp1->next;         /* 头节点移到第二个 */
7
        free(temp1);                /* C++ 用 delete temp1; */
8
        return;                     /* 必须 return 或加 else */
9
    }
10

11
    /* 一般情况 */
12
    for (int i = 0; i < n - 2; i++) {   /* 循环 n-2 次，走到第 n-1 个 */
13
        temp1 = temp1->next;
14
    }
15
    struct node *temp2 = temp1->next;   /* temp2 指向第 n 个节点 */
16
    temp1->next = temp2->next;          /* 修正链接：指向第 n+1 个 */
17
    free(temp2);                        /* 释放 */
18
}

释放方式要对应分配方式：malloc 配 free，new 配 delete，别配错。

那个 return 的由来#

对于 n != 1 的情况，不应执行删除头节点这段代码，所以要在此之后加一个 else，或者在针对该条件执行完语句后加上 return。少了它，删完头节点还会继续往下跑。

运行验证#

初始列表 2 4 6 5：

1
删除位置 1          →  4 6 5   ✓
2
删除位置 4（数字 5） →  2 4 6   ✓
3
删除位置 2          →  2 6     ✓

全部正确。

内存模拟（删除位置 3）#

1
temp1 = head（地址 100）
2
n = 3 → 循环恰好执行 1 次 → temp1 移到地址 200（第 2 个节点）
3
temp2 = temp1->next = 150（第 3 个节点）
4
temp1->next = temp2->next → 150 变成 250
5
free(temp2) → 地址 150 的内存块被删除
6
函数结束，temp1、temp2 都被清除
7
最终地址 250 的节点成为第 3 个节点

head 是全局变量，所以不会被清除。

插入 vs 删除#

	插入	删除
走到哪	第 (n-1) 个节点	第 (n-1) 个节点
循环次数	n−2	n−2
关键顺序	先建新链路，再断旧链路	先跨过目标，再释放
必须做的事	创建节点	修正链接 + 显式释放
n==1 特殊处理	`temp1->next = head; head = temp1;`	`head = temp1->next; free(temp1);`

坑#

位置是 1-based，长度为 n 的链表最大合法插入位置是 n+1。
循环次数是 n−2 次，不是 n−1。这是最容易写错的地方。
插入要「先建新链路，再断旧链路」，顺序反了会丢节点。
删除只修链接不够，必须 free / delete，否则内存泄漏。
删头节点之后必须 return 或加 else。