数据结构--双链表

今天我们来用数组来模拟双链表

为什么要数组模拟呢？
因为用数组模拟的双链表，运行速度更快，做算法题更加舒服

用数组模拟双链表的内容

1、同样也有首尾结点
2、相邻的两个节点是相互指向的
3、可以看成两个方向相反的单链表相互连接在一起

首先同样要初始化

1、现在用两个数组来代表左单链表和右单链表，即为l[N], r[N]
2、l[N]数组为指向右边的链表，r[N]为指向左边的链表
3、e[N]为当前结点的值
4、设r[0]=1,l[1]=0,因为是相互指向
5、同样用一个idx来储存当前结点用到了哪一点下面给出图和代码

int m;
int e[N],r[N],l[N],idx;
 
void init()
{
    r[0]=1,l[1]=0;
    idx=2;
}
1
2
3
4
5
6
7
8

为什么idx要等于2呢，因为初始化左右结点因为各被用了，所以 idx为2，而且0代表头结点，1为尾节点

接下来就是功能的实现

1、任意插入一个数x
2、任意删除某一个结点

讲x插入到第k的右边

1、首先要确定某一个结点，e[idx]=x;
2、让idx的右边指向k结点的右边，r[idx]=r[k];
3、让idx的左边指向k,l[idx]=k
4、再让k结点的右边的点指向x，即为l[r[k]]=idx;
5、再让k结点的左边指向idx，r[k]=idx;
6、最后当前结点被用过了，所以idx要向后移动一位，即idx++;

而且第四步和第五步不能相互颠倒，如果相互颠倒，就会改变r[k]的值，就会出现错误
代码功能如下

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

那怎么插入到k节点的左边呢？

就是相当于l[k]的右边插入一个数，所以把参数k换成l[k]就行，因为l[k]为k左边相邻的结点

2、删除某一个结点

和单链表相似，不过这次要左边和右边都要相互操作一遍

因为某一个结点都是相互指向的，用第k个结点举例

首先，用k结点的左边的结点等于k结点右边的结点，即为r[l[k]]=r[k];

然后再让k结点的右边的结点等于k结点左边的节点，即为l[r[k]]=l[k];

//删除第k个数
void remove(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}
1
2
3
4
5
6

这样双链表的功能的就实现了

具体问题：

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

1. 在最左侧插入一个数；
2. 在最右侧插入一个数；
3. 将第 k 个插入的数删除；
4. 在第 k 个插入的数左侧插入一个数；
5. 在第 k 个插入的数右侧插入一个数
6. 现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的前后顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

Acwing 827

#include 
using namespace std;

const int N = 100010;
int e[N], l[N], r[N], idx;

void init() {
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在下标是k的点的右边插入x
void add(int k, int x) {
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main() {
    int n;
    cin >> n;
    
    init();
    while (n--) {
        string op;
        cin >> op;
        int k, x;
        if (op == "L") {
            cin >> x;
            add(0, x);
        } else if (op == "R") {
            cin >> x;
            add(l[1], x);
        } else if (op == "D") {
            cin >> k;
            remove(k + 1);
        } else if (op == "IL") {
            cin >> k >> x;
            add(l[k + 1], x);
        } else if (op == "IR") {
            cin >> k >> x;
            add(k + 1, x);
        }
    }

    int head = r[0];
    while (head != 1) {
        cout << e[head] << " ";
        head = r[head];
    }

    return 0;
}

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