单向循环链表

循环链表 ​

Cyclic Linked List

对于一般的链表其末尾节点的指针域指向一个空的节点。而循环链表则指向头节点。

graph LR
    b[ ] --> a
	a[head] --> 1
	1 --> 2
	2 --> 3
	3 --> 4
	4 --> 5
	5 --> 6
	6 --> a

如果链表没有头节点，那么它的指针域指向自己也是可以的：

graph TD
    b[ ] --> a
	a[第一个节点] --> a

当然，如果看到链表的末尾不是指向头，而是其他的数据也不要惊讶（只是不太常见）：

graph LR
    b[ ] --> a
	a[head] --> 1
	1 --> 2
	2 --> 3
	3 --> 4
	4 --> 5
	5 --> 6
	6 --> 3

循环链表的优点 ​

在单向链表中，如果我们获得的指针不是头结点，而是中间位置的指针。那么，我们无法访问到链表的所有节点。而双向链表的设计很好解决了这个问题，而且它在大多数的操作上和普通单向链表没有差异。

存储结构 ​

和单向链表差不多，只是头节点初始化的时候其指针域指向自己。这样之后在插入过程中，会将这个指向传递。

基本操作 ​

• 插入数据：循环链表的插入数据和单向链表的插入是一模一样的，因为插入操作之和插入位置的前一个位置有关。
• 通过下标读取数据：也是和单向链表的读取一模一样的，头尾用 0 和 len -1 下标获取。
• 通过下标删除数据：也是和单向链表的删除一模一样的，头尾用 0 和 len - 1 下标获取。

综上所述，循环链表只有在头结点初始化的时候，需要将指针域指向自身，其他内容和一般的单向链表一样。

代码实现 ​

view in source code. 因为和普通链表基本一样，所以很简略，记得搭配单向链表的代码查看。

算法应用 ​

• 约瑟夫问题