题目描述

数组模拟链表，属于静态链表，虽然不想动态链表可以申请空间但是速度挺快的。

主要思想：
1–：
链表是由 数据 和 指向下一个结点的地址 所构成的，所以只要将 数组的下标 当作地址保存在ne[]数组中，数据保存在e[]中便可构成链表，而双链表中了l[]
保存指向左边的指针，r[]保存指向右边的指针，e[]保存数据。
2–：
单链表以般使用一个head指向链表的第一个结点并且head（初始）=-1，这样子在
插入操作中，-1将是最后一个结点所指向的位置，所以遍历函数如下

for(int i=head;i!=-1;i=ne[i])

3–:
双链表 会有head 和 last两个变量分别表示链表的左右两端但是一般将数组下标为0，1的元素看作
head和last，head=0，last=1；
初始化r[0]=1,l[1]=0;
遍历操作

for(int i=r[0],i!=1;i=r[i])

算法1

(单链表)

C++ 代码

#include<iostream>

using namespace std;

int const maxn=1e5+10;
int e[maxn],ne[maxn],idx,head;

void init()         //初始化单链表 
{
    head=-1;        
    idx=0;          
}

void add_head(int x)//加入头结点的操作 
{
    e[idx]=x;
    ne[idx]=head;
    head=idx;       
    idx++;          
}

void del(int k)
{
    if(k==-1) head=ne[head];    //删除结点如果是头结点需要特判 
    else ne[k]=ne[ne[k]];   
}

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

int main()
{
    int m; cin>>m;
    init(); 
    while(m--)
    {
        char aim; cin>>aim;
        if(aim=='H')
        {
            int x; cin>>x; add_head(x);
        }
        if(aim=='I')
        {
            int x,k; cin>>k>>x;
            add(x,k-1);
        }
        if(aim=='D')
        {
            int k; cin>>k;
            del(k-1);
        }
    }
    for(int i=head;i!=-1;i=ne[i])
    cout<<e[i]<<" ";
}

算法2

(双链表)

C++ 代码

#include<iostream>

using namespace std;

int const maxn=1e5+10;
int e[maxn],l[maxn],r[maxn],idx;

void init() //初始化
{
    r[0]=1;
    l[1]=0; 
    idx=2;
}

void add(int k,int x)  //添加操作
{
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];

    l[r[k]]=idx;//这两行代码不可以写反
    r[k]=idx;   //

    idx++;
}

void del(int k) //删除操作
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

int main()
{
    int m; cin>>m;
    init();
    while(m--)
    {
        string aim; cin>>aim;
        if(aim=="L")
        {
            int x; cin>>x;
            add(0,x);
        }
        else if(aim=="R")
        {
            int x; cin>>x;
            add(l[1],x);
        }
        else if(aim=="D")
        {
            int k; cin>>k;
            del(k+1);
        }
        else if(aim=="IL")
        {
            int x,k; cin>>k>>x;
            add(l[k+1],x);
        }
        else
        {
            int x,k; cin>>k>>x;
            add(k+1,x);
        }
    }   
        for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";
        cout<<endl;
}