双链表

/*L x，表示在链表的最左端插入数 x。
R x，表示在链表的最右端插入数 x。
D k，表示将第 k 个插入的数删除。
IL k x，表示在第 k 个插入的数左侧插入一个数。
IR k x，表示在第 k 个插入的数右侧插入一个数。*/
#include<iostream>
using namespace std;
const int N=1e5+10;
int l[N],r[N],index,value[N];
void ini()
{//一开始左边界节点指向右边界节点,右边界节点指向左边界节点r[0]=1;l[1]=0;//更新节点索引index=2;
}void insert(int k,int x)//在第k个节点后插入x
{//将值赋给新节点value[index]=x;//将新节点分别指向插入位置的右节点和左节点r[index]=r[k];l[index]=k;//将新节点右边一节点向左指向新节点,将新节点左边一节点向右指向新节点l[r[k]]=index;r[k]=index;//更新节点索引index++;
}
void remove(int k)
{//删除第k个节点,第k-1的右指针指向原先第k个节点的右指针指向的节点r[l[k]]=r[k];//删除第k个节点,原先第k个节点的右指针指向的节点的左指针指向原先第k个节点的左指针指向//的节点l[r[k]]=l[k];
}
int main()
{// 0 是左边界  1是右边界//因为0和1都被占用,所以第1个节点也就是2=1+1 ,第2个节点为3=2+1;//∴第k个节点也就是k+1ini();int M,k,x;string operation;cin>>M;//操作个数while(M--){cin>>operation;//操作指令if(operation=="L")//在链表的最左端插入x{//也就是在左边界后插入一个节点,就是最左端插入一个节点cin>>x;insert(0,x);}else if(operation=="R")//在链表的最右端插入x{//也就是右边界的左节点后插入一个新节点cin>>x;insert(l[1],x);}else if(operation=="D")//把第k个插入的数删除{cin>>k;remove(k+1);}else if(operation=="IL")//第k个插入的数左侧插入一个数{//也就是在第k个插入的数的左节点后插入一个数cin>>k>>x;insert(l[k+1],x);}else//第k个插入的数右侧插入一个数{//在第k个节点后插入一个数cin>>k>>x;insert(k+1,x);}}int pos=r[0];while(pos!=1)//当指向右边界节点时,循环结束{cout<<value[pos]<<" ";pos=r[pos];}return 0;
}