head 表示头结点的下标
e[i] 表示节点i的值
ne[i] 表示节点i的next指针是多少 (下一个节点的下标)
idx 存储当前已经用到了哪一个点

[数组模拟单链表] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int head,e[N],ne[N],idx;

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

void add_to_head(int x) //将x插到头结点
{
    e[idx]=x;//这个结点赋值
    ne[idx]=head;//新头结点的下一个结点是之前的头结点
    head=idx; head变成新的头结点的下标
    idx++;
}

void add(int k,int x)//将x插到下标为k的位置的后面 注意不是第k个点 是下标为k的点
{
    e[idx]=x;//还是先赋值到新节点
    ne[idx]=ne[k]; //新节点的下一个坐标更新为k节点原本的下一个坐标
    ne[k]=idx;//k的下一个下标是新节点
    idx++;
}

void remove(int k,int x) //删掉k之后的一个元素
{
    ne[k]=ne[ne[k]];直接跳过就得了
}
遍历
for(int i=head;i!=-1;i=ne[i]) 略


每个点有两个指针

[数组模拟双链表] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const int N=100010;

int m;
int e[N],l[N],r[N],idx; l是左边的点的下标 r是右边的点的下标

void init()
{
    r[0]=1;
    l[1]=0;
    idx =2;//0 1已经被占用过了
}

void add(int k, int x) 在下标为k的点的右边插入x
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;//注意倒数二三个不能换位置 不然没法完成
    r[k]=idx;
    idx++;
}
在k的左边 直接add(l[k],int x)

void remove(int k) //删除第k个节点
{
    r[l[k]]=r[k]; //k上一个元素的右边下标直接等于k右边边的元素下标
    l[r[k]]=l[k]; //k下一个元素的左边下标直接等于k左边的元素下标
}

for (int i = r[0]; i != 1; i = r[i])  // 从左向右遍历
        cout << e[i] <<" ";

邻接表 就是n个单链表