链表

单链表(数组实现)

邻接表 用来存储图和树

e[N] 用来存储该点的val值
ne[N] 用来存储该点的next指针(指向数组下标也就是它的值就是数组下标)
(二者利用下标来进行关联)

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
// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点(哪个下标可以用,还没有用过的)
int head, e[N], ne[N], idx;

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

// 在链表头插入一个数x
void add_head(int x)
{
e[idx]=x;
ne[idx]=head;
head=idx;
idx++;
}

// 插到下标是k的点的后面
void add(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;

}
// 将下标为k的下一个的节点删除
// 因为单链表找不到前面的(不一定是按顺序连起来的,下标-1不一定是上一个点的下标)
// 要想找到上一个点只能遍历一遍
void remove(int k)
{
ne[k]=ne[ne[k]];
}

20220111122942

双链表(数组实现)

优化某些问题

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
// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

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

// 在节点k的右边插入一个数x
void add(int k, int x)
{
e[idx] = x;

r[idx] = r[k];
l[idx] = k;

l[r[k]] = idx,
r[k] = idx;

idx++;
}

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