链表 | OI笔记

单链表

English Time

init 初始化
initialize [ɪˈnɪʃəlaɪz] 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的指针指向
dx 存储当前用到的地址数量，同时存储可用的数组下标位置

单链表的初始化

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

单链表的插入操作

头节点处插入：

void add_to_head(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 个单链表，存储每个点所有的邻边

链表用途：

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

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

循环链表

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

块状链表

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