双链表详解：定义、存储结构与基本操作

双链表详解：定义、存储结构与基本操作

双链表是计算机科学中一种重要的数据结构，它在每个节点中存储了两个指针，分别指向其前一个和后一个节点。这种结构使得双链表在插入和删除操作上具有较高的效率，特别是在需要频繁进行这些操作的场景中。本文将详细介绍双链表的定义、存储结构以及基本操作的实现方法。

双链表的基本概念

双链表在竞赛中用的不多，通常是因为需要优化某些问题而使用双链表。双链表上的每个结点都有 $4$ 个值，$\mathtt{Lnext}$ 指针表示它左边的结点的下标，$\mathtt{Rnext}$ 指针表示它右边的结点的下标，其他的数组和变量和单链表的存储代表一个意思。

使用C++实现双链表

用 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$ 个插入的数删除

插入操作

在第 $k$ 个插入的数的右边插入一个数：

1. 第 $1$ 步：先让要插入的点的右指针指向第 $k$ 个插入的点右边的点
2. 第 $2$ 步：让要插入的点的左指针指向第 $k$ 个插入的点
3. 第 $3$ 步：让第 $k$ 个插入的点的右边的点的左指针指向要插入的点
4. 第 $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 开始

删除操作

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

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 个插入的点的右边的结点的左指针

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