双向链表是什么



本页面将简要介绍链表。

链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。

链表和数组都可用于存储数据。与链表不同，数组将所有元素按次序依次存储。不同的存储结构令它们有了不同的优势：

链表因其链状的结构，能方便地删除、插入数据，操作次数是 。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 。

数组可以方便地寻找并读取数据，在随机访问中操作次数是 。但删除、插入的操作次数是 次。

单向链表中包含数据域和指针域，其中数据域用于存放数据，指针域用来连接当前结点和下一节点。

双向链表中同样有数据域和指针域。不同之处在于，指针域有左右（或上一个、下一个）之分，用来连接上一个结点、当前结点、下一个结点。

流程大致如下：

1. 初始化待插入的数据 ；
2. 将 的 指针指向 的下一个结点；
3. 将 的 指针指向 。

具体过程可参考下图：

代码实现如下：

将链表的头尾连接起来，链表就变成了循环链表。由于链表首尾相连，在插入数据时需要判断原链表是否为空：为空则自身循环，不为空则正常插入数据。

大致流程如下：

1. 初始化待插入的数据 ；
2. 判断给定链表 是否为空；
3. 若为空，则将 的 指针和 都指向自己；
4. 否则，将 的 指针指向 的下一个结点；
5. 将 的 指针指向 。

具体过程可参考下图：

代码实现如下：

在向双向循环链表插入数据时，除了要判断给定链表是否为空外，还要同时修改左、右两个指针。

大致流程如下：

1. 初始化待插入的数据 ；
2. 判断给定链表 是否为空；
3. 若为空，则将 的 和 指针，以及 都指向自己；
4. 否则，将 的 指针指向 ;
5. 将 的 指针指向 的右结点；
6. 将 右结点的 指针指向 ；
7. 将 的 指针指向 。

代码实现如下：

设待删除结点为 ，从链表中删除它时，将 的下一个结点 的值覆盖给 即可，与此同时更新 的下下个结点。

流程大致如下：

1. 将 下一个结点的值赋给 ，以抹掉 ；
2. 新建一个临时结点 存放 的地址；
3. 将 的 指针指向 的下下个结点，以抹掉 ；
4. 删除 。此时虽然原结点 的地址还在使用，删除的是原结点 的地址，但 的数据被 覆盖， 名存实亡。

具体过程可参考下图：

代码实现如下：

流程大致如下：

1. 将 左结点的右指针指向 的右节点；
2. 将 右结点的左指针指向 的左节点；
3. 新建一个临时结点 存放 的地址；
4. 将 的右节点地址赋给 ，以避免 变成悬垂指针；
5. 删除 。

代码实现如下：

异或链表（XOR Linked List）本质上还是 双向链表，但它利用按位异或的值，仅使用一个指针的内存大小便可以实现双向链表的功能。

我们在结构 中定义 ，即前后两个元素地址的 按位异或值。正向遍历时用前一个元素的地址异 或当前节点的 可得到后一个元素的地址，反向遍历时用后一个元素的地址异或当前节点的 又可得到前一个的元素地址。 这样一来，便可以用一半的内存实现双向链表同样的功能。

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/7130.html