本质：

本质上就是用数组模拟动态链表，也就是说这是静态链表，静态模拟链表速度快。

基本原理：

就是利用数组来模拟整个过程，如在头节点插入数据，删除数据，在任意结点插入数据……每个结点有一个值e[i],有一个指针ne[i]，

head指的是头节点的下标，idx表示当前用到了第几个结点，这个结点是可用的。

实现功能：

1、在头节点处插入一个结点

void add_to_head(int k)
{
      e[idx]=k;
      ne[k]=head;
      head=idx++;
}

2、在其他位置插入一个新结点

void insert(int k,int c)
{
     e[idx]=c;
     ne[idx]=ne[k];
     ne[k]=idx++;
}

3、删除结点

void remove(int k)
{
    ne[k]=ne[ne[k]];
}

代码实现：

#include <iostream>
using namespace std;
const int N=100010;
int e[N],ne[N],head,idx,n;
​
void init()
{
    head=-1;
    idx=0;
}
void add_to_head(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}
​
void remove(int k)
{
    ne[k]=ne[ne[k]];
    
}
​
void insert(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
int main()
{
    init();
    scanf("%d",&n);
    while(n--)
    {
        int k,x;
        char c;
        cin>>c;
        if(c=='H')
        {
            scanf("%d",&x);
            add_to_head(x);
        }
        else if(c=='D')
        {
            scanf("%d",&k);
            if(!k)
            head=ne[head];
            else
            remove(k-1);
     
       }
       else
       {
           scanf("%d%d",&k,&x);
           insert(k-1,x);
       }
       
    }
    for(int i=head;i!=-1;i=ne[i])
    {
        printf("%d ",e[i]);
    }
    return 0;
    
}