Homepage of Jinghua Xu

链表与邻接表

【一般实现方式：指针+结构体——动态链表（工程中常用）】

struct Node
{
	int val;
    Node *next;
}

new Node(); // 非常慢，若要使用可以初始化n个节点

这里介绍用数组模拟【静态链表】该数据结构的方式——速度快！

单链表

单链表中用的最多的是邻接表——n个单链表：将每个点（共有n个点）的所有邻边存下来

邻接表应用：存储图和树（e.g. 最短路问题、最小生成树问题、……）

单链表基本结构：从头指针开始依次指向若干个节点，每个节点存储一个数值val和一个next指针，沿着next指针不断访问后续数据，直到指向空指针

数组模拟链表存储需要定义（均为整数型数组）：

• e[N]：存储各点数值val
• ne[N]：存储各点next指针——空节点下标用-1表示

二者通过下标关联 ：

事实上，同一下标i对应的e[i]与ne[i]表示一个节点的数值val及其next指针，将其看作一个结构体会更好理解，但在代码实现过程中，为使得代码尽量简洁，选择直接对数组下标进行操作

// 结构体写法
struct Node
{
    int e, ne;
}nodes[N];

// 以删除为例：删除下标是k的节点“后面”的一个节点
void remove(int k)
{
    // 直接让k节点指向的节点变成其后的节点指向的节点
    nodes[k].ne = nodes[nodes[k].ne].ne;   
}

需要注意：一个下标代表一个节点，各节点之间的指向关系仅由next指针（即ne[i]的值）决定

单链表的性质：顺序（单向）访问——可以在O(1)的时间复杂度内找到指定节点的后一个节点（包括完成插入等操作），但如果要找到指定节点之前的节点，则只能从头指针head开始遍历

---

例题：826. 单链表 - AcWing题库

实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数；
2. 删除第 k 个插入的数后面的一个数；
3. 在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：