算法竞赛基础：双向链表
本文将会介绍在算法竞赛中双向链表的几种使用方式，适合有一定基础的人阅读。
双向链表的结构
一般来说，普通的链表结构是这样的：
struct node {
int num;
node *next;
}
next指针指向下一个链表，这样的结构只能够支持单向查询。
双向链表，顾名思义，就是可以支持双向的访问和查询。
也就是这样的：
struct node {
int num;
node *l, *r;
}
这种链表为访问前后的元素提供的很大的便利性。
C++的STL模板中也有类似的结构：
List
list<int> lis;
List是连续的容器，而vector是非连续的容器，即list将元素存储在连续的存储器中，而vector存储在不连续的存储器中。
向量（vector）中间的插入和删除是非常昂贵的，因为它需要大量的时间来移动所有的元素。链表克服了这个问题，它是使用list容器实现的。
List支持双向，并为插入和删除操作提供了一种有效的方法。
在列表中遍历速度很慢，因为列表元素是按顺序访问的，而vector支持随机访问。
列表模板
示例
#include<iostream>
#include<list>
using namespace std;
int main()
{
list<int> l;
}
它创建一个空的整数类型值列表。
列表也可以使用参数初始化。
示例
#include<iostream>
#include<list>
using namespace std;
int main()
{
list<int> l{1,2,3,4};
}
列表可以通过两种方式初始化。
示例
list<int> new_list{1,2,3,4};
or
list<int> new_list = {1,2,3,4};
list支持的操作有以下这些：
| 方法 | 描述 |
|---|---|
| insert() | 它将新元素插入到迭代器指向的位置之前。 |
| push_back() | 它在容器的末尾添加了一个新元素。 |
| push_front() | 它在前面增加了一个新元素。 |
| pop_back() | 删除最后一个元素。 |
| pop_front() | 删除第一个元素。 |
| empty() | 它检查列表是否为空。 |
| size() | 它查找列表中存在的元素数。 |
| max_size() | 它找到列表的最大大小。 |
| front() | 它返回列表的第一个元素。 |
| back() | 它返回列表的最后一个元素。 |
| swap() | 当两个列表的类型相同时，它将交换两个列表。 |
| reverse() | 它反转了列表的元素。 |
| sort() | 它以递增的顺序对列表中的元素进行排序。 |
| merge() | 它合并两个排序的列表。 |
| splice() | 它将新列表插入到调用列表中。 |
| unique() | 它从列表中删除所有重复的元素。 |
| resize() | 它更改列表容器的大小。 |
| assign() | 它将一个新元素分配给列表容器。 |
| emplace() | 它将在指定位置插入一个新元素。 |
| emplace_back() | 它将在容器的末尾插入一个新元素。 |
| emplace_front() | 它将在列表的开头插入一个新元素。 |
| erase() | 删除这个元素 |
但是这种结构往往在大量数据的情况下会超时。我们需要一种更加有效的方式，通常，我们选择空间换时间，因此静态链表通常是更好的选择，接下来介绍一种静态双向循环链表在竞赛中实现的方式。
竞赛方式实现
思路是这样的：
要实现一个静态双向循环链表，需要模拟一个左右指针，在这里，我们选择花费大量空间去用数组的下标代替指针和对应的值：
#include <bits/stdc++.h>
using namespace std;
const int MAX_N 1e5 + 10;
struct node {
int l, r;
int key;
} arr[MAX_N] = {0};
其中，l和r分别表示上一个和下一个元素的数组下标。
插入操作
插入操作的思路很简单：
先将新元素的l和r指向左右两个元素。
再分别让左右两个元素的r和l分别指向新元素本身；
//ll:左元素，rr:右元素, new:新元素
void add(int ll， int rr, int new) {
arr[new].l = ll;
arr[new].r == rr;
arr[ll].r == new;
arr[rr].l == new;
}
这不是一种唯一的实现方式，其中的参数和需求都可以根据具体情况改变。
删除操作
删除操作提供两种思路：
- 第一种与插入操作类似，实现元素的删除
- 第二种更加快速，通过在节点种的key值，去判断是否输出（如果要求输出链表的话）
第一种方式：
void del(int target) {
int l, r;
l = arr[target].l;
r = arr[target].r;
arr[l].r = r;
arr[r].l = l;
第二种方式：
void del(int target) {
arr[target].key = 0; //在对链表元素进行操作时，检测其key值的真值，如果为0，直接不对其进行操作
}
第二种方式虽然没有改变l和r的值，但是也能够实现链表访问机制的修改而且还支持数据恢复，相当好用。
查找操作
这种方式是基于上面删除操作时的第二种方式实现的：
bool find(int target) {
return arr[target].key == 1;
}
因为这种特殊的链表结构支持随机访问（正常的链表结构是不支持的），所以查找操作变成检测对应元素的键值是否有效，如果有效，返回一个真值。
遍历操作
以输出全部数值为例：
这里值得一提的是，如果按照这种上文所述的方式去建立双向链表的话，你会发现没有头结点。
具体原因是由于开辟第一个结点时，也就是数组下标为1的时候，结构体中的
l和r指向的是1本身，那这个时候如果再多插入几个结点，最后一个结点的r会指向1，1的l会指向最后一个结点，这样一来，当你在1之前插入结点时，按理来说头节点会变成新插入的结点，但由于缺少一个指向头节点的指针而丢失链表的头，这显然是我们不想看到的。
解决方法也很简单，我们在数组下标为0的位置创建一个结点作为虚拟头结点，当在真正的头结点之前插入新的结点时，这时候新结点会在0和头节点之间，当我们需要访问头节点的时候，通过0去访问就可以了。
下面是建立的虚拟头节点0之后的遍历输出操作：
void bs() {
// from left to right
for (int i = arr[0].r; i; i = arr[i].r) {
cout << arr[i] << " ";
}