链表

单链表

  • 邻接表：存储图、树

head $\rightarrow \empty$

node: val, next

  • 值数组： e[N] (val数组)
  • 指针数组: ne[N] (next 数组)
  • e和ne用下标关联起来

代码

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
const int N = 100010;
// idx 存储当前已经用到哪个点
int head, e[N], ne[N], idx;

void init(){
    head = -1;
    idx = 0;
}

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

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

// 将下标是k的点后面的点删掉
void remove(int k){
    ne[k] = ne[ne[k]];
}

双链表

  • 优化问题

l[N],r[N], 0:head, 1:tail

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
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;
    r[k] = idx;
    l[r[idx]] = idx;
    idx++;
}
// add(l[k], x) 即左边插入x

void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

邻接表：n个单链表