链表 | 学习笔记

单链表

$English\ Time$

$init$ 初始化
$initialize$ $v.$ 初始化

单链表图解

单链表定义：

定义方式1：

struct Node {
    int val;
    Node *Next;
};

new Node();

缺点：$new$ 函数效率极低

定义方式2：

数组模拟静态链表

int head, val[100], Next[100], idx = 0;

优点：静态链表，效率高

$head$ 表示头节点的下标
$val_i$ 表示节点i的值
$Next_i$ 表示节点i的指针指向
$idx$ 存储当前用到的地址数量，同时存储可用的数组下标位置

单链表的初始化

void init() {
    head = -1; // -1 表示空集
    idx = 0; // 使用了多少个节点(数组的最大下标)
}

单链表的插入操作

头节点处插入：

void add(int x) {
    val[idx] = x; // 从 0 开始存储
    Next[idx] = head;	
    head = idx ++;
    // head 表示指向头节点，但位置不一定是第一个，而是idx
	// 也就是说数组中各数排列的顺序不一定是链表的逻辑顺序
}

一般化插入(将值为 $x$ 的值插入下标为 $k$ 的节点后)：

void add(int x， int k) {
	val[idx] = x;
	nxt[idx] = nxt[k];
	nxt[k] = idx ++;
}

单链表的删除节点操作

将下标为 k 的节点后面的第一个节点删掉，直接将 $k$ 的 $nxt$ 指向后面第二个元素即可

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

双链表

相比于单链表，双链表多维护了当前点前一个位置的数

链表中 $val$ 表示存储遇的值， $l$ 指向该节点左侧节点的地址， $r$ 指向该节点右侧节点的地址。

在双链表中， $head $指向第 $0$ 个点， $tail$ 指向第 $1$ 个点

双链表图解

双链表初始化

int val[N + 10], l[N + 10], r[N + 10], idx;
void init() {
	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; // 对 idx 右侧的节点指针进行处理
	r[k] = idx; // 对 idx 左侧的节点指针进行处理
	idx ++;
}

如果要在 $k$ 的左边插入一个点，那么只需要进行：
add(l[k])

双链表删除操作

(在第 $k$ 个点右边删除一个点)

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

邻接表

开 $n$ 个单链表，存储每个点所有的邻边

链表用途：

单链表 -> 邻接表 -> 存储树和图
双链表 -> 做优化

邻接表详解及应用，见第三章图论[邻接表]

循环链表

尾节点指向头节点，构成首尾相连的一个环

块状链表

块状链表基本原理就是链表的每个元素不是只能存一个元素，而是能存更多的元素，一般元素数量我们取 $\sqrt n$ 个，这样能让所有操作的时间复杂度都达到 $O(\sqrt n)$。