本笔记内容来源于算法基础课

链表

class Node {
    int val;
    Node next;
}

此种定义方式需要对每一个元素都创建节点，申请空间的时间容易超时

因此常采用数组模拟的方式

单链表

node -> node -> null
 ↑               ↑
head            -1

每个节点使用数组的下标进行标号，从0开始，空节点下标用-1表示
head 表示头节点的下标
e[i] 表示节点i的值
ne[i] 表示节点i的即下一个元素的下标
idx 表示当前分配元素的哨兵

初始化

void init() {
    head = -1; // 空节点为-1，此时头节点为空节点
    idx = 0;
}

插入到头节点，成为新的头节点

void add_to_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]; // 新节点的下一个元素指向k的后一个元素
    ne[k] = idx; // k的下一个元素指向新节点
    idx++;
}

删除下标是k的节点的后一个节点删除

void remove(int k) {
    ne[k] = ne[ne[k]]; // k的下一个元素指向下一个的下一个元素
}

遍历链表

for (int i = head; i != -1; i = ne[i]) {
    ......
}

双链表

node <-> node <-> null
 ↑        ↑
 0        1

下标为0代表虚拟头节点，下标为1代表虚拟尾节点，当中不包含真实的值
e[i] 表示节点i的值
l[i] 表示节点左边的元素下标
r[i] 表示节点右边的元素下标
idx 表示当前分配元素的哨兵

初始化

void init() {
    r[0] = 1;
    l[1] = 0; // 初始两个虚拟节点互相连接
    idx = 2;  // 0，1分配给虚拟节点，从2开始分配新元素
}

插入到k结点的右边

void add(int k, int x) {
    e[idx] = x; // 创建新节点
    r[idx] = r[k]; // 新节点的右边指向k的右元素
    l[idx] = k;  // 新节点的左边指向k
    l[r[k]] = idx;  // k的右元素的左边指向新节点
    r[k] = idx; // k的右元素指向新节点，两个操作需要注意先后顺序 
    idx++;
}

插入到k节点的左边，等价于插入到l[k]的右边

add(l[k], x);

删除k节点

void remove(int 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]) {
    ......
}

邻接表

邻接表是N个个单链表

可以用来存储图和树