1. 前言

链表：不仅存储 当前元素的数据，还存储着 元素排列顺序

2. 正题

2.1 如何存储节点？

我们可以使用 结构体 数组来存储 链表节点　

struct Node {
    int val; // 可以是 string 或其它复杂的类型
    int nxt;
} node[N];

Tip: 下标顺序不是单链表顺序

val 代表 元素本身，nxt 代表 连接的下一个元素 

2.2 插入元素的方法？

执行此操作的时间复杂度为 O(1)

在 链表 中插入元素

让 链表中的C 的指向为 链表中的A 的原来的指向（也就是B）

让 链表中的A 的指向变为 C

node[C].nxt = node[A].nxt;
node[A].nxt = C;

在 链表 开头插入元素

node[B].nxt = A;

在 链表 末尾插入元素

在 链表 中，末尾元素中的 nxt 始终保持 -1 的状态， 所以在 末尾 插入元素时， 插入元素 的 nxt 要 赋值 为 原末尾 的 nxt 值

node[B].nxt = node[A].nxt;
node[A].nxt = B;

2.3 删除元素的方法？

在 链表 中删除中间元素

让 A 的 nxt 直接指向 C

node[A].nxt = C;

在 链表 中删除队头元素

直接 pass 掉，不调用 队头 即可

在 链表 中删除队尾元素

将原来队尾的 nxt 的值 赋值 到 前一个的 nxt 值 里面

node[A].nxt = node[B].nxt;

3. 引例

Tip: 如果你想自己将这题独立完成做一遍，请自行到文章最底部进行传送

实现一个数据结构，维护一张表（最初只有一个元素 1）。需要支持下面的操作，其中 x 和 y 都是 1 到 10⁶ 范围内的正整数，且保证任何时间表中所有数字均不相同，操作数量不多于 10⁵：

1 x y ：将元素 y 插入到 x 后面；

2 x ：询问 x 后面的元素是什么。如果 x 是最后一个元素，则输出 0；

3 x：从表中删除元素 xxx后面的那个元素，不改变其他元素的先后顺序。

输入格式

第一行一个整数 q 表示操作次数。

接下来 q 行，每行表示一次操作，操作具体间题目描述。

输出格式

对于每个操作 2，输出一个数字，用换行隔开。

4. 正题

定义相关变量 q (操作次数），operation（进行的操作）， x，y。并且需要一个 结构体 来储存 链表节点

const int N = 2e6;
int q, operation, x, y;
struct Node() {
    int nxt; // 此程序不需要 val 值
} node[N];

题目告知最初的表有一个 元素 1 在维护，所以我们对它进行 预处理

node[1].nxt = -1;

当 operation 的值为 1 时，将 y 插入在 x 的后面，所以排除直接在开头插入元素时的代码，只用处理好 中间 与 末尾 的插入即可

if (operation == 1) {
    cin >> x >> y;
    node[y].nxt = node[x].nxt; // 将原来 x 的 nxt 给到 y 的 nxt
    node[x].nxt = y; // x 的 nxt 变为 y
}

当 operation 的值为 2 时， 输出 x 后面的元素（即 node[x].nxt ）

if (operation == 2) {
    cin >> x;
    cout << node[x].nxt << endl;
}

当 operation 的值为 3 时， 删除 x 后面的元素（即 node[x].nxt ）

if (operation == 2) {
    cin >> x;
    node[x].nxt = node[node[x].nxt].nxt; // 相当于套娃，即 x 的下一个元素 为 x 的下一个元素 的下一个元素
}

最终代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6;
int q, operation, x, y;
struct Node {
    int  nxt;
} node[N];
signed main() {
    cin >> q;
    node[1].nxt = -1;
    for (int i = 1; i <= q; ++i) {
        cin >> operation;
        if (operation == 1) {
            cin >> x >> y;
            node[y].nxt = node[x].nxt;
            node[x].nxt = y;
        }
        else if (operation == 2) {
            cin >> x;
            if (node[x].nxt == -1) {
                cout << 0 << endl;
                continue;
            }
            cout << node[x].nxt << endl;
        }
        else if (operation == 3) {
            cin >> x;
            node[x].nxt = node[node[x].nxt].nxt;
        }
    }

}

相关练习

洛谷 B3631：传送门