08-基础算法/04-链表

链表

链表是一种链式存储的线性数据结构，每个节点包含数据和指向下一节点的指针。

单向链表节点

struct Node
{
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

基本操作

操作	说明
插入节点	修改前驱的 next 指针，新节点的 next 指向后继
删除节点	将前驱的 next 指向后继
遍历	从头节点开始，依次访问 next
查找	从头节点开始遍历，找到目标值

用数组模拟链表

O（编程竞赛）中常用数组模拟链表，避免指针操作，速度更快：

const int MAXN = 100005;
int val[MAXN];  // 节点值
int nxt[MAXN];  // 下一个节点的下标
int head = 0;   // 头节点下标（0 表示空）

// 在节点 p 后插入新节点 x
int tot = 0;
void insert(int p, int x)
{
    tot++;
    val[tot] = x;
    nxt[tot] = nxt[p];
    nxt[p] = tot;
}

// 删除节点 p 的后一个节点
void remove(int p)
{
    nxt[p] = nxt[nxt[p]];
}

应用场景

• 需要频繁在中间插入/删除的场景
• 邻接表存图（链式前向星的基础）
• 链表模拟（如约瑟夫问题）