单向循环链表
| 单向循环链表 | |
|---|---|
| 术语名称 | 单向循环链表 |
| 英语名称 | circular singly linked list |
单向循环链表(circular singly linked list)指逻辑结构为线性表、存储结构为链式存储结构（即属于链表），且结点间只存在指向下个结点的链接（尾结点除外）的数据结构。其是单向链表变体，尾结点不再为空，而是指向第一个数据结点，如果有头结点（哨兵结点）则指向头结点，形成一个循环的结构。
与单向链表类似，在内存中，链表分配和访问内存的方式不符合访问局部性原理，对缓存不友好，执行效率会按照缓存与内存的访问时间比例成数量级地放大。因此真正需要链表时往往通过内存池方案预分配结点块，或者结合自由链表的形式复用存储上局部化的结点，减少内存碎片。
与单向链表不同的是，由于链接成环，单向循环链表可以从其中任意一个结点开始循环遍历全部结点。如果需要较高性能，且结构上不需要具体的头尾，甚至可以进一步将尾结点的下一链接指向上一结点，留下一个指向环中任意位置的指针，并忽略头尾将所有结点视为有着循环前后顺序的的结点。
结构
单向循环链表中的结点与普通单向链表相同，可以抽象成如图所示结构。
其中含有数据域和指向下个结点的链接。链接成一个链表时如下图所示，较普通的单向链表增加了一个从最后一个结点指回第一个结点的指针。
与单向链表相似，循环链表通常保存一个头指针(head pointer, head reference)或加入一个头结点(head node)/哨兵结点(sentinel node)。
语言实例
| 单向循环链表 | |||
|---|---|---|---|
| 语言 | 版本/库 | 对应内容 | 说明 |
| C | C89 | 人工实现 | - |
| C++ | C++98 | 人工实现 | - |
GSSDS 定义
GSSDS: array/include/sds/circular_linked_list/circular_linked_list.h
复杂度
空间复杂度
单向循环链表整体空间复杂度为线性复杂度，每个结点保存一个数据，使得结点数量与数据量成正比。但是由于结点中需要额外保存链接，比起直接保存有额外常数，考虑每段数据的大小和链接大小的关系，为 [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{ \Theta(n) }[/math] ，结束位置 | [math]\displaystyle{ \sim i\sim \tfrac{n}{2}=O(n) }[/math] ，需要遍历到指定位置 |
指定位置 Get(p)
|
[math]\displaystyle{ \Theta(1) }[/math] | |||
头部 Head
|
[math]\displaystyle{ \Theta(1) }[/math] | |||
尾部 Rear
|
[math]\displaystyle{ \Theta(n) }[/math] ，若需要遍历到尾部 | |||
| 插入删除 | 指定索引 Insert(i,x)/Remove(i)
|
[math]\displaystyle{ \Theta(1) }[/math] ，头部 | [math]\displaystyle{ \Theta(n) }[/math] ，尾部 | [math]\displaystyle{ \sim i\sim \tfrac{n}{2}=\Theta(n) }[/math] ，平均遍历长度 |
指定位置 InsertAfter(p,x)/RemoveAfter(p) *
|
[math]\displaystyle{ \Theta(1) }[/math] ，只需要插入删除结点后连接指针 | |||
| 头部 | [math]\displaystyle{ \Theta(1) }[/math] | |||
| 尾部 | [math]\displaystyle{ \Theta(n) }[/math] ，需要遍历找到尾部或其前结点 | |||
| 元素顺序 | 指定位置前趋 Pred
|
[math]\displaystyle{ \Theta(1) }[/math] ，头部 | [math]\displaystyle{ \Theta(n) }[/math] ，尾部 | [math]\displaystyle{ \sim i\sim \tfrac{n}{2}=\Theta(n) }[/math] ，平均遍历长度 |
指定位置后继 Succ
|
[math]\displaystyle{ \Theta(1) }[/math] ，只需要随着链接找到 | |||
- 由于单向循环链表中直接操作一个结点往往需要修改前后结点的指针，一般指定其前一结点的位置而不是本结点，根据链表连接关系得到本结点和下一结点，所以和线性表词条中的定义不同。