双链表

                     

贡献者： 有机物

　　 本文对应了上一篇文章，这里讲解双链表。

　　 双链表在竞赛中用的不多，通常是因为需要优化某些问题而使用双链表。

　　 双链表上的每个结点都有 $4$ 个值，$\mathtt{Lnext}$ 指针表示它左边的结点的下标，$\mathtt{Rnext}$ 指针表示它右边的结点的下标，其他的数组和变量和单链表的存储代表一个意思。

　　 用 C++ 的指针和结构体来实现双链表：

struct Double_List
{
    int value;
    Double_List *prev, *next;  // 左指针和右指针
};

　　 这里来详细的讲解一下如何使用数组来模拟双链表。

　　 数组模拟双链表需要这么几个数组和变量：

// 为了简化代码，我们用 e 表示 value, l 表示 Lnext, r 表示 Rnext
int e[N], l[N], r[N], idx;

　　 双链表的基本操作有：

1. 在第 $k$ 个插入的数左侧插入一个数；
2. 在第 $k$ 个插入的数右侧插入一个数；
3. 将第 $k$ 个插入的数删除

　　 插入（$\text{insert}$）操作：

　　 第 $1$ 步：先让要插入的点的右指针指向第 $k$ 个插入的点右边的点

　　 第 $2$ 步：让要插入的点的左指针指向第 $k$ 个插入的点

　　 第 $3$ 步：让第 $k$ 个插入的点的右边的点的左指针指向要插入的点

　　 第 $4$ 步：让第 $k$ 个插入的点的右指针指向要插入的点

// 在第 k 个插入的数的右边插入一个数
void insert(int k, int x)
{
    e[idx] = x;         // 赋值
    r[idx] = r[k];      // 第 1 步
    l[idx] = k;         // 第 2 步
    l[r[k]] = idx;      // 第 3 步
    // r[k] 是第 k 个插入的点的右边的点，
    // l[r[k] 就是第 k 个插入的点的右边的点的左指针
    r[k] = idx ++ ;     // 第 4 步
}


// 熟练掌握了之后就可以写成一行了。
e[idx] = x, r[idx] = r[k], l[idx] = k, l[r[k]] = idx, r[k] = idx ++ ;

　　 注意：

　　 第 $1$ 步和第 $2$ 步的操作的位置可互换，但是第 $3$ 步和第 $4$ 步的位置不可互换。 因为如果先操作第 $4$ 步的话，r[k] 就是修改之后的值了，如果接下来再调用 l[r[k]] 就不对了。

　　 如果想要在第 $k$ 个插入的数的左边插入一个数怎么办呢？

　　 最直接的办法就是照着刚才的逻辑对应着再写一遍，当然还有更见简便的方法。

　　 就是直接调用

insert(l[k + 1], x);
// 注意 k 要加 1，因为 idx 从 2 开始，所以下标也从 2 开始

意思就是在第 $k$ 个插入的数的左边插入一个数。

　　 删除（$\text{remove}$）操作：

　　 双链表的删除操作和单链表的删除类似

1. 让第 $k$ 个插入的点的左边的结点的右指针指向第 $k$ 个插入的点的右边的结点
2. 让第 $k$ 个插入的点的右边的结点的左指针指向第 $k$ 个插入的点的左边的结点

　　 对应到代码上：

// 删除第 k 个插入的点
void remove(int k)
{
    r[l[k]] = r[k], l[r[k]] = l[k];
}

// l[k] 为第 k 个插入的点的左边的结点，r[l[k]] 为第 k 个插入的点的左边的结点的右指针
// r[k] 为第 k 个插入的点的右边的结点，l[r[k]] 为第 k 个插入的点的右边的结点的左指针

　　 这样，双链表的基本操作就讲完了。