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 插入第一个节点。

c
#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;
}

预期输出

text
10 -> 20 -> 30 -> 40
insert position 5: invalid position

边界为什么这样处理

头插没有前驱节点,所以必须单独修改 *head。尾插虽然没有后继节点,但前驱节点存在,此时 prev->next 原本就是 NULL,通用逻辑可以直接完成插入。

非法位置的判断也应发生在真正修改链表之前。例如长度为 4 的链表允许位置 4,但位置 5 必须失败;失败时链表保持原样。这样调用者可以根据返回值决定是否提示用户或重试。

复杂度与使用时机

头插只需常数时间,时间复杂度为 O(1)O(1);一般位置需要从头遍历到前驱,时间复杂度为 O(n)O(n)。除新节点本身外,算法只使用常数个指针变量。

当程序频繁按下标访问或在尾部插入时,单链表未必是最佳结构;但在已经持有前驱指针、需要局部插入的场景中,单链表只需修改两个指针,操作非常直接。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

在指定位置插入节点

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通