与数组比较

优点：插入、删除效率比数组高

缺点：找一个节点需要遍历这个链表

单链表

用数组模拟链表

具体操作可以见下图

idx 当前节点编号

val 当前节点值

next 当前节点的下一个节点的编号

原始链表

插入

插入一个值为 $5$ 的节点，先将 next 指向下一个节点

再把之前的节点的 next 指向这个插入的节点

删除

将删除节点的指针指向删除节点的后一个即可

#include<bits/stdc++.h>
using namespace std;
int m,hed,nxt[114514],v[114514],idx;
void init()
{
    hed=-1;
}//初始化，一开始没有节点
void addH(int x)
{
    v[++idx]=x;
    nxt[idx]=hed;
    hed=idx;
}//在表头插入一个节点，并修改 head 为自己
void del(int k)
{
    nxt[k]=nxt[nxt[k]];
}//删除第 k 个插入的节点
void addI(int k,int x)
{
    v[++idx]=x;
    nxt[idx]=nxt[k];
    nxt[k]=idx;
}//在第 k 个插入的节点后面插入一个节点
int main()
{
    init();
    cin>>m;
    while(m--)
    {
        char op;
        cin>>op;
        if(op=='H')
        {
            int x;
            cin>>x;
            addH(x);
        }
        else if(op=='D')
        {
            int k;
            cin>>k;
            if(k==0)
            {
                hed=nxt[hed];
            }//特判是删除表头节点
            else del(k);
        }
        else if(op=='I')
        {
            int k,x;
            cin>>k>>x;
            addI(k,x);
        }
    }
    for(int i=hed;i!=-1;i=nxt[i])
    {
        cout<<v[i]<<" ";
    }//从头到尾输出
    return 0;
}

双链表

差不多的道理，但是要有一个指向前面一个节点的指针

原始链表

插入

把要插入的节点左指针和右指针分别指向左边的节点和右边的

将右边的节点的左指针指向要插入的节点

将左边的节点的右指针指向要插入的节点

注意：如果和上一步调换顺序会导致右边的节点丢失

删除

与单链表差不多

#include<bits/stdc++.h>
using namespace std;
int m,l[114514],r[114514],v[114514],idx;
void init()
{
    r[1]=2;
    l[2]=1;
    idx=2;
}//一开始要设两个节点分别为头和尾
void addR(int k,int x)
{
    v[++idx]=x;

    r[idx]=r[k];
    l[idx]=k;
    
    l[r[k]]=idx;
    r[k]=idx;
}
void addL(int k,int x)
{
    addR(l[k],x);
}
void del(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}
int main()
{
    init();
    cin>>m;
    while(m--)
    {
        string op;
        cin>>op;
        if(op=="L")
        {
            int x;
            cin>>x;
            addR(1,x);
        }
        if(op=="R")
        {
            int x;
            cin>>x;
            addL(2,x);
        }
        if(op=="D")
        {
            int k;
            cin>>k;
            del(k+2);//别忘记之前加过两个头尾节点
        }
        if(op=="IL")
        {
            int k,x;
            cin>>k>>x;
            addL(k+2,x);
        }
        if(op=="IR")
        {
            int k,x;
            cin>>k>>x;
            addR(k+2,x);
        }
    }
    for(int i=r[1];i!=2;i=r[i])
    {
        cout<<v[i]<<" ";
    }
    return 0;
}