查看“︁08-基础算法/04-链表”︁的源代码


== 链表 ==

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

=== 单向链表节点 ===

<syntaxhighlight lang="cpp">
struct Node
{
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};
</syntaxhighlight>

=== 基本操作 ===

{| class="wikitable"
! 操作 !! 说明
|-
| 插入节点
| 修改前驱的 <code>next</code> 指针，新节点的 <code>next</code> 指向后继
|-
| 删除节点
| 将前驱的 <code>next</code> 指向后继
|-
| 遍历
| 从头节点开始，依次访问 <code>next</code>
|-
| 查找
| 从头节点开始遍历，找到目标值
|}

=== 用数组模拟链表 ===

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

<syntaxhighlight lang="cpp">
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]];
}
</syntaxhighlight>

=== 应用场景 ===

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

[[Category:基础算法]]
[[Category:三三文档]]