C / C++ / 系统课时
在指定位置插入节点
在指定位置插入节点
单链表按位置插入的关键,不是“创建一个节点”,而是先找到正确的前驱,再按安全顺序改写指针。本节用从 0 开始的位置编号实现通用插入,并覆盖头部、尾部、空链表和非法位置。
学习目标
- 理解位置编号与前驱节点之间的关系
- 正确处理头插、尾插和越界插入
- 能写出不断链、可验证的 C 语言插入函数
先定义位置语义
下面统一使用 0-based 位置:位置 0 表示插到当前头节点之前,位置 1 表示插到原第 0 个节点之后。若链表长度为 n,合法插入位置是 0 到 n,因此位置 n 正好表示尾插。
这一定义很重要,因为“插入位置”和“访问已有节点的位置”边界不同:访问节点时最大下标是 n - 1,插入时还允许 n。
找到前驱再改指针
当位置大于 0 时,需要遍历到位置 position - 1 的前驱节点 prev。找到后,新节点应先接住原后继,再让前驱指向新节点:
new_node->next = prev->next,然后 prev->next = new_node。

如果先把 prev->next 改成新节点,却没有提前保存原来的后继,新节点就无法再连接到链表后半段。因此,先接后继,再改前驱 是最稳妥的顺序。
完整实现
下面的 insert_at 返回 true 表示插入成功,返回 false 表示位置非法或内存分配失败。它允许空链表在位置 0 插入第一个节点。
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
bool insert_at(Node **head, size_t position, int value) {
if (head == NULL) {
return false;
}
if (position == 0) {
Node *new_node = malloc(sizeof(*new_node));
if (new_node == NULL) {
return false;
}
new_node->value = value;
new_node->next = *head;
*head = new_node;
return true;
}
Node *prev = *head;
for (size_t i = 1; i < position && prev != NULL; ++i) {
prev = prev->next;
}
if (prev == NULL) {
return false;
}
Node *new_node = malloc(sizeof(*new_node));
if (new_node == NULL) {
return false;
}
new_node->value = value;
// 先保存原后继关系,再让前驱改指向新节点。
new_node->next = prev->next;
prev->next = new_node;
return true;
}
void print_list(const Node *head) {
for (const Node *p = head; p != NULL; p = p->next) {
printf("%d", p->value);
if (p->next != NULL) {
printf(" -> ");
}
}
printf("\n");
}
void free_list(Node *head) {
while (head != NULL) {
Node *next = head->next;
free(head);
head = next;
}
}
int main(void) {
Node *head = NULL;
insert_at(&head, 0, 10);
insert_at(&head, 1, 30);
insert_at(&head, 1, 20);
insert_at(&head, 3, 40);
print_list(head);
bool ok = insert_at(&head, 5, 99);
printf("insert position 5: %s\n", ok ? "success" : "invalid position");
free_list(head);
return 0;
}预期输出
10 -> 20 -> 30 -> 40
insert position 5: invalid position边界为什么这样处理
头插没有前驱节点,所以必须单独修改 *head。尾插虽然没有后继节点,但前驱节点存在,此时 prev->next 原本就是 NULL,通用逻辑可以直接完成插入。
非法位置的判断也应发生在真正修改链表之前。例如长度为 4 的链表允许位置 4,但位置 5 必须失败;失败时链表保持原样。这样调用者可以根据返回值决定是否提示用户或重试。
复杂度与使用时机
头插只需常数时间,时间复杂度为 ;一般位置需要从头遍历到前驱,时间复杂度为 。除新节点本身外,算法只使用常数个指针变量。
当程序频繁按下标访问或在尾部插入时,单链表未必是最佳结构;但在已经持有前驱指针、需要局部插入的场景中,单链表只需修改两个指针,操作非常直接。