本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-08 20:37:47

链表

一、链表基础知识

1. 链表特性

• 动态数据结构，节点通过指针连接
• 支持O(1)时间的插入/删除操作
• 不支持随机访问（访问效率O(n)）
• 两种常见实现方式：数组模拟（静态链表）、STL list（双向链表）

2. 链表类型对比

二、数组模拟链表

1. 单向链表模板

const int MAXN = 1e6+5;
struct Node {
    int val;
    int next;
} node[MAXN];
int idx; \/\/ 当前可用节点索引

\/\/ 初始化
void init() {
    node[0].next = -1; \/\/ 头节点
    idx = 1;
}

\/\/ 在pos节点后插入新节点
void insert(int pos, int x) {
    node[idx].val = x;
    node[idx].next = node[pos].next;
    node[pos].next = idx++;
}

\/\/ 删除pos节点的后继节点
void remove(int pos) {
    node[pos].next = node[node[pos].next].next;
}

2. 双向链表模板

const int MAXN = 1e6+5;
struct Node {
    int val;
    int prev, next;
} node[MAXN];
int idx;

void init() {
    node[0].next = 1;  \/\/ 头节点
    node[1].prev = 0;  \/\/ 尾节点
    idx = 2;
}

\/\/ 在pos节点右侧插入
void insert(int pos, int x) {
    node[idx] = {x, pos, node[pos].next};
    node[node[pos].next].prev = idx;
    node[pos].next = idx++;
}

\/\/ 删除pos节点
void remove(int pos) {
    node[node[pos].prev].next = node[pos].next;
    node[node[pos].next].prev = node[pos].prev;
}

三、STL list应用

1. 基本操作

#include <list>
using namespace std;

list<int> lst;
list<int>::iterator it;

lst.push_back(x);    \/\/ 尾部插入
lst.push_front(x);   \/\/ 头部插入
lst.pop_back();      \/\/ 删除尾部
lst.pop_front();     \/\/ 删除头部
it = lst.begin();    \/\/ 获取起始迭代器
advance(it, k);      \/\/ 迭代器移动k步
lst.insert(it, x);   \/\/ 在迭代器位置插入
lst.erase(it);       \/\/ 删除迭代器指向元素

四、基础例题实现

例题1：洛谷P1160 队列安排

题目描述：实现双向链表操作，支持：

1. 将i号同学插入到k号同学左边/右边
2. 删除指定同学

数组模拟实现

#include <iostream>
using namespace std;

const int MAXN = 1e5+5;
struct Node { int prev, next; } node[MAXN];
bool exist[MAXN];

void init() {
    node[0].next = 1;
    node[1].prev = 0;
}

void insert(int k, int x, int pos) { \/\/ pos:0左 1右
    if(pos == 0) {
        node[x].prev = node[k].prev;
        node[x].next = k;
        node[node[k].prev].next = x;
        node[k].prev = x;
    } else {
        node[x].prev = k;
        node[x].next = node[k].next;
        node[node[k].next].prev = x;
        node[k].next = x;
    }
    exist[x] = true;
}

void remove(int x) {
    if(!exist[x]) return;
    node[node[x].prev].next = node[x].next;
    node[node[x].next].prev = node[x].prev;
    exist[x] = false;
}

STL list实现

#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

unordered_map<int, list<int>::iterator> mp;
list<int> lst;

int main() {
    lst.push_back(1);
    mp[1] = lst.begin();
    
    int n, k, p, m, x;
    cin >> n;
    for(int i=2; i<=n; ++i) {
        cin >> k >> p;
        auto it = mp[k];
        if(p == 1) ++it;
        mp[i] = lst.insert(it, i);
    }
    \/\/ ...后续删除操作类似...
    return 0;
}

例题2：洛谷P1996 约瑟夫问题

题目描述：n个人围成环，从第1个开始报数，数到m的人出列

数组模拟实现

int cur = 0;
for(int i=0; i<n; ++i){
    for(int j=1; j<m; ++j)
        cur = node[cur].next;
    cout << node[cur].next << " ";
    remove(cur);
    cur = node[cur].next;
}

STL list实现

list<int> lst;
for(int i=1; i<=n; ++i) lst.push_back(i);

auto it = lst.begin();
while(!lst.empty()){
    for(int i=1; i<m; ++i){
        ++it;
        if(it == lst.end()) it = lst.begin();
    }
    cout << *it << " ";
    it = lst.erase(it);
    if(it == lst.end() && !lst.empty()) 
        it = lst.begin();
}

五、进阶练习题

1. 洛谷P2058 海港（STL list维护时间窗口）
2. Codeforces 706D - Vasiliy's Multiset（双向链表维护有序集合）
3. AtCoder ABC237E - Skiing（链表优化BFS）
4. 洛谷P4001 [ICPC-Beijing 2006]狼抓兔子（双向链表维护平面图）
5. Codeforces 1154E - Two Teams（双向链表快速删除）

六、使用技巧

1. 数组模拟常用优化：

   • 使用「索引0」作为头节点
   • 预先分配足够空间（1e6级别）
   • 用exist数组标记有效节点

2. STL list注意事项：

   • 迭代器失效问题
   • 结合unordered_map实现快速查找
   • 谨慎处理空链表和边界情况

3. 性能对比：

   • 数组模拟：访问O(1)，适合频繁修改
   • STL list：代码简洁，适合简单操作

七、常见错误

1. 数组模拟时忘记更新相邻节点的指针
2. STL list在循环中错误处理迭代器
3. 没有正确处理空链表的情况
4. 数组模拟时未初始化头尾节点
5. 时间复杂度误判（多次遍历链表）