单链表

一、算法思想

使用静态数组实现单链表。优势：相比于 new 操作，数组内操作更快，

二、算法模板

C++

// e[] 存储节点的值
// ne[] 存储节点的 next 指针
// idx 表示当前用到了哪个节点
int e[N], ne[N], idx;

// 初始化
void init()
{
    ne[0] = -1;
    idx = 1;
}

// 将 x 插入到下标为 k 的节点后面
void insert(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

// 删除下标为 k 的节点后面的结点
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

三、代码实战

AcWing 0826

---

题目：单链表

实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数；
2. 删除第 $k$ 个插入的数后面的数；
3. 在第 $k$ 个插入的数后插入一个数。

现在要对该链表进行 $M$ 次操作，进行完所有操作后，从头到尾输出整个链表。

注意：题目中第 $k$ 个插入的数并不是指当前链表的第 $k$ 个数。例如操作过程中一共插入了 $n$ 个数，则按照插入的时间顺序，这 $n$ 个数依次为：第 $1$ 个插入的数，第 $2$ 个插入的数，$\cdots$ 第 $n$ 个插入的数。

输入格式

第一行包含整数 $M$，表示操作次数。

接下来 $M$ 行，每行包含一个操作命令，操作命令可能为以下几种：

1. H x，表示向链表头插入一个数 $x$；
2. D k，表示删除第 $k$ 个插入的数后面的数（当 $k$ 为 $0$ 时，表示删除头结点）。
3. I k x，表示在第 $k$ 个插入的数后面插入一个数 $x$（此操作中 $k$ 均大于 $0$）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

$1 \le M \le 100000 \text{，所有操作保证合法。}$

输入样例：

10

H 9

I 1 1

D 1

D 0

H 6

I 3 6

I 4 5

I 4 5

I 3 4

D 6

输出样例：

6 4 6 5

解答代码：

#include <iostream>

using namespace std;

const int N = 100010;

// e[] 存储节点的值
// ne[] 存储节点的 next 指针
// idx 表示当前用到了哪个节点
int e[N], ne[N], idx;

// 初始化
void init()
{
    ne[0] = -1;
    idx = 1;
}

// 将 x 插入到下标为 k 的节点后面
void insert(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

// 删除下标为 k 的节点后面的结点
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    init();
    
    int m;
    cin >> m;
    
    while (m--) {
        int k, x;
        char op;
        cin >> op;
        if (op == 'H') {
            cin >> x;
            insert(0, x);
        } else if (op == 'D') {
            cin >> k;
            remove(k);
        } else {
            cin >> k >> x;
            insert(k, x);
        }
    }
    
    for (int i = ne[0]; i != -1; i = ne[i]) {
        cout << e[i] << " ";
    }
    
    return 0;
}