【概述】

循环链表分为循环单链表和循环双链表，两者分别是在单链表和双链表的基础上进行的改进，其最大的特点就是在遍历时，从一个结点出发总能到达链表的任一结点

对于循环单链表来说，其结点类型与单链表类型相同，只是表尾结点 p 的指针 next 指向头结点，此外，基本操作与单链表相似

对于循环双链表来说，其结点类型与双链表类型相同，只是表尾结点 p 的后继指针 next 指向头结点，头结点的前驱指针 prior 指向表尾结点 p，此外，基本操作与双链表相似

为便于实现，两者均采用带头结点的方式，此外，由于对链表的操作很多都在头部或尾部进行，而从头结点找到尾结点时间复杂度为 $O(n)$，为便于操作，可以令头指针 L 指向表尾元素，这样无论对头部还是尾部进行操作时，时间复杂度都为 $O(1)$

【循环单链表】

初始化表

在初始化时，令头结点 first 的后继指针 next 指向其自身

template <typename T> 
CirSingleLinkList<T>::CirSingleLinkList() {       //无参构造函数，初始化
    first = (CNode<T> *)malloc(sizeof(CNode<T>)); //分配一头结点
    first->next = first;                          //空表
}
template <typename T>
CirSingleLinkList<T>::CirSingleLinkList(T data[], int len) { //有参构造函数，链表建立
    first = (CNode<T> *)malloc(sizeof(CNode<T>)); //分配一头结点
    first->next = first;                          //空表

    this->headInsert(data, len);                  //头插法
    // this->tailInsert(data, len);               //尾插法
}

销毁表

由于循环链表的尾结点的后继结点指向头结点，在逐个销毁结点空间时，会导致指向错误

因此，对于循环单链表来说，要一开始对表进行遍历，寻找到尾结点，然后将其与头结点的连接断开

template <typename T> 
CirSingleLinkList<T>::~CirSingleLinkList() { //析构函数，链表销毁
    CNode<T> *p = first;
    while (p->next != first) { //遍历循环单链表
        p = p->next;
        if (p->next = first) { //寻找尾结点
            p->next = NULL;    //断开与头结点的链接
            break;
        }
    }

    while (first != NULL) {
        CNode<T> *p = first; //暂存要被释放的结点
        first = first->next; //头指针指向要被释放的结点的下一个结点
        free(p);             //释放空间
    }
}

基本操作

求表长

在求表长时，只要头指针 first 所指向的结点不为其自身，就继续枚举，统计表长

template <typename T> 
int CirSingleLinkList<T>::getLen() { //求表长
    int len = 0;
    CNode<T> *p = first;
    while (p->next != first) { //判断下一结点是否为头结点
        p = p->next;
        len++;
    }
    return len;
}

判空

在判空时，只需判断头指针 first 是否指向他自己

template <typename T> 
bool CirSingleLinkList<T>::empty() { //判空
    if (first->next == first)
        return true;
    return false;
}

输出

在输出时，只要头指针 first 所指向的结点不为其自身，就循环输出

template <typename T> 
void CirSingleLinkList<T>::print() { //输出
    CNode<T> *p = first->next;      //指向第1个结点
    while (p != first) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

查找

按值查找

在按值查找时，只要工作指针 p 不为头结点，就循环查找

template <typename T>
CNode<T> *CirSingleLinkList<T>::getNodeByValue(T elem) { //按值查找
    CNode<T> *p = first->next; //从头结点开始
    while (p != first && p->data != elem)
        p = p->next;
    return p;
}

按位查找

在按位查找时，从头结点指向的结点开始计数，同时，只要工作指针 p 不为头结点，就循环查找

template <typename T>
CNode<T> *CirSingleLinkList<T>::getNodeByLocate(int pos) { //按位查找
    if (pos < 0)     //越界判断
        return NULL;
    if (pos == 0)    //返回头结点
        return first;

    CNode<T> *p;     //扫描器，当前扫描到的工作结点
    p = first->next; //扫描器从头结点指向的结点开始
    int now_pos = 1; //累加器，记录p指向的第几个结点

    while (p != first && now_pos < pos) { //查找第pos个结点
        p = p->next;
        now_pos++;
    }
    return p;
}

删除

与单链表不同，循环单链表在任意一个位置上的删除是等价的，无须判断是否为表尾元素

template <typename T>
bool CirSingleLinkList<T>::deleteNodeByLocate(CNode<T> *p, T &elem) { //删除指定结点p
    if (p == NULL)
        return false;
    
    CNode<T> *s = p->next; //指向结点p的下一结点s
    elem = p->data;        //记录数据域
    p->data = s->data;     //将结点p的下一结点s中的数据存到结点p中
    p->next = s->next;     //断开结点p与其下一结点s的链接关系
    free(s);               //释放p的下一结点的空间
    return true;
}

【循环双链表】