查看“︁双向链表”︁的源代码

[[分类:线性表]]
[[分类:链式存储结构]]
{{InfoBox
|name=双向链表
|eng_name=doubly linked list
|aliases=双链表
}}
{{#seo:
|keywords=双向链表,双链表
|description=介绍了双向链表，即逻辑结构为线性表、存储结构为链式、结点拥有指向上下结点链接的数据结构，即结点拥有指向上下结点链接的链表。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2024-11-10
}}
'''双向链表'''('''doubly linked list''')或'''双链表'''指逻辑结构为[[线性表]]、存储结构为[[链式存储结构]]（即属于[[链表]]），且结点间同时存在指向上个结点和下个结点的两个链接（头尾结点除外）。

在[[编程语言]]中，通常不直接提供链表结构。如果实际提供，通常都是双向链表而不是简单的[[单向链表]]。

在内存中，链表分配和访问内存的方式不符合[[访问局部性原理]]，对[[缓存]]不友好，执行效率会按照缓存与内存的访问时间比例成数量级地放大，因此通常会使用[[动态数组]]代替。但是动态数组中间插入时间复杂度较高，必须要插入中间段时，会使用[[块状链表]]作为代替。

外存中，文件间通过文件名的双向链表链接是常见做法，特别是用于文件很多且允许向文件间插入或删除文件的情况。

== 结构 ==

双向链表中的每个结点可以抽象成如图所示结构。

{{GiteaSvg|doubly_linked_node}}

其中含有数据域和指向上下两个结点的链接，链接通常画在数据域两侧（但是内存排布一般把两个链接放在一起），以便绘制成链。链接成一个链表时如下图所示。

{{GiteaSvg|doubly_linked_list}}

这个结构只需要获取第一个或最后一个结点，就可以顺藤摸瓜地找到整个结构。
如果只保存一个能取得第一个结点的数据，保存这个数据的变量通常称为 <code>head</code> ，也称为'''头指针'''('''head pointer''', '''head reference''')。
如果也保存用于取得最后一个结点的数据，保存这个数据的变量通常称为 <code>tail</code> 或 <code>rear</code> ，也称为'''尾指针'''('''tail pointer''', '''tail reference''', '''rear pointer''', '''rear reference''')。

类似单向链表，有时也保存一个虚拟结点，称为'''头结点'''('''head node''')。头结点中的链接就相当于上一个方法中的头指针。
具有头结点的双向链表往往被实现为双向循环链表，也就是说第一个和最后一个结点都和头结点相连接。

== 语言实例 ==

{{数据结构实例
|c=人工实现
|cpp=[https://en.cppreference.com/w/cpp/container/list <syntaxhighlight inline lang="cpp">std::list</syntaxhighlight>]
|cpp_ex=STL
}}

== 实现实例 ==

{{Libcxx|libcxx/include/list|https://github.com/llvm/llvm-project/blob/9a3e66e314e698ffb08dba151bc098b6b8867c61/libcxx/include/list#L663}}

{{Libstdc++|libstdc++-v3/include/std/list|https://github.com/gcc-mirror/gcc/blob/7eecc08ccf75679e6ae688d92e50afae935547ab/libstdc%2B%2B-v3/include/bits/stl_list.h#L632}}

== 复杂度估计 ==

=== 空间复杂度 ===

双向链表整体空间复杂度为[[线性复杂度]]，每个结点保存一个数据，使得结点数量与数据量成正比。但是由于结点中需要额外保存链接，比起直接保存有额外常数，考虑每段数据的大小和链接大小的关系，为 <math>\sim \frac{d+2p}{d} n=O(n)</math> 。

=== 时间复杂度 ===

本节讨论双向链表数组对其逻辑结构线性表的操作实现。

双向链表中的特殊操作与单向链表相同，是[[头插法]]。由于双向链表结构上更加前后对称，没有单独的尾插法问题。

==== 时间复杂度总结 ====

记链表长度为 <math>n</math> 。

{| class='wikitable' style='width:100%'
! colspan=2 | 操作
! 最好
! 最坏
! 平均
|-
! rowspan=3 | 基本操作
! 初始化 <code>Create</code>
| colspan=3 | 不初始化结点为一次分配
|-
! 长度 <code>Length/Size</code>
| colspan=3 | <math>O(n)</math> ，如果没维护则需要遍历
|-
! 清空
| colspan=3 | <math>O(n)</math> ，逐个结点销毁
|-
! rowspan=4 | 元素获取
! 指定索引 <code>Get(i)</code>
| <math>\Theta(1)</math> ，起始或结束位置
| <math>\tfrac{n}{2} = \Theta(n)</math> ，中间位置
| <math>\sim \operatorname{max}(i,n-i)\sim \tfrac{n}{4}=\Theta(n)</math> ，需要遍历到指定位置
|-
! 指定位置 <code>Get(p)</code>
| colspan=3 | <math>\Theta(1)</math>
|-
! 头部 <code>Head</code>
| colspan=3 rowspan=2 | <math>\Theta(1)</math>
|-
! 尾部 <code>Rear</code>
|-
! rowspan=4 | 插入删除
! 指定索引 <code>Insert(i,x)/Remove(i)</code>
| <math>\Theta(1)</math> ，起始或结束位置
| <math>\tfrac{n}{2} = \Theta(n)</math> ，中间位置
| <math>\sim \operatorname{max}(i,n-i)\sim \tfrac{n}{4}=\Theta(n)</math> ，平均遍历长度
|-
! 指定位置 <code>Insert(p,x)/Remove(p)</code>
| colspan=3 | <math>\Theta(1)</math> ，只需要插入删除结点后连接指针
|-
! 头部
| colspan=3 rowspan=2 | <math>\Theta(1)</math>
|-
! 尾部
|-
! rowspan=2 | 元素顺序
! 指定位置前趋/后继 <code>Pred/Succ</code>
| colspan=3 | <math>\Theta(1)</math> ，只需要随着链接找到
|}


{{数据结构}}