铺垫

在学这个之前，小伙伴们最好先要了解下如何用结构体形成单链表，因为如果理解了那个，这儿就很好理解了，不懂得小伙伴可以去看看博主之前的文章。带你重温单链表
很多小伙伴可能会好奇？结构体形成单链表玩的好好的，为什么要用数组来玩了？其实这就要涉及到效率的问题了，如果用之前的方法，在C++中我们每创建一个节点，就要new一下，如果单链表很长，那么会很消耗时间，有时在面试题中甚至都过不了，因为new消耗的时间太多了。

基本思想

用数组实现单链表的基本思想就是用两个数组：一个存放值，一个存放下一个节点的下标（在结构体的写法中，就相当于存放下一个节点的地址）。在这个过程中我们要用到一个变量idx来记录当前可用节点的下标。这个算法说起来很抽象，不容器理解，下面我们来看代码以及结合之前结构体形成链表的方法来理解，就很容器理解了。

初始化

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

一开始链表中为空，-1为下标的位置就是空节点，idx为0，说明当前为0个可用节点。

向头节点插入

这种方法其实在结构体形成链表中也就是头插法。

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

1.首先给这个位置赋值为x，一开始我们就说了，idx为当前可用位置的下标。所以代码为e[idx]=x。
2.当前位置的next（ne[]数组代替）指向头，然后让这个位置变为头节点。所以相应代码为：
ne[idx]=head;
head=idx；
3.这样就完成了头插操作,此时当前位置已经用过了，所以idx++。

下面的几个函数接口也是采用同样的类比方法来理解，这儿就不在赘述。

在任意节点之后插入一个x

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

删除任意位置之后的一个节点

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

单链表题目

这儿要注意的一个点是：
要理解第k个插入的数的含义，我们来举例看看（以结构体形成单链表中而言），第一个数插入之后，其下标为0，第二个插入之后其下标为1，那么第k个插入的数其下标则为k-1。

代码实现

#include<iostream>
using namespace std;

const int N=100010;

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

void init()
{
    head=-1;
    idx=0;
}
void  add_to_head(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}

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

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

int main()
{
    int m;
    cin>>m;
    init();

    while(m--)
    {
        char op;
        int x;
        int k;
        cin>>op;
        if(op=='H')
        {
            cin>>x;
            add_to_head(x);
        }
        else if(op=='I')
        {
            cin>>k>>x;
            add_to_after(k-1,x);
        }
        else
        {
            cin>>k;
            if(!k) head=ne[head];
            else move_after(k-1);
        }
    }
    for(int i=head;i!=-1;i=ne[i])
    {
        cout<<e[i]<<" ";
    }
    cout<<endl;
    return 0;
}

注意：
1.至于这儿为什么要传k-1，上面已经说过了。
2.在D的这种情况中，要处理一下特殊情况，如果k=0，也就是删除头节点之后的节点的情况。
3.

在这儿也是要类比结构体实现单链表中一样理解，我们要打印单链表中的值，就要遍历他，通过ne这个数组来遍历，因为其中相当于存放了他们之间的连接关系，首先从head开始，然后ne[i]从头往后遍历，之后最后遇到-1（空节点）停止。

双向链表题目

双链表的思路也是，同样需要类比之前用指针实现的双向循环链表的思路，这是博主之前的关于双向链表的文章：双向循环链表
注意：这儿的双向链表并不是双向循环链表

代码实现

#include<iostream>

using namespace std;

const int N=100010;

int e[N],l[N],r[N],idx;

//初始化 0表示左端点，1表示右端点
void init()
{
    r[0]=1;
    l[1]=0;
    idx=2;
}

//在节点k的右边插入一个节点
void add_k_right(int k,int x)
{
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];
    l[r[k]]=idx;   //这两个顺序不能反，因为你要引用r[k]
    r[k]=idx++;
}

//删除k节点
void movek(int k)
{
     l[r[k]]=l[k];
     r[l[k]]=r[k];
}

int main()
{
    int m;
    cin>>m;
    init();
   while(m--)
   {
       string op;
       cin>>op;
       int x;
       int k;
       if(op=="L")
       {
           cin>>x;
           add_k_right(0,x);
       }
       else if(op=="R")
       {
           cin>>x;
           add_k_right(l[1],x);
       }
       else if(op=="D")
       {
           cin>>k;
           //注意这儿idx是从2开始的，即第一个插入的元素idx为2，因为0,1被左右端点占据了
           movek(k+1);
       }
       else if(op=="IL")
       {
           cin>>k;    //注意这儿的顺序，k写在前面，因为在函数传参时，先传的是有关k+1的这个，所以k的cin要写在前面
           cin>>x;
           add_k_right(l[k+1],x);
       }
       else
       {
           cin>>k>>x;  //注意这儿的顺序，k写在前面，因为在函数传参时，先传的是有关k+1的这个，所以k的cin要写在前面
           add_k_right(k+1,x);
       }

   }
   for(int i=r[0];i!=1;i=r[i])
   {
       cout<<e[i]<<' ';
   }
   cout<<endl;
   return 0;
}

注意：
1.这儿只需要两个接口就可以实现5个功能，我们实现的是在k节点右边插入一个节点，如果要在它的左边插入一个节点，可以将问题转化为在k的左节点的右边插入一个节点。
2.在双向链表中0表示左端点，1表示右端点，仅起标识作用，不存放值。
3.正因为有0,1左端点和右端点的存在，所以idx是从2开始的，即第一个插入的元素的idx为2，所以在传第k个插入元素的时候要传k+1进去。
4.cin>>k>>x这儿要注意顺序，不能先写x再写k，因为你函数传参时是先传的有关k的参，所以要先把k写在前面。
5. l[r[k]]=idx; r[k]=idx++; 这两句代码写的时候要注意顺序，不然可能会对之后的代码造成影响。