head是头指针
// head存储链表头位置,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 将头结点删除,需要保证头结点存在
void remove()
{
head = ne[head];
}
////////////////////////////////////////////////////////////
#include<iostream>
using namespace std;
const int N = 111111;
int head = -1, e[N],ne[N],idx=0;
void add_head(int x)
{
e[idx]=x;
ne[idx]=head;
head = idx++;
}
void dlt(int k)
{
if(k==0)head = ne[head];
else ne[k-1]=ne[ne[k-1]];
}
void insert(int k , int x)
{
e[idx]=x;
ne[idx]=ne[k-1];
ne[k-1]=idx++;
}
int main()
{ ios::sync_with_stdio(false);
cin.tie(NULL);
int n;cin>>n;
char op;
while(n--)
{
cin>>op;
if(op=='H')
{
int x;cin>>x;
add_head(x);
}
else if(op=='D')
{
int k;cin>>k;
dlt(k);
}
else if(op=='I')
{
int k,x;cin>>k>>x;
insert(k,x);
}
}
for(int i = head;i!=-1;i=ne[i])
cout<<e[i]<<' ';
}
//再上一个代码的基础上,把head(头指针)换成了ne[0](头结点);
//这样子对于删除首元结点就不需要特判了,而且传参的时候k就是第k个插入的数
#include<iostream>
using namespace std;
const int N = 111111;
int e[N],ne[N],idx=1;
void add_head(int a)
{
e[idx]=a;
ne[idx]=ne[0];
ne[0] = idx++;
}
void insert(int k,int a)
{
e[idx]=a;
ne[idx]=ne[k];
ne[k]=idx++;
}
void dlt(int k)
{
ne[k]=ne[ne[k]];
}
int main()
{
char op;
ne[0]=-1;
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;cin>>n;
while(n--)
{
cin>>op;
if(op=='D')
{
int k;
cin>>k;
dlt(k);
}
if(op=='H')
{
int a;
cin>>a;
add_head(a);
}
if(op=='I')
{
int a,k;
cin>>k>>a;
insert(k,a);
}
}
for(int i = ne[0];~i;i=ne[i])
cout<<e[i]<<' ';
}