15.双链表

原题链接

//把0看成左端点，1看成右端点，刚开始的时候，左端点指向右端点，右端点指向左端点

• 插入操作

void add(int k,int x)//第k个元素后面插入x
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;//先后顺序注意
    r[k]=idx++;
}

• 删除操作

  //让这个点的左边指向右边，这个点的右边指向左边

void Remove(int k)//删除第k个元素
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

注意：因为idx是从2开始的，所以第k个插入的数对应的下标是k+1。
//是从0开始的话，第k个数对应第k-1的下标

#include <iostream>
using namespace std;
int l[MAX],r[MAX],e[MAX],idx;
void init()
{
    //0表示左端点，1表示右端点
    r[0]=1;
    l[1]=0;
    idx=2;
}
void add(int k,int x)//第k个元素后面插入x
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx++;
}
void Remove(int k)//删除第k个元素
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}
int main()
{
    init();
    int m;
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        string str;
        int t,num;
        cin>>str;
        if(str[0]=='L')
        {
            scanf("%d",&t);
            add(0,t);
        }
        else if(str[0]=='R')
        {
            scanf("%d",&t);
            add(l[1],t);
        }
        else if(str[0]=='D')
        {
            scanf("%d",&t);
            Remove(t+1);
        }
        else if(str=="IL")
        {
            scanf("%d%d",&t,&num);
            add(l[t+1],num);
        }
        else if(str=="IR")
        {
            scanf("%d%d",&t,&num);
            add(t+1,num);
        }
    }
    for(int i=r[0];i!=1;i=r[i])
        cout<<e[i]<<" ";
    return 0;
}