使用数组模拟的双链表

双链表

与单链表相比，区别是：
双链表的每一个节点都有对应的前驱和后继。

可以完成一些单链表无法完成的任务。

[基础的双链表操作](827. 双链表 - AcWing题库)

#include <iostream>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

void init()
{
    //将0 ， 1 分别设为头节点和尾部节点
    l[1] = 0;
    r[0] = 1;
    idx = 2;
}

//向插入的第k个数后面插入一个数
//也可以通过将参数k 改为l[k]来实现向k的左边插入一个数
void add(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

//移去第k个插入的数
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main()
{
    init();
    int m;
    cin >> m;
    string op;
    while (m--)
    {
        cin >> op;
        if (op == "L")
        {
            //向头节点的后面添加一个数，就是在最前面加上一个数
            int x;
            cin >> x;
            add(0, x);
        }
        else if (op == "R")
        {
            //向尾节点前面一个数的后面加一个数，就是在最后加上一个数
            int x;
            cin >> x;
            add(l[1], x);
        }
        else if (op == "D")
        {
            //删去第k个插入的数
            int x;
            cin >> x;
            remove(x + 1);
            //第一个插入的数的下标是2 ，因为将  1 定义为了末尾
        }
        else if (op == "IL")
        {
            //在第k个插入的数前面插入一个数
            int k, x;
            cin >> k >> x;
            add(l[k + 1], x);
            //在第k个左边的右面插入，就是在k的左边插入
        }
        else
        {
            int k, x;
            cin >> k >> x;
            add(k + 1, x);
        }
    }
    for (int i = r[0]; i != 1; i = r[i])
        cout << e[i] << " ";
    return 0;
}