双链表

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1e6 + 10;
int e[N], l[N], r[N], idx;
//l[N]储存的是点左边相连的点是谁，r[N]同理
void init() {
	r[0] = 1;//头部
	l[1] = 0;//尾部
    //头部和尾部是开始和结束的标志，不储存值
	idx = 2;//下标从二开始，所以要在k处插入时，对应的是 k + 1
}

//在k右边插入一个值为x的点，如果是在k的左边，那传入的就是l[k]
void add(int k, int x) {
	e[idx] = x;
    //先把新点与左右点建立联系
	r[idx] = r[k];
	l[idx] = k;
    //在更改原来点左右联系
	l[r[k]] = idx;//k右边的点与新点相连
	r[k] = idx;//k与新点相连
	idx ++;
}

void remove(int k) {
	r[l[k]] = r[k];//k左边的点直接与k右边的点相连
	l[r[k]] = l[k];
}

int main() {
	init();
	int n;
	cin >> n;
	while (n --) {
		char s[5];
		int k, x;
		cin >> s;
		if (s[0] == 'L') {
			cin >> x;
			add(0, x);
		}
		if (s[0] == 'R') {
			cin >> x;
			add(l[1], x);
		}
		if (s[0] == 'D') {
			cin >> k;
			remove(k + 1);
		}
		if (s[0] == 'I' && s[1] == 'L') {
			cin >> k >> x;
			add(l[k + 1], x);
		}
		if (s[0] == 'I' && s[1] == 'R') {
			cin >> k >> x;
			add(k + 1, x);
		}
	}
	for(int i = r[0]; i != 1; i = r[i])
	{
		cout << e[i]<<" ";
	}
}