链表

发表于 分类于 阅读次数：
本文字数： 924 阅读时长 ≈ 1 分钟

单链表(数组实现)

邻接表 用来存储图和树

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];
}