数组模拟单链表，双链表

单链表
双链表
这两道题有一种好写的写法，就是左右建立哨兵，然后就不需要考虑边界，数组模拟链表我还是习惯性写结构体带next的写法，更容易理解吧。

#include<iostream>
using namespace std;
int m,idx;
const int N=100005;
struct node
{
    int val,next;
}a[N];

void init()
{
    a[0].next=1;
    idx=2;
}
//在第k个数右边插入x
void insert(int k,int x)
{
    a[idx].val=x;
    a[idx].next=a[k].next;
    a[k].next=idx++;
}

void del(int k)
{
    a[k].next=a[a[k].next].next;
}

int main()
{
    init();
    string s;
    int x,k;
    cin>>m;
    while(m--)
    {
        cin>>s;
        if(s=="H")
        {
            cin>>x;
            insert(0,x);
        }
        else if(s=="D")
        {
            cin>>k;
            if(k==0)
                del(0);
            else
                del(k+1);
        }
        else
        {
            cin>>k>>x;
            insert(k+1,x);
        }
    }    
    for(int i=a[0].next;i!=1;i=a[i].next)
    {
        cout<<a[i].val<<" ";
    }
    cout<<endl;
}

先初始化0,1节点，真正的节点从2开始赋值，insert的时候，都需要先考虑新插入的点，先写长的式子，最后遍历输出从0节点的下一个节点开始，到1节点的前面那个节点。

#include<iostream>
using namespace std;
const int N=1e5;
struct node
{
    int val,pre,next;
}a[N];
int idx;
void init()
{
    a[0].next=1;
    a[1].pre=0;
    idx=2;
}

//表示在第k个插入的数右侧插入一个数
void insert(int x,int k)
{
    a[idx].val=x;
    a[idx].pre=k;
    a[idx].next=a[k].next;
    a[a[k].next].pre=idx;
    a[k].next=idx;
    idx++;
}
//将第k个插入的数删除
void del(int k)
{
    a[a[k].next].pre=a[k].pre;
    a[a[k].pre].next=a[k].next;
}

int main()
{
    init();
    int m,x,k;
    cin>>m;
    string s;
    while(m--)
    {
        cin>>s;
        if(s=="L")
        {
            cin>>x;
            insert(x,0);
        }
        else if(s=="R")
        {
            cin>>x;
            insert(x,a[1].pre);
        }
        else if(s=="D")
        {
            cin>>k;
            del(k+1);//k+1
        }
        else if(s=="IL")
        {
            cin>>k>>x;
            insert(x,a[k+1].pre);
        }
        else
        {
            cin>>k>>x;
            insert(x,k+1);
        }
    }
    for(int i=a[0].next;i!=1;i=a[i].next)
    {
        cout<<a[i].val<<" ";
    }
    cout<<endl;
}

这样单链表和双链表都可以通过insert和del操作完成所有的基本操作，不需要分析边界。