链表CSP-J

💡 核心思想

链表是一种动态数据结构，每个节点包含数据和指向下一个节点的指针。在竞赛中，通常用数组模拟链表（因为不需要动态分配内存，速度更快）。常见变体：单链表、双链表、循环链表。

🎯 直觉理解

链表是"手拉手排队"：每个节点存数据 + 指向下一个节点的指针，像链条一样串起来。插入删除只要改指针（$O(1)$），但查找必须从头走（$O(n)$）。

竞赛里常用数组模拟链表：nxt 数组存 i 的下一个下标，配合 pre 数组就是双向链表。删除节点只需改前后指针，比用 vector 的 erase 快得多。

什么时候用：频繁在序列中间插入/删除的场景（如约瑟夫环、某些模拟题）。记住和数组的取舍——数组查得快、链表改得快。

📝 算法流程

1. 数组模拟：val[], nxt[], pre[]
2. 头插法/尾插法
3. 删除：修改前后节点的指针
4. 遍历：从 head 开始沿 nxt 走

$$\text{插入/删除：} O(1)，\text{查找第k个：} O(k)$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
const int N = 100005;
int val[N], nxt[N], head, tot;
void init() { head = -1; tot = 0; }
void insertHead(int x) { val[tot] = x; nxt[tot] = head; head = tot++; }
void insertAfter(int k, int x) { val[tot] = x; nxt[tot] = nxt[k]; nxt[k] = tot++; }
int main() {
    init();
    int n; cin >> n;
    for (int i = 0; i < n; i++) { int x; cin >> x; insertHead(x); }
    for (int i = head; i != -1; i = nxt[i]) cout << val[i] << " ";
    return 0;
}

⚠️ 常见坑点

📚 相关题目