使用数组模拟单链表结构

使用数组模拟链表相对于使用结构指针,拥有更高的效率（省去了动态分配内存的环节)

c++代码

#include <iostream>
using namespace std;

const int N = 1e6+10;

//头指针
int head;
//下一个可用的位置
int idx;

//存储链表值
int e[N];
//存储next指针
int ne[N];

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

//插入头节点
void insert_head(int x){
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

//向k节点后面追加一个新的节点
void insert(int k,int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

//删除k节点后面的一个元素
void remove(int k){
    ne[k] = ne[ne[k]];
}

//遍历链表
void out(){
    for(int i=head;i!=-1;i=ne[i]){
        int value = e[i];
        ...
    }
}

以下是图解各个操作的执行流程

初始化链表

(打错字了，不是“执行”，是指向)

插入头节点

在k后方插入一个新的节点

删除k的下一个节点