链表

概念讲解

什么是链表？

链表是一种链式存储的线性数据结构，通过指针将各个节点连接起来。

链表 vs 数组

特性 数组 链表
存储方式 连续内存 分散内存
随机访问 O(1) O(n)
插入删除 O(n) O(1)
空间 固定 动态

单链表

节点结构

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

数组模拟（竞赛常用）

1234567891011121314151617181920212223242526const int N = 100005;
int e[N], ne[N];  // 值，next 指针
int head, idx;    // 头指针，当前可用位置

void init() {
    head = -1;
    idx = 0;
}

void insert_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

void insert(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

void remove(int k) {
    ne[k] = ne[ne[k]];
}

双链表

1234567891011121314151617181920212223const int N = 100005;
int e[N], l[N], r[N];  // 值，左指针，右指针
int idx;

void init() {
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

void insert(int k, int x) {
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

考点分析

初赛考查方式

  1. 选择题： 链表特性
  2. 程序阅读： 链表操作
  3. 编程题： 链表应用

常见考点

  • 链表与数组的区别
  • 链表插入删除
  • 数组模拟链表

例题精讲

例题 1：链表操作

题目： 链表的特点是什么？

解答：

链表不需要连续内存，插入删除效率高，但不支持随机访问。

练习题

  1. 用数组模拟实现单链表。
查看答案
1234567891011121314151617181920212223242526const int N = 100005;
int e[N], ne[N];  // 值，next 指针
int head, idx;    // 头指针，当前可用位置

void init() {
    head = -1;
    idx = 0;
}

void insert_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

void insert(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

void remove(int k) {
    ne[k] = ne[ne[k]];
}
  1. 链表和数组的主要区别是什么？
查看答案
特性 数组 链表
存储方式 连续内存 分散内存
随机访问 O(1) O(n)
插入删除 O(n) O(1)
空间 固定大小 动态分配
缓存友好 好 差
  1. 实现链表的反转。
查看答案
12345678910111213141516171819202122232425// 迭代方法
Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* curr = head;
    
    while (curr) {
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

// 递归方法
Node* reverse(Node* head) {
    if (!head || !head->next) return head;
    
    Node* newHead = reverse(head->next);
    head->next->next = head;
    head->next = nullptr;
    
    return newHead;
}

易错点

⚠️ 注意：

  1. 数组模拟链表是竞赛常用技巧
  2. 头指针初始化为 -1
  3. 注意指针的更新顺序
  4. 链表不支持随机访问