链表

1.链表

主要思想：使用数组实现链表（而不用结构体，结构体代码更长，后续图论也是基于数组实现），即静态链表。因为动态链表使用new申请空间需要较多的时间，而算法要求的是以较少的时间完成任务。

1. 单链表，最主要用单链表写邻接表，用邻接表存储图或者树
2. 双链表，优化某些问题

1）单链表

**单链表：**头指针head指向第一个结点，初始为-1。数组e[]存储结点的值，数组ne[]存储对应结点的下一个结点的下标，形成一个链条。本质上是用数组下标来操作对应结点

AcWing 826.单链表

实现思路：

• 设置数组e[]存储结点值，数组ne[]存储对应结点下一个结点的下标

• 设置头指针head指向第一个结点，初始值为-1

• 设置指针idx表示当前操作位置，初始为0即指向数组的第一个位置，单增（实际上idx所指向的位置就是将要操作的数组位置，这个位置还未存入结点，每次存入结点后idx需要后移，但删除结点时不用考虑当前数组位置是否浪费而做出某种处理，算法以速度为主，因此删除结点是idx结点不用前移）

#include <iostream>
using namespace std;
const int N=1e6+10;
 
int e[N],ne[N];
int head,idx;
 
//初始化
void init(){
    head=-1;
    idx=0;
}
 
//链表头插入结点
void add_to_head(int x){
    e[idx]=x;
    ne[idx]=head;
    head=idx;//根据数组表示链表的性质，随着链表头不断插入结点，第一个结点的位置是后移的，即head后移到idx
    idx++;//插入结点后idx指针后移
}
//在下标为k的结点后面插入结点
void add(int k,int x){
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}
 
//删除下标为k的结点后面的结点
void remove(int k){
    if(k==-1) head=ne[head];//即删除头结点
    else ne[k]=ne[ne[k]];
}
int main() {
    int m;
    cin>>m;
    init();
    while(m--)
    {
        char s;
        cin>>s;
        if(s=='D')
        {
            int k;
            cin>>k;
          	remove(k-1);
        }
        else if(s=='H')
        {
            int x;
            cin>>x;
            add_to_head(x);
        }
        else
        {
            int k,x;
            cin>>k>>x;
            add(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<' ';
    return 0;
}
 
 

2）双链表

**双链表：**此时没有头指针，固定数组前两个位置的存储，下标0的位置存储链表第一个结点（即左端点），数组下标1的位置存储链表的末尾结点（即右端点）。三个数组，数组e[]存储结点值，数组l[]指向当前结点的左结点（即前驱），数组r[]指向当前结点的右结点（即后继），idx指向当前操作位置.

AcWing 827.双链表

实现思路：类似单链表

• 注意idx初始为2，因为数组前两个位置已固定存储链表首尾结点
• 初始左端点右指向右端点，右端点左指向左端点

#include <iostream>
using namespace std;
const int N=1e6+10;
 
int e[N],l[N],r[N];
int idx;
int n;
 
//初始化
void init(){
    r[0]=1;
    l[1]=0;
    idx=2;
}
 
//在下标为k的结点的右侧插入结点   若是左侧插入结点则传入的k为l[k]
void add(int k,inx){
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];
    l[r[k]]=idx;
    r[k]=idx;
    idx++;
}
//删除下标为k的结点
void remove(int k){
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}
int main()
{
    cin>>n;
    init();
    while(n--)
    {
        string op;
        cin>>op;
        if(op=="L")
        {
            int x;
            cin>>x;
            add(0,x);
        }
        else if(op=="R")
        {
            int x;
            cin>>x;
            add(l[1],x);
        }
        else if(op=="D")
        {
            int k;
            cin>>k;
            remove(k+1);
        }
        else if(op=="IL")
        {
            int k,x;
            cin>>k>>x;
            add(l[k+1],x);
        }
        else 
        {
            int k,x;
            cin>>k>>x;
            add(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";
}