双链表

include[HTML_REMOVED]

using namespace std;
const int N=1e6;
int l[N],r[N],idx,v[N];
//l数组是每一个数的前指针。
void init(){
l[1]=0; //head:0
r[0]=1;//tail:1
idx=2;
}
void headadd(int x){
l[idx]=0;
r[idx]=r[0];

r[0]=idx;
l[r[idx]]=idx;//注意这里很容易出错
v[idx++]=x;

}
void tailadd(int x){
v[idx]=x;
r[idx]=1;
l[idx]=l[1];

r[l[idx]]=idx;
l[1]=idx;
idx++;

}
void deletee(int k ){
r[l[k]]=r[k];
l[r[k]]=l[k];
}
void insertl(int x,int k){
r[idx]=k;
l[idx]=l[k];

r[l[idx]]=idx;
l[k]=idx;
v[idx++]=x;

}
void insertr(int k,int x){
l[idx]=k;
r[idx]=r[k];

l[r[idx]]=idx;
r[k]=idx;
v[idx++]=x;

}
int main(){
ios::sync_with_stdio(false);
init();
int m;
cin>>m;
while(m–>0){
int k,x;
string s;
cin>>s;
if(s==”L”) {
cin>>x;
headadd(x);
}
else if(s==”R”){
cin>>x;
tailadd(x);
}
else if(s==”D”){
cin>>k;
deletee(k+1);
}
else if(s==”IL”){
cin>>k>>x;
insertl(x,k+1);
}
else if(s==”IR”){
cin>>k>>x;
insertr(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i])
cout<<v[i]<<’ ‘;
cout<<endl;
return 0;

}