循环链表

今天药忘吃喽~ 2023-10-05 20:33 2阅读 0赞

### 前文回顾 ###

在 [单链表][Link 1] 中，我们重点介绍了单链表，涉及到单链表的结构以及单链表元素的读取、插入、删除。

这篇文章将对循环链表进行简单的介绍。

### 举例 ###

先举个例子吧，这里就直接引用《大话数据结构》上的例子了：

> 你是一个业务员，住在上海，需要在下图的各个城市出差。从上海出发，到北京后再返回上海。  
> ![在这里插入图片描述][20210307154915442.png]
> 
> --------------------
> 
> 有次，你先到南京开会，然后要将上述所有城市走个遍（上海、苏州、无锡、常州、镇江、南京、蚌埠、徐州、上海、济南、天津、北京）。这时候有人说你得先回到上海，因为上海是第一站。此时你会咋想，是不是「这个人智障吧」，我明明可以先走完蚌埠、徐州、上海、济南、天津、北京之后再去上海、苏州、无锡、常州、镇江这几个地方出差。
> 
> --------------------
> 
> 分析下:
> 
> 1.  对方那个人的思维是「单链表」的思维，找到某个元素后再想找到某个元素就得从 **头** 开始遍历
> 2.  你将北京和上海连起来后，从当中的某个结点开始遍历整个链表，解决了上述单链表解决不了的问题。

### 定义 ###

再说下循环链表的定义吧：将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）。

### 结构 ###

带有头结点的空表：  
![在这里插入图片描述][20210307163756731.png]  
带有头结点的非空循环链表：  
![在这里插入图片描述][20210307163816778.png]  
此时我们访问第一个结点的时间复杂度是 O( n n n)，访问最后一个结点的时间复杂度还是 O( n n n)，因为还是需要将整个链表全部遍历一遍。

我们来做下改进，将访问最后一个结点的时间复杂度改进为 O( n n n)，如何改进呢：

*  不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都很方便了。如下图：![在这里插入图片描述][20210307222922246.png]  
    终端结点用「rear」表示，则查找终端结点的时间复杂度为 O( 1 1 1)，开始结点的话，则为 `rear->next->next`，时间复杂度也为 O( 1 1 1)。

### 写在最后 ###

关联阅读：先读 [线性表][Link 2]，再读 [单链表][Link 1]（要搞清楚头结点和头指针）。

这篇博客内容比较简单，但是有个疑惑：带有头结点的循环链表的第一个结点是「头结点」还是说「第一个数据元素所在结点」，欢迎读者阅读与斧正~

[Link 1]: https://mindartisan.blog.csdn.net/article/details/113622842
[20210307154915442.png]: https://img-blog.csdnimg.cn/20210307154915442.png
[20210307163756731.png]: https://img-blog.csdnimg.cn/20210307163756731.png
[20210307163816778.png]: https://img-blog.csdnimg.cn/20210307163816778.png
[20210307222922246.png]: https://img-blog.csdnimg.cn/20210307222922246.png
[Link 2]: https://mindartisan.blog.csdn.net/article/details/113271849