链表
一种线性数据结构，可以在 $\operatorname O(1)$ 内完成表头处的插入和删除，在已知下标情况下，可以对特定位置实现 $\operatorname O(1)$ 的插入和删除。
链表重要的有四部分：表头（$h$），$next$ 指针，代表数组（e）和索引变量（$idx$）。
具体实现为表头指向节点，节点拥有数值数组和 $next$ 指针，其中数值数组用于存储 $id$ 和数值，$next$ 指针用于指向下一个节点（的下标）。如下图：
![[Pasted image 20250730202816.png|500]]
链表内节点的下标存储是不连续的，你很难直接去通过下标去访问一个元素，如果要访问，一般只有通过遍历这一种方式（如果实时存储下标则可以实现 $\operatorname O(1)$ 查询，但比较复杂）。
主要支持：插入，删除两种操作
表头一般初始化为 $-1$ 以方便后续使用。
## 数组模拟
##### 插入
遵从先旧再新的原则，主要分为两步，先让新点的 $next$ 指向表头所指向的下标，然后让表头指向新点即可。先添后改。
如下图：
![[Pasted image 20250730203528.png|225]]
代码为：
```cpp
int h = -1, ne[N], e[N], idx; // 表头，next，数值，索引变量
void add(int x) // 添加点 x
{
ne[idx] = h, e[idx] = x, h = idx ++ ;
}
```
```cpp
void add(int x, int v) // 此是
{
ne[idx] = ne[x], e[idx] = v, ne[x] = idx ++ ;
}
```
##### 删除
在链表中，遍历从表头开始，只要断开联系，就相当于删除。如果要删除一个数，只需要使原本指向这个数的指针 指向 这个数所指的**数**即可。
如图：
![[Pasted image 20250730204328.png|325]]
代码为：
```cpp
int h = -1, ne[N], e[N], idx; // 表头，next，数值，索引变量
void remove() // 删除
{
h = ne[h]; // 即指向x所指向的即可，相当于跳过了x
}
```
```cpp
void remove(int h, int x) // 删除链表h 第x个数
{
for (int i = h; i != -1; i = ne[i])
{
if (e[ne[i]] == x) ne[i] = ne[ne[i]];
}
}
```
双链表和单链表相似，就是多了一个做指针，可以回去，除此之外没有差别。（极少用到）
## 动态链表
比起来模拟的链表来说，动态链表可以动态调整空间使用，但是效率会相对低一些（涉及增删点）。
## 应用
链表的一个重要应用就是链式前向星。