双向链表
| 双向链表 | |
|---|---|
| 术语名称 | 双向链表 |
| 英语名称 | doubly linked list |
| 别名 | 双链表 |
双向链表(doubly linked list)或双链表指逻辑结构为线性表、存储结构为链式存储结构（即属于链表），且结点间同时存在指向上个结点和下个结点的两个链接（头尾结点除外）。
在编程语言中，通常不直接提供链表结构。如果实际提供，通常都是双向链表而不是简单的单向链表。
在内存中，链表分配和访问内存的方式不符合访问局部性原理，对缓存不友好，执行效率会按照缓存与内存的访问时间比例成数量级地放大，因此通常会使用动态数组代替。但是动态数组中间插入时间复杂度较高，必须要插入中间段时，会使用块状链表作为代替。
外存中，文件间通过文件名的双向链表链接是常见做法，特别是用于文件很多且允许向文件间插入或删除文件的情况。
结构
双向链表中的每个结点可以抽象成如图所示结构。
其中含有数据域和指向上下两个结点的链接，链接通常画在数据域两侧（但是内存排布一般把两个链接放在一起），以便绘制成链。链接成一个链表时如下图所示。
这个结构只需要获取第一个或最后一个结点，就可以顺藤摸瓜地找到整个结构。
如果只保存一个能取得第一个结点的数据，保存这个数据的变量通常称为 head ，也称为头指针(head pointer, head reference)。
如果也保存用于取得最后一个结点的数据，保存这个数据的变量通常称为 tail 或 rear ，也称为尾指针(tail pointer, tail reference, rear pointer, rear reference)。
类似单向链表，有时也保存一个虚拟结点，称为头结点(head node)。头结点中的链接就相当于上一个方法中的头指针。 具有头结点的双向链表往往被实现为双向循环链表，也就是说第一个和最后一个结点都和头结点相连接。
语言实例
| 双向链表 | |||
|---|---|---|---|
| 语言 | 版本/库 | 对应内容 | 说明 |
| C | C89 | 人工实现 | - |
| C++ | C++98 | std::list
|
STL |
实现实例
libstdc++: libstdc++-v3/include/std/list
复杂度估计
空间复杂度
双向链表整体空间复杂度为线性复杂度，每个结点保存一个数据，使得结点数量与数据量成正比。但是由于结点中需要额外保存链接，比起直接保存有额外常数，考虑每段数据的大小和链接大小的关系，为 [math]\displaystyle{ \sim \frac{d+2p}{d} n=O(n) }[/math] 。
时间复杂度
本节讨论双向链表数组对其逻辑结构线性表的操作实现。
双向链表中的特殊操作与单向链表相同，是头插法。由于双向链表结构上更加前后对称，没有单独的尾插法问题。
时间复杂度总结
记链表长度为 [math]\displaystyle{ n }[/math] 。
| 操作 | 最好 | 最坏 | 平均 | |
|---|---|---|---|---|
| 基本操作 | 初始化 Create
|
不初始化结点为一次分配 | ||
长度 Length/Size
|
[math]\displaystyle{ O(n) }[/math] ，如果没维护则需要遍历 | |||
| 清空 | [math]\displaystyle{ O(n) }[/math] ，逐个结点销毁 | |||
| 元素获取 | 指定索引 Get(i)
|
[math]\displaystyle{ \Theta(1) }[/math] ，起始或结束位置 | [math]\displaystyle{ \tfrac{n}{2} = \Theta(n) }[/math] ，中间位置 | [math]\displaystyle{ \sim \operatorname{max}(i,n-i)\sim \tfrac{n}{4}=\Theta(n) }[/math] ，需要遍历到指定位置 |
指定位置 Get(p)
|
[math]\displaystyle{ \Theta(1) }[/math] | |||
头部 Head
|
[math]\displaystyle{ \Theta(1) }[/math] | |||
尾部 Rear
| ||||
| 插入删除 | 指定索引 Insert(i,x)/Remove(i)
|
[math]\displaystyle{ \Theta(1) }[/math] ，起始或结束位置 | [math]\displaystyle{ \tfrac{n}{2} = \Theta(n) }[/math] ，中间位置 | [math]\displaystyle{ \sim \operatorname{max}(i,n-i)\sim \tfrac{n}{4}=\Theta(n) }[/math] ，平均遍历长度 |
指定位置 Insert(p,x)/Remove(p)
|
[math]\displaystyle{ \Theta(1) }[/math] ，只需要插入删除结点后连接指针 | |||
| 头部 | [math]\displaystyle{ \Theta(1) }[/math] | |||
| 尾部 | ||||
| 元素顺序 | 指定位置前趋/后继 Pred/Succ
|
[math]\displaystyle{ \Theta(1) }[/math] ，只需要随着链接找到 | ||