1. 单链表
#include<iostream>
using namespace std;
const int N=1e5+10;
int head,idx,e[N],ne[N];
void init ()
{
head=-1;
idx=0;
}
//初始化
void add_to_head (int x)
{
e[idx]=x;
ne[idx]=head; //先让插入元素指向head的下一个节点的下标
head=idx++; //再让head指向插入元素的下标
}
void add (int k,int x)
{
e[idx]=x;
ne[idx]=ne[k]; //先让插入元素指向k的下一个节点的下标
ne[k]=idx++; //再让k指向插入元素的下标
}
void remove (int k)
{
ne[k]=ne[ne[k]]; //k直接指向下下个元素的下标
}
int main()
{
int m;
cin>>m;
init();
while (m--)
{
int x,k;
char s;
cin>>s;
if (s=='H')
{
cin>>x;
add_to_head(x);
}
else if (s=='D')
{
cin>>k;
if (k==0) head=ne[head]; //head指向下下个元素的下标
else remove(k-1); //第k个数的下标是k-1
}
else if (s=='I')
{
cin>>k>>x;
add(k-1,x);
}
}
for (int i=head;i!=-1;i=ne[i]) cout<<e[i]<<" ";
//i不断指向下一个下标直到i=-1
return 0;
}
2.双链表
#include<iostream>
using namespace std;
const int N=1e5+10;
int e[N],l[N],r[N],idx;
void init ()
{
r[0]=1;
l[1]=0;
idx=2;
}
//初始化,0右边是1,1左边是0
void add (int k,int x)
{
e[idx]=x;
r[idx]=r[k];
l[r[k]]=idx;
l[idx]=k;
r[k]=idx++;
}
//和单链表类似,因为是双链表,所以指向了四次
void _remove (int k)
{
l[r[k]]=l[k];
r[l[k]]=r[k];
}
int main ()
{
int m;
cin>>m;
init ();
while (m--)
{
int k,x;
string s;
cin>>s;
if (s=="L")
{
cin>>x;
add (0,x); //在0的右边插入
}
else if (s=="R")
{
cin>>x;
add (l[1],x); //在1的上一个节点的右边插入
}
else if (s=="D")
{
cin>>k;
_remove(k+1);
}
else if (s=="IL")
{
cin>>k>>x;
add (l[k+1],x);
}
else
{
cin>>k>>x;
add (k+1,x);
}
}
//k+1是因为数组是从0开始,idx初始为2,k-1+2=k+1
for (int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";
return 0;
}