1.单链表

「常见实现方式」：

  1. STL vector ：直接使用库函数，方便。
  2. 结构体： 最常规的数据结构，按部就班的来。
  3. 静态数组：数组模拟在算法题中提高运行速度。

「采用静态数组」：

「变量介绍」：

e[N]: 存储每一个插入的元素的值。

ne[N]: 存储每一个元素的下一个元素对应的的数组下标。

head: 存储 头节点的下标。

idx: 是计量数，可以理解为每插入一个元素都会追加在e[N]数组里，而idx表示当前到第几个该插入了，插入后idx++。

1
int e[N], ne[N], head, idx;

「实现思路：」

  1. 初始化 head 为 -1，首先head指向空。初始化 idx 为0，从下标0开始记录。

  2. 指令为 ‘H’，表示在链表最头部插入，也就是头节点，对应代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 在链表头插入
    void into_head(int x)
    {
        e[idx] = x; // 先存下当前要插入元素
        ne[idx] = head; // 让 当前点的指向的下一个元素的下标 为 head的下一个，
      	//因为头结点之前可能指向 a，你要在头结点插入一个新元素 b，那就形成了head ----> b(新) ----> a（旧）的关系。
        head = idx; // 之后让 head 指向新插入的元素
        idx++; // 操作完成，idx++
    }

  3. 指令为 ‘I’，则表示在第k个数后面插入一个新元素，因为数组下标从0开始，则k-1就对应第k个数

    1
    2
    3
    4
    5
    6
    7
    8
    // 在第 k个插入的数后插入一个数
    void add_to_k(int k, int x)
    {
        e[idx] = x; // 思路大致相同
        ne[idx] = ne[k]; // 让 新插入的元素的下一个指向为 k 的下一个。
        ne[k] = idx; // 之后让 k指向新插入的元素
        idx++;
    }

  4. 指令为 ‘D’，则表示删除 第k个元素后面的数。

    1
    2
    3
    4
    5
    // 移除第k个后面的数
    void remove(int k)
    {
        ne[k] = ne[ne[k]]; // 例如 a --> b -- >c ，直接 a --> c,就表示删除了中间元素 
     }

「完整代码：」

题目链接：826. 单链表 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;

int e[N], ne[N], head, idx;

void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入

void into_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

// 在第 k个插入的数后插入一个数
void add_to_k(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

// 移除第k个后面的数
void remove(int k)
{
    ne[k] = ne[ne[k]];
}
int main()
{
    int num;
    cin >> num;
    init();
    for (int i = 1; i <= num; i++)
    {
        char c1;
        cin >> c1;
        if (c1 == 'H')
        {
            int x;
            cin >> x;
            into_head(x);
        }
        if (c1 == 'D')
        {
            int k;
            cin >> k;
            if (k == 0)
                head = ne[head];
            else
                remove(k - 1);
        }
        if (c1 == 'I')
        {
            int k, x;
            cin >> k >> x;
            add_to_k(k - 1, x);
        }
    }
   
    for (int i = head; i != -1; i = ne[i])
    {
        cout << e[i] << " ";
        
    }
    return 0;
}

2.双链表

「常见实现方式：」

  1. 结构体：最基础，常用。
  2. 静态数组：数组模拟，速度较快。

「静态数组方式：」

「变量介绍：」

e[N]: 存储每一个插入的元素的值。

l[N]: 存储每一个元素的左链接元素下标。

r[N]: 存储每一个元素的右链接元素下标。

idx: 是计量数，可以理解为每插入一个元素都会追加在e[N]数组里，而idx表示当前到第几个该插入了，插入后idx++。

「注意：」

这里 默认初始占据数组两个空间，l[1] and r[0] 互相指向

r[0]：r[0] = 1，表示虚拟头节点，初始指向 1，1也代表着链表结束，后续添加元素指向新的头结点元素下标。

l[1]：l[1] = 0，表示虚拟尾节点，初始指向 0，0表示虚拟头结点的位置，后续添加新元素指向新的尾节点元素下标。

「实现思路：」

1.以下插入操作都可以通过一个函数解决：

L x，表示在链表的最左端插入数 x。（最左端可以理解为在0的右边插入，即让 r[0] = idx(大概意思)）

R x，表示在链表的最右端插入数 x。 (在最右端可以理解为在尾端点的 左元素 的右边插入，即在 r[l[1]] = idx(大概意思))

IL k x，表示在第 k个插入的数左侧插入一个数。 (第k个数的左边，即 第 k - 1插入的数的右边，这里注意，不是直接寻找第k-1个数，而是寻找第k个数的左边，然后再在这个元素的右边插入，即 r[l[k+1]] = idx(大概意思，因为idx从2开始，k+1对应第k个数))

IR k x，表示在第 k 个插入的数右侧插入一个数。

1
2
3
4
5
6
7
8
9
10
// 往第k个右边插入数据
void insert_right(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

2.删除操作就一个函数：

让第k个数的右边的左边等于第k个数的左边，让k的左边的右边等于k的右边。

1
2
3
4
5
void removeK(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

「完整代码：」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
int e[N], l[N], r[N], idx;

// 初始化双链表
void init()
{
    l[1] = 0;
    r[0] = 1;
    
    idx = 2;
}

// 往第k个右边插入数据
void insert_right(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}
void removeK(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int M;
    cin >> M;
    init();
    for (int i = 0; i < M; i++)
    {
        string c1;
        cin >> c1;
        if (c1 == "IR")
        {
            int k, x;
            cin >> k >> x;
            insert_right(k + 1, x); // idx 从 2 开始，那么 第 k 个插入的数就是 k + 1
        }
        else if (c1 == "L")
        {
            int x;
            cin >> x;
            insert_right(0, x);
        }
        else if (c1 == "IL") // 往 第 k 个的左边插入数据，就是往 k - 1的右边插入，因为 第k个对应 k + 1，所以k-1就对应 l[k + 1]
        {

            int k, x;
            cin >> k >> x;
            insert_right(l[k + 1], x);
        }
        else if (c1 == "R")
        {
            // 往最右边插入，即 l[1] 的右侧插入，因为l[1]肯定对应最后一个元素的下标
            int x;cin >> x;
            insert_right(l[1],x);
        } else 
        {
            int k;
            cin >> k;
            removeK(k+1); // 找到 第k个的左侧
        }
    }

    for (int i = r[0]; i != 1; i = r[i])
    {
        cout << e[i] << " ";
    }
    cout << endl;
    return 0;
}