大家好，欢迎来到IT知识分享网。

循环链表的定义

循环链表（Circular Linked List）是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。其结构如图所示：

循环链表示意图

其实，循环链表和单链表的主要差异就在于循环的判断条件上。单链表结束的判断条件是p->next是否为空，而循环链表结束的判断条件是p->next是否等于头结点。

在单链表中，通过增加头结点的方法使得访问第一个结点的时间为，但对于访问最后一个结点，却需要时间。有没有可能用的时间访问第一个结点和最后一个结点呢？对于这个问题，通常在循环链表中设立尾指针而不设头指针，则rear->next指向头结点。如图所示：

循环链表示意图

循环链表结点设计

对于循环链表的结点，可以完全参照单链表的结点设计，如图所示：

循环链表结点的数据结构

data表示数据，其可以是简单的类型（如int, double等等），也可以是复杂的结构体（struct类型）。next表示指针域，它永远指向自身的下一个结点，对于只有一个结点的存在，这个next指针则永远指向自身，对于一个链表的尾部结点，next永远指向开头。

其代码可以表示为：

typedef struct _CircleLinkedList { ElemType data; struct _CircleLinkedList* next; }CircleLinkedListNode, *CircleLinkedList;

循环链表的创建

如同单链表的创建，需要先创建一个头结点并且给其开辟内存空间；但与单链表不同的是，需要在开辟内存空间成功之后将头结点的next指向自身。当链表为空时，创建一个头结点，读取数据元素值，并将头结点的next指向自身，返回next作为尾指针。当链表不为空时，直接在尾结点后插入新结点，并且新结点作为新的尾结点。如图所示：

循环链表的创建过程

【算法代码】

CircleLinkedList CircleLinkedListCreate(CircleLinkedList slist, ElemType elem) { if (nullptr == slist) { slist = (CircleLinkedListNode*)malloc(sizeof(CircleLinkedListNode)); if (nullptr == slist) { cout << "创建链表头失败" << endl; return nullptr; } else { slist->data = elem; slist->next = slist; return slist->next; //返回尾结点 } } else { CircleLinkedListNode* rlist = (CircleLinkedListNode*)malloc(sizeof(CircleLinkedListNode)); if (nullptr == rlist) { cout << "创建结点失败" << endl; } else { rlist->data = elem; rlist->next = slist->next; slist->next = rlist; } return rlist; //返回尾结点 } }

循环链表的插入

如图，对于插入数据的操作，基本与单链表的插入操作相同，可以创建一个独立的结点，通过将需要插入的结点的上一个结点的next指针指向该结点，再由需要插入的结点的next指针指向下一个结点的方式完成插入操作。如图所示：

循环链表的插入过程

插入过程分为两种情况：

• 从头部或中间插入时，插入的结点的上一个结点的next指针指向该结点，新结点的next指针指向下一个结点，尾结点不变。
• 从尾部插入时，新结点的next指针指向头结点，同时新结点作为新的尾结点。

【算法代码】

CircleLinkedList CircleLinkedListInsert(CircleLinkedList slist, ElemType elem, int pos) { if (nullptr == slist) { cout << "输入空链表" << endl; return nullptr; } else if (pos <= 0) { cout << "输入位置错误" << endl; return slist; } else { CircleLinkedListNode* nlist = (CircleLinkedListNode*)malloc(sizeof(CircleLinkedListNode)); if (nullptr == nlist) { cout << "创建结点失败" << endl; return slist; } else { int index = 1; //头结点位置 CircleLinkedListNode* clist = slist; for (clist = slist; index < pos && clist->next != slist; clist = clist->next, ++index);//寻找当前结点 if (index == pos) //在指定位置插入 { nlist->data = elem; nlist->next = clist->next; //插入结点下一个结点指向当前位置结点 clist->next = nlist; //上一个结点的下一个结点指向新结点 } else { cout << "查找位置 " << pos << " 超出链表最大长度 " << index << "，默认插入到尾结点" << endl; nlist->data = elem; nlist->next = slist->next; //插入结点下一个结点指向尾结点的下一个结点 slist->next = nlist; //尾结点指针域指向新结点 slist = nlist; //新结点作为新的尾结点 } return slist; } } }

循环链表的删除

循环单链表的删除操作可以参考单链表的删除操作，其都是找到需要删除的结点，将其前一个结点的next指针直接指向删除结点的下一个结点即可。但需要注意的是尾节点的特判，因为删除尾节点后，尾节点前一个结点就成了新的尾节点，这个新的尾节点需要指向的是头结点而不是空，其重点可以记录为【当前的前一节点.next=自身结点.next】。如图所示：

循环链表的删除过程

【算法代码】

CircleLinkedList CircleLinkedListDelete(CircleLinkedList slist, int pos) { if (nullptr == slist) { cout << "输入空链表" << endl; return nullptr; } else if (pos <= 0) { cout << "输入位置错误" << endl; return slist; } else { CircleLinkedListNode* clist = slist; CircleLinkedListNode* rlist = slist;//存放尾指针 CircleLinkedListNode* nlist = nullptr; int index = 1; //头结点位置 for (clist = slist; index < pos && clist->next != slist; clist = clist->next, ++index);//寻找当前结点 if (index == pos) { clist->next == slist ? rlist = clist : //最后一个结点作为新的尾结点 rlist = slist; //尾结点不变 nlist = clist->next; //暂存要删除的结点结点 clist->next = clist->next->next; //指向当前结点的下一个结点 free(nlist); } else { cout << "删除位置 " << pos << " 超出链表最大长度 " << index << endl; } return rlist; } }

循环链表的获取

循环单链表的获取操作可以参考单链表的获取操作，根据给定的结点位置序号i，从链表的头结点出发，顺着链域next逐个结点向下访问。

【算法代码】

CircleLinkedList GetCircleLinkedList(CircleLinkedList slist, int pos) { if (nullptr == slist) { cout << "输入空链表" << endl; return nullptr; } else if (pos <= 0) { cout << "输入位置错误，默认输出头结点" << endl; return slist; } else { int index = 1; CircleLinkedListNode* clist = slist; for (clist = slist; index < pos && clist->next != slist; clist = clist->next, ++index);//找到尾结点 if (index < pos) { cout << "查找位置 " << pos << " 超出链表最大长度 " << index << "，默认输出尾结点" << endl; } return clist->next; } }

完整代码

GitHub: https://github.com/MrYuxiangZhu/DataStructure/tree/master/01.%20LinkedList