双向循环链表
| 双向循环链表 | |
|---|---|
| 术语名称 | 双向循环链表 |
| 英语名称 | circular doubly linked list |
双向循环链表(circular 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 | 人工实现 | - |
复杂度估计
空间复杂度
单向链表整体空间复杂度为线性复杂度，每个结点保存一个数据，使得结点数量与数据量成正比。但是由于结点中需要额外保存链接，比起直接保存有额外常数，考虑每段数据的大小和链接大小的关系，为 [math]\displaystyle{ \sim \frac{d+p}{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] ，只需要随着链接找到 | ||