单链表

为什么需要单链表

顺序表虽然支持随机访问，但插入和删除时需要大量移动元素，且需要预先分配连续的存储空间。当数据量不确定、插入删除频繁时，顺序表的效率和灵活性就成了瓶颈。

单链表通过指针将分散在内存各处的结点串联起来，不需要连续的存储空间，插入和删除时只需修改指针，无需移动数据元素。408 考研中，单链表是线性表章节的核心考点，也是理解更复杂链式结构（双链表、循环链表、静态链表）的基础。

核心思想

单链表的核心特点：

• 逻辑顺序与物理顺序不一致：元素在内存中不连续存放，通过指针链接
• 顺序访问：只能从头结点出发，沿指针链逐个访问，不支持随机访问
• 动态分配：按需申请结点空间，不会浪费也不会溢出（除非内存耗尽）

结点结构定义：

typedef struct LNode {
    ElemType data;       // 数据域
    struct LNode *next;  // 指针域，指向下一个结点
} LNode, *LinkList;

单链表在内存中的存储方式：

头指针 → [data|next] → [data|next] → [data|next] → NULL
          结点1         结点2         结点3

带头结点 vs 不带头结点：408 考研中默认使用带头结点的单链表。头结点的数据域不存储有效数据，它的引入使得在第一个元素之前插入和删除第一个元素时，操作与其他位置统一，简化了代码逻辑。

头插法与尾插法对比

交互可视化

通过下方的交互动画，你可以逐步观察单链表的执行过程：

加载可视化中...

操作详解

头插法建表

每次将新结点插入到头结点之后（即链表的最前端）。建表结果与输入顺序相反，因此头插法也叫逆序建表。

关键步骤：

1. 创建头结点，L->next = NULL
2. 对每个待插入元素，创建新结点 s
3. s->next = L->next（新结点指向原来的第一个结点）
4. L->next = s（头结点指向新结点）

LinkList HeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));  // 创建头结点
    L->next = NULL;                        // 初始为空表
    scanf("%d", &x);
    while (x != 9999) {                   // 9999 作为输入结束标志
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

考点提醒：头插法的结果是输入序列的逆序，这个特性常用于链表逆置。

尾插法建表

每次将新结点插入到链表的尾部。建表结果与输入顺序一致，因此尾插法也叫正序建表。需要维护一个尾指针 r 始终指向当前链表的最后一个结点。

关键步骤：

1. 创建头结点，尾指针 r 指向头结点
2. 对每个待插入元素，创建新结点 s
3. r->next = s（尾结点指向新结点）
4. r = s（尾指针后移到新结点）
5. 全部插入后，r->next = NULL

LinkList TailInsert(LinkList &L) {
    LNode *s, *r;
    int x;
    L = (LinkList)malloc(sizeof(LNode));  // 创建头结点
    r = L;                                 // 尾指针初始指向头结点
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;                        // 尾结点指针置空
    return L;
}

对比：头插法不需要尾指针，代码更简洁；尾插法需要额外维护尾指针，但能保持输入顺序。两种方法的时间复杂度都是 O(n)。

插入操作

在第 i 个位置插入新元素时，需要先找到第 i-1 个结点（前驱结点），然后修改指针完成插入。与顺序表不同，链表插入不需要移动元素，只需修改两个指针。

关键步骤：

1. 找到第 i-1 个结点 p（从头结点出发遍历 i-1 步）
2. 创建新结点 s，赋值 s->data = e
3. s->next = p->next（新结点指向原第 i 个结点）
4. p->next = s（前驱结点指向新结点）

// 在第 i 个位置插入元素 e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e) {
    if (i < 1) return false;
    LNode *p = L;               // p 指向头结点，相当于第 0 个结点
    int j = 0;
    while (p != NULL && j < i - 1) {  // 找到第 i-1 个结点
        p = p->next;
        j++;
    }
    if (p == NULL) return false;       // i 值不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

注意：第 3、4 步的顺序不能颠倒！如果先执行 p->next = s，就丢失了原来第 i 个结点的地址。这是考研选择题的常见陷阱。

删除操作

删除第 i 个位置的元素时，需要先找到第 i-1 个结点（前驱结点），然后修改指针跳过被删除结点，最后释放其内存空间。

关键步骤：

1. 找到第 i-1 个结点 p
2. q = p->next（q 指向待删除结点）
3. p->next = q->next（前驱结点指向被删除结点的后继）
4. free(q)（释放被删除结点的内存）

// 删除第 i 个位置的元素，用 e 返回其值
bool ListDelete(LinkList &L, int i, ElemType &e) {
    if (i < 1) return false;
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i - 1) {  // 找到第 i-1 个结点
        p = p->next;
        j++;
    }
    if (p == NULL || p->next == NULL) return false;
    LNode *q = p->next;               // q 指向被删除结点
    e = q->data;                       // 取出被删除元素的值
    p->next = q->next;                // 跳过被删除结点
    free(q);                           // 释放内存
    return true;
}

与顺序表对比：顺序表删除需要移动 O(n) 个元素，而链表删除只需修改一个指针（O(1)），但找到前驱结点需要 O(n) 时间遍历。

逆置

将单链表中所有结点的顺序反转。这是 408 考研的高频算法题，常见解法有两种：

方法一：头插法逆置（推荐）

核心思想：将原链表的结点依次取下，用头插法插入到头结点之后，自然实现逆序。

// 原地逆置单链表（头插法）
void ReverseList(LinkList &L) {
    LNode *p = L->next;   // p 指向第一个数据结点
    LNode *r;              // r 用于保存 p 的后继
    L->next = NULL;        // 头结点断开，变成空表
    while (p != NULL) {
        r = p->next;       // 暂存 p 的后继
        p->next = L->next; // 头插：p 指向当前第一个结点
        L->next = p;       // 头结点指向 p
        p = r;             // p 后移到下一个待处理结点
    }
}

方法二：指针反转法

核心思想：使用三个指针 pre、p、r，遍历链表的同时将每个结点的 next 指针反转指向前驱。

void ReverseList2(LinkList &L) {
    LNode *pre, *p = L->next, *r;
    if (p == NULL) return;
    pre = NULL;
    while (p != NULL) {
        r = p->next;       // 暂存后继
        p->next = pre;     // 反转指针
        pre = p;           // pre 后移
        p = r;             // p 后移
    }
    L->next = pre;         // 头结点指向新的第一个结点
}

考场建议：两种方法时间复杂度都是 O(n)，空间复杂度都是 O(1)。头插法思路更直观、不容易写错，推荐优先使用。

复杂度分析

操作	时间复杂度	说明
头插法建表	O(n)	每个结点插入 O(1)，共 n 个结点
尾插法建表	O(n)	维护尾指针，每个结点插入 O(1)
按位查找	O(n)	需从头遍历到第 i 个结点
按值查找	O(n)	最坏需遍历整个链表
插入（已知前驱）	O(1)	只需修改两个指针
插入（按位序）	O(n)	查找前驱 O(n) + 插入 O(1)
删除（已知前驱）	O(1)	只需修改一个指针
删除（按位序）	O(n)	查找前驱 O(n) + 删除 O(1)
逆置	O(n)	遍历一次链表

空间复杂度：O(1)，所有操作只需常数级辅助变量（指针）。

与顺序表对比：顺序表按位查找 O(1) 优于链表的 O(n)；但链表在已知前驱的情况下插入/删除 O(1)，优于顺序表的 O(n) 元素移动。选用哪种结构取决于应用场景中查找与增删的频率。

考研高频考点

• ⭐ 头插法与尾插法的区别及代码实现（选择题/代码题高频）
• ⭐ 链表逆置的算法设计（算法大题常考）
• ⭐ 单链表 vs 顺序表的优缺点对比（简答题必考）
• ⭐ 插入/删除操作中指针修改的顺序（选择题陷阱）
• ⭐ 带头结点与不带头结点的区别及各自优劣
• 按位查找与按值查找的时间复杂度
• 链表的存储密度（< 1，因为每个结点需要额外存储指针）
• 头插法建表结果为输入的逆序（选择题常考）

相关文章

• 顺序表（数组）
• 单链表
• 双链表
• 循环链表
• 静态链表

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...