第44章 线性表和链表
搜索知识点 /

第44章 线性表和链表

线性表是计算机科学中最基础、最常用的数据结构之一，它是由 nn 个具有相同特性的数据元素组成的有限序列。本章对应 GESP C++ 五级知识块 4：链表，要求掌握单链表、双链表、循环链表的创建、插入、删除、遍历、查找、反转等基本操作，并理解三者的区别。

单链表 / 双向链表 / 循环单链表 结构对比

44.1 线性表的基本概念

44.1.1 定义

线性表是由 n (n≥0)n\ (n \ge 0) 个数据元素 (a1,a2,...,an)(a_1, a_2, ..., a_n) 组成的有限序列，其中：

  • nn 为线性表的长度，n=0n = 0 时称为空表。
  • 数据元素可以是 int、char 等基础类型，也可以是结构体，所有元素类型必须统一。
  • 元素线性关系：除首元素无前驱、尾元素无后继外，其余元素有唯一直接前驱、唯一直接后继。

44.1.2 线性表基础操作

  1. 初始化：创建空线性表
  2. 判空：判断长度是否为 0
  3. 求长度：返回当前元素总数
  4. 获取指定下标元素
  5. 按值查找，返回位置（不存在返回 -1）
  6. 指定位置插入元素
  7. 指定位置删除元素
  8. 清空所有元素

44.2 顺序表（数组实现的顺序存储）

44.2.1 存储结构

连续内存存放元素，同时记录当前长度、最大容量。

#define MAX_SIZE 100
typedef int ElemType;
typedef struct {
    ElemType data[MAX_SIZE];
    int length; // 当前有效元素个数
} SeqList;

44.2.2 核心操作实现

初始化顺序表

void initList(SeqList &L) {
    L.length = 0;
}

插入元素（第 i 个位置插入，位序从 1 开始）

bool insertList(SeqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return false;
    if (L.length >= MAX_SIZE) return false;
    // 后移元素腾出位置
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

删除元素

bool deleteList(SeqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return false;
    e = L.data[i - 1];
    // 元素前移覆盖
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

按值查找

int locateElem(SeqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1; // 返回 1 号位序
        }
    }
    return -1;
}

44.2.3 顺序表优缺点

  • 优点：随机访问 O(1)O(1)，存储无额外指针开销
  • 缺点：插入删除需要大量移动元素 O(n)O(n)；容量固定易溢出/浪费内存

44.2.4 适用场景

查询多、增删少，元素数量固定的场景。

44.3 链表（链式存储）

链表不占用连续内存，依靠指针连接分散节点，每个节点包含数据域与指针域。

44.3.1 单链表

每个节点仅存后继指针，带表头节点简化边界逻辑。

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

初始化空链表（头节点）

void initList(LinkList &L) {
    L = new LNode;
    L->next = nullptr;
}

头插法建表

void createListHead(LinkList &L, int n) {
    L = new LNode;
    L->next = nullptr;
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode;
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
}

尾插法建表

void createListTail(LinkList &L, int n) {
    L = new LNode;
    L->next = nullptr;
    LNode *r = L; // 尾指针
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode;
        cin >> p->data;
        p->next = nullptr;
        r->next = p;
        r = p;
    }
}

指定位置插入

bool insertList(LinkList &L, int i, ElemType e) {
    LNode *p = L;
    int j = 0;
    while (p != nullptr && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == nullptr) return false;
    LNode *s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

指定位置删除

bool deleteList(LinkList &L, int i, ElemType &e) {
    LNode *p = L;
    int j = 0;
    while (p != nullptr && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == nullptr || p->next == nullptr) return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    delete q;
    return true;
}

按值查找节点（遍历）

LNode* locateElem(LinkList L, ElemType e) {
    LNode *p = L->next;
    while (p != nullptr && p->data != e) {
        p = p->next;
    }
    return p;
}

遍历输出

void traverse(LinkList L) {
    LNode *p = L->next;
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

44.3.2 单链表反转（reverse）

反转是 GESP 五级高频操作：将原链表头尾颠倒，返回新的头节点。核心是用三个指针 prev、cur、nxt 边遍历边把 cur->next 指回 prev。

// 反转单链表，返回新的头节点
LNode* reverseList(LinkList L) {
    LNode *prev = nullptr;
    LNode *cur = L->next; // 跳过头节点，反转实际数据链
    while (cur != nullptr) {
        LNode *nxt = cur->next; // 暂存下一个
        cur->next = prev;       // 当前节点指向前一个
        prev = cur;             // prev、cur 前移
        cur = nxt;
    }
    // 重新接回头节点
    LNode *head = new LNode;
    head->next = prev;
    return head;
}

复杂度：只遍历一次，时间 O(n)O(n)，额外空间 O(1)O(1)。

44.3.3 双向链表

节点同时存前驱、后继指针，可双向遍历。

typedef struct DNode {
    ElemType data;
    struct DNode *prior;
    struct DNode *next;
} DNode, *DLinkList;

特点：访问前驱 O(1)O(1)；插入删除需要修改两个指针，代码更复杂。

44.3.4 循环单链表

尾节点 next 指向头节点，形成环形结构；适合约瑟夫环等环形问题。

struct Node {
    int data;
    Node* next;
};

44.3.5 三类链表对比

类型节点指针尾节点指向访问前驱
单链表仅 nextnullptrO(n)O(n)
双向链表prior + nextnullptrO(1)O(1)
循环单链表仅 next头节点O(n)O(n)

44.3.6 链表通用优缺点

  • 优点：动态分配内存，插入删除仅改指针 O(1)O(1)（找到前驱前提下）
  • 缺点：不支持随机访问，查找需遍历 O(n)O(n)；每个节点额外存指针，内存开销更大

44.4 顺序表与链表对比

特性顺序表单链表
内存分布连续分散
随机访问O(1)O(1)O(n)O(n)
中间增删O(n)O(n)O(1)O(1)（找到前驱）
内存开销仅存储数据数据 + 指针
扩容固定容量，需整体复制按需分配

44.5 线性表应用场景

  1. 顺序表：数组、vector、需要频繁下标查询
  2. 单链表：任务队列、临时动态数据
  3. 双向链表：浏览器前进后退、LRU 缓存
  4. 循环链表：约瑟夫问题、环形缓冲队列

44.6 选择题练习

  1. 单链表中，在已知节点 p 后插入新节点 s（已知 p 非空），正确的指针修改顺序是： A. s->next = p->next; p->next = s; B. p->next = s; s->next = p->next; C. s->next = p; p->next = s; D. p->next = s->next; s->next = p;

    查看答案

    答案：A。必须先保存 p 的原后继（s->next = p->next），再把 p->next 指向 s；若先改 p->next = s，原后继链就丢失了。

  2. 单链表反转算法的时间复杂度和额外空间复杂度分别是： A. O(n)O(n) 和 O(1)O(1) B. O(n)O(n) 和 O(n)O(n) C. O(1)O(1) 和 O(1)O(1) D. O(n2)O(n^2) 和 O(1)O(1)

    查看答案

    答案：A。反转只需一次遍历，时间 O(n)O(n)；只用常数个指针变量，额外空间 O(1)O(1)。

  3. 已知单链表 1 -> 2 -> 3 -> nullptr，调用反转后得到的链表头（数据链）是： A. 1 -> 2 -> 3 B. 3 -> 2 -> 1 C. 1 -> 3 -> 2 D. 2 -> 1 -> 3

    查看答案

    答案：B。反转后顺序颠倒，变为 3 -> 2 -> 1。

  4. 与单链表相比，双向链表的主要优势是： A. 占用内存更少 B. 可 O(1)O(1) 访问前驱节点 C. 插入删除更快 D. 支持随机访问

    查看答案

    答案：B。双向链表每个节点带 prior 指针，可 O(1)O(1) 找到前驱；代价是内存开销更大。

  5. 循环单链表区别于普通单链表的关键特征是： A. 没有头节点 B. 尾节点的 next 指向头节点，形成环 C. 每个节点有两个指针 D. 不能遍历

    查看答案

    答案：B。循环单链表尾节点 next 指向头节点，构成闭环，适合环形问题（如约瑟夫环）。

SShowball OI知识手册