2.5　循环单链表

2.5.1　循环链表的链式存储

循环单链表（circular linked list）是首尾相连的一种单链表。将单链表的最后一个结点的指针域由空指针改为指向头结点或第一个结点，整个链表就形成一个环，这样的单链表称为循环单链表。从表中任何一个结点出发均可找到表中其他结点。

与单链表类似，循环单链表也可分为带头结点结构和不带头结点结构两种。对于不带头结点的循环单链表，当表不为空时，最后一个结点的指针域指向头结点，如图2-20所示。对于带头结点的循环单链表，当表为空时，头结点的指针域指向头结点本身，如图2-21所示。

图2-20　循环单链表

图2-21　结点为空的循环单链表

循环单链表与单链表在结构、类型定义及实现方法上都是一样的，唯一的区别仅在于判断链表是否为空的条件上。判断单链表为空的条件是head->next==NULL，判断循环单链表为空的条件是head->next==head。

在单链表中，访问第一个结点的时间复杂度为O（1），而访问最后一个结点则需要将整个单链表扫描一遍，故时间复杂度为O（n）。对于循环单链表，只需设置一个尾指针（利用rear指向循环单链表的最后一个结点）而不设置头指针，就可以直接访问最后一个结点，时间复杂度为O（1）。访问第一个结点即rear->next->next，时间复杂度也为O（1），如图2-22所示。

图2-22　仅设置尾指针的循环单链表