双向链表

$O(n)$

C++ 代码

#include <iostream>
#include <string>

const int N = 100010; 
using namespace std;
int val[N], l[N], r[N], idx;
// 初始化，比如首先定好两个左右节点，0和1，遍历就是从0到1就完事了
void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

// 每一次插入都需要改变四根线
void add_to_head(int x)
{
    val[idx] = x;
    l[idx] = 0;
    r[idx] = r[0];
    l[r[0]] = idx;
    r[0] = idx++;
}

void add_to_tail(int x)
{
    val[idx] = x;
    r[idx] = 1;
    l[idx] = l[1];
    r[l[1]] = idx;
    l[1] = idx++;
}

// 删除的是第几个插入的数而不是此时链表中第几个数
void del(int k)
{
    // 第一个插入的数坐标为2
    r[l[k+1]] = r[k+1];
    l[r[k+1]] = l[k+1];
}

// 插入到某个树左边
void add_k_left(int k, int x)
{
    val[idx] = x;
    l[idx] = l[k+1];
    r[idx] = k+1;
    r[l[k+1]] = idx;
    l[k+1] = idx++;
}

// 插入到某个树右边
void add_k_right(int k, int x)
{
    val[idx] = x;
    r[idx] = r[k+1];
    l[idx] = k+1;
    l[r[k+1]] = idx;
    r[k+1] = idx++;
}

int main()
{
    std::ios::sync_with_stdio(false);
    init();
    string command;
    int a, b;
    int m;
    cin >> m;
    // 操作m次
    while(m--)
    {
        cin >> command;
        if(command == "L")
        {
            cin >> a;
            add_to_head(a);
        }
        else if(command == "R")
        {
            cin >> a;
            add_to_tail(a);
        }
        else if(command == "D")
        {
            cin >> a;
            del(a);
        }
        else if(command == "IL")
        {
            cin >> a >> b;
            add_k_left(a,b);
        }
        else
        {
            cin >> a >> b;
            add_k_right(a,b);
        }
    }
    for(int i = r[0]; i != 1; i = r[i])
        cout << val[i] << " ";
    return 0;
}