题目描述
双链表
具有左右两个指针
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int idx,l[N],r[N],e[N];
//初始化双链表,头结点和尾结点是空值,他们的下标是0,1;插入的结点下标从2开始
void init()
{
r[0]=1;
l[1]=0;
idx=2;
}
void add(int k,int x)
{
e[idx]=x;
//先将新插入的结点的左右指针分别指向左右两边
r[idx]=r[k];
l[idx]=k;
//将k右边的结点的左指针指向新的结点
l[r[k]]=idx;
//将k左边的结点的右指针指向新的结点
r[k]=idx;
idx++;
}
void remove(int k)
{
//直接将k结点的左右两个结点互指,忽略中间结点k:
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main()
{
int m;
cin>>m;
init();
while(m--)
{
string op;
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")
{
int k;
cin>>k;
remove(k+1); //因为idx从2开始,所以中间的结点都是k+1;
}
else if(op=="IL")
{
int k,x;
cin>>k>>x;
add(l[k+1],x);
}
else
{
int k,x;
cin>>k>>x;
add(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i])cout<<e[i]<<" ";
cout<<endl;
return 0;
}