什么是雙鏈表

雙鏈表不同于單鏈表的是 每一個(gè)節(jié)點(diǎn)不但存儲了下一個(gè)節(jié)點(diǎn)的位置，也存儲了上一個(gè)節(jié)點(diǎn)的位置。

數(shù)組模擬雙鏈表

所以如果用數(shù)組的話，就需要創(chuàng)建三個(gè)數(shù)組。

題目

實(shí)現(xiàn)一個(gè)雙鏈表，雙鏈表初始為空，支持 $5$ 種操作：

1. 在最左側(cè)插入一個(gè)數(shù)；
2. 在最右側(cè)插入一個(gè)數(shù)；
3. 將第 $k$ 個(gè)插入的數(shù)刪除；
4. 在第 $k$ 個(gè)插入的數(shù)左側(cè)插入一個(gè)數(shù)；
5. 在第 $k$ 個(gè)插入的數(shù)右側(cè)插入一個(gè)數(shù)

現(xiàn)在要對該鏈表進(jìn)行 $M$ 次操作，進(jìn)行完所有操作后，從左到右輸出整個(gè)鏈表。

注意:題目中第 $k$ 個(gè)插入的數(shù)并不是指當(dāng)前鏈表的第 $k$ 個(gè)數(shù)。例如操作過程中一共插入了 $n$ 個(gè)數(shù)，則按照插入的時(shí)間順序，這 $n$ 個(gè)數(shù)依次為：第 $1$ 個(gè)插入的數(shù)，第 $2$ 個(gè)插入的數(shù)，…第 $n$ 個(gè)插入的數(shù)。

輸入格式

第一行包含整數(shù) $M$，表示操作次數(shù)。

接下來 $M$ 行，每行包含一個(gè)操作命令，操作命令可能為以下幾種：

1. L x，表示在鏈表的最左端插入數(shù) $x$。
2. R x，表示在鏈表的最右端插入數(shù) $x$。
3. D k，表示將第 $k$ 個(gè)插入的數(shù)刪除。
4. IL k x，表示在第 $k$ 個(gè)插入的數(shù)左側(cè)插入一個(gè)數(shù)。
5. IR k x，表示在第 $k$ 個(gè)插入的數(shù)右側(cè)插入一個(gè)數(shù)。

輸出格式

共一行，將整個(gè)鏈表從左到右輸出。

數(shù)據(jù)范圍

$1\le M\le 100000$
所有操作保證合法。

輸入樣例：

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

輸出樣例：

8 7 7 3 2 9

其中 數(shù)組 e 用于存儲 元素的值，數(shù)組 l 存儲上一個(gè)節(jié)點(diǎn)的位置（下標(biāo)），數(shù)組 r 存儲下一個(gè)節(jié)點(diǎn)的位置。

idx 是 下一次即將要用到的 點(diǎn)。

對于雙鏈表來說，雖然題目中有5中操作，但是只需要寫兩個(gè)函數(shù)就可以了。（不包含初始化函數(shù)）

---

初始化函數(shù)：

在用數(shù)組模擬雙鏈表時(shí)，我們可以規(guī)定數(shù)組的前兩個(gè)點(diǎn)分別指向 鏈表的頭和尾，由于剛開始沒有節(jié)點(diǎn)。

所以讓他們互相指向?qū)Ψ?#xff0c;由于前面用了兩個(gè)點(diǎn)，所以直接 讓 idx = 2.

---

在 k 位置 后插入 一個(gè)新節(jié)點(diǎn) 的函數(shù)：

模擬代碼過程：

e[ idx ] = x;

l[ idx ] = k;

r[ idx ] = r[ k ];

l[ r [ k ] ] = idx;

r[ k ] = idx;

最后自增 idx。

---

刪除 下標(biāo)為 k 的 數(shù) 的函數(shù)：

r[ l[ k ] ] = r [ k ];

l [ r [ k ] ] = l [ k ];

本題目當(dāng)中的五種操作都可以轉(zhuǎn)換該兩種函數(shù)。

輸入m，然后循環(huán)輸入m次，記得寫初始化函數(shù)。

因?yàn)橛胹canf讀取字符會讀取空格或換行符，而%s不會讀取這些符號，所以會方便很多

---

題目的五個(gè)操作：

0下標(biāo)是一個(gè)沒有存值（數(shù)組e里面沒有值，數(shù)組 l 有值）的頭坐標(biāo)，所以在下標(biāo)0的右面插入一個(gè)值相當(dāng)于在整個(gè)鏈表左邊插入一個(gè)值。

1下標(biāo)記錄著鏈表最右邊的位置，l [ 1 ] 則代表鏈表中最右邊的點(diǎn)的位置，所以在 l [ 1 ] 后面插入相當(dāng)于在鏈表的 最右邊插入一個(gè)值。

這里唯一注意的點(diǎn)就是 傳的實(shí)參是 k + 1，而不是k ，因?yàn)橐呀?jīng)用過兩個(gè)點(diǎn)了。所以插入的第一個(gè)數(shù)的下標(biāo)就是從2開始的，以此類推。

如果我們想要在 k 位置的左邊插入一個(gè)節(jié)點(diǎn)，那么相當(dāng)于在 k 的左邊節(jié)點(diǎn)的右側(cè)插入一個(gè)節(jié)點(diǎn)。

那么在右側(cè)就直接調(diào)用函數(shù)即可。

最后輸出整個(gè)鏈表即可

完整代碼如下：

#include <iostream>
#include <cstring>
using namespace std;const int N = 1e5+10;int e[N], l[N], r[N];
int idx;void init()
{r[0] = 1;l[1] = 0;idx = 2;
}//在 k 下標(biāo)后插入一個(gè)數(shù)
void insert(int k, int x)
{e[idx] = x;l[idx] = k;r[idx] = r[k];l[r[k]] = idx;r[k] = idx;idx++;
}//刪除下標(biāo)為 k 的節(jié)點(diǎn)
void remove(int k)
{r[l[k]] = r[k];l[r[k]] = l[k];
}int main()
{init();int m;scanf("%d", &m);while (m--){char op[5];int k, x;scanf("%s", op);if (op[0] == 'L')//鏈表最左端插入一個(gè)數(shù){scanf("%d", &x);insert(0, x);}else if (op[0] == 'R')//鏈表最右端插入一個(gè)數(shù){scanf("%d", &x);insert(l[1], x);}else if (op[0] == 'D')//將插入的第K個(gè)數(shù)刪除{scanf("%d", &k);remove(k + 1);//數(shù)組剛開始會用掉兩個(gè)點(diǎn)，//那么插入的第一個(gè)數(shù)下標(biāo)就為2，所以插入的第k個(gè)數(shù)就是下標(biāo)就是k+1.}else if (strcmp(op, "IL") == 0){scanf("%d%d", &k, &x);insert(l[k+1], x); }else {scanf("%d%d", &k, &x);insert(k+1, x);}}for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);return 0;
}

---

完