14.单链表

//用数组表示静态链表，相比于动态链表更快，初始化head=-1，indx=0;

注意:下标是从0开始的，所以第k个数，是下标为k-1的数。

//头插法

void add_to_head(int x)//头插法
{
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}

//将x插入到下标是k的点后面

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

//将下标是k的点的后面的点删掉

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

//注意删除操作中，删除头结点时，只需要让头结点指向下下个点即可

     if(!t)//删除头结点
        head=ne[head];

#include <iostream>

using namespace std;

const int N=1e5+10;

int head,idx,e[N],ne[N];

int m;

void init()
{
    head=-1;
    idx=0;
}

void add_to_head(int x)//链表头插入一个元素
{
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}

void add(int k,int x)//将x插到下标是k的点的后面
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}

void remove(int k)//删除第k个节点的后面的节点
{
    ne[k]=ne[ne[k]];
}

int main()
{
    init();
    cin>>m;
    for(int i=0;i<m;i++)
    {
        char c;
        int k,t;
        getchar();
        scanf("%c",&c);
        if(c=='H')//链表头插入一个元素
        {
            scanf("%d",&t);
            add_to_head(t);
        }
        else if(c=='D')
        {
            scanf("%d",&k);//删除第k个插入的数后面的数（当k为0时，表示删除头结点）
            if(!k)  head=ne[head];
            remove(k-1);
        }
        else if(c=='I')//在第k个插入的数后面插入一个数x（此操作中k均大于0）
        {
            scanf("%d%d",&k,&t);
            add(k-1,t);
        }
    }
    
    for(int i=head;i!=-1;i=ne[i])   cout<<e[i]<<" ";
    
    return 0;
}