当前位置：首页 > ds >正文

C/C++数据结构之循环链表

ds 2025/8/25 7:43:51

概述

循环链表本质上也是一个单向或双向链表，但其最后一个节点的指针并不指向NULL，而是指向链表的第一个节点，从而形成一个闭合的环。这种结构使得在遍历链表时，可以从任意一个节点开始，并最终回到起始点。

音乐播放软件一般都提供了重复播放的功能，这意味着：当播放列表中的最后一首歌曲播放完毕后，自动跳转至第一首歌曲继续播放。这种功能可以通过循环链表来轻松实现，其中每首歌曲代表链表中的一个节点。可以看到，循环链表非常适合需要重复访问元素的场景，比如：循环队列、时间轮等。

基本操作

与单向链表类似，单向循环链表的每个节点包含两部分：一部分是存储数据的数据域，另一部分是指向下一个节点的指针。只不过最后一个节点的pNext指针不为NULL，而是指向头节点。

对单向循环链表进行插入操作时，如果插入位置在中间，则与单向链表的插入逻辑基本相同。如果在头部插入新节点，则新节点的pNext指向当前头节点，尾部节点的pNext指向新节点，然后更新头指针指向新节点。如果链表为空，则新节点的pNext也指向自己。如果在尾部插入新节点，则首先找到链表的尾节点，即pNext指针指向头节点的那个节点；然后，让它的pNext指向新节点，新节点的pNext指向头节点。

对单向循环链表进行删除操作时，根据要删除的节点位置，调整前一个节点的pNext指针指向被删节点的下一个节点。如果是删除头节点，则需要更新头指针。

对单向循环链表进行遍历操作时，可以从任意节点开始，沿着pNext指针移动，直到再次到达起始节点为止。

具体的实现，可参考下面的示例代码。双向循环链表与双向链表的区别，与上面基本类似，这里就不再赘述了。

#include <iostream>
using namespace std;struct Node
{int nData;Node* pNext;
};// 创建新节点
Node* CreateNode(int nData)
{Node* pNode = new Node();pNode->nData = nData;pNode->pNext = NULL;return pNode;
}// 查找前一个节点
Node* FindPrevious(Node* pHead, Node* pTarget)
{if (pHead == NULL || pTarget == NULL){return NULL;}Node* pCurrent = pHead;while (pCurrent->pNext != pTarget){pCurrent = pCurrent->pNext;if (pCurrent == pHead){// 循环了一圈没找到return NULL;}}return pCurrent;
}// 头部插入
void InsertAtHead(Node*& pHead, int nData)
{Node* pNode = CreateNode(nData);if (pHead == NULL){pHead = pNode;// 循环指向自己pNode->pNext = pHead;}else{// 新节点的pNext指向当前头节点pNode->pNext = pHead;// 尾部节点的pNext指向新节点Node *pPre = FindPrevious(pHead, pHead);if (pPre != NULL){pPre->pNext = pNode;}pHead = pNode;}
}// 尾部插入
void InsertAtTail(Node*& pTail, int nData)
{Node* pNode = CreateNode(nData);if (pTail == NULL){pTail = pNode;pNode->pNext = pTail;}else{pNode->pNext = pTail->pNext;pTail->pNext = pNode;// 更新尾节点为新节点pTail = pNode;}
}// 指定位置后插入
bool InsertAfter(Node* pNode, int nData)
{if (pNode == NULL){return false;}Node* pNewNode = CreateNode(nData);pNewNode->pNext = pNode->pNext;pNode->pNext = pNewNode;return true;
}// 删除操作
bool DeleteNode(Node*& pHead, Node* pDelNode)
{if (pHead == NULL || pDelNode == NULL){return false;}// 只有一个节点的情况if (pDelNode->pNext == pDelNode){delete pDelNode;pHead = NULL;return true;}// 找到前一个节点Node* pPrev = FindPrevious(pHead, pDelNode);if (pPrev == NULL){return false;}// 更新指针pPrev->pNext = pDelNode->pNext;// 如果删除的是头节点，更新head指针if (pDelNode == pHead){pHead = pDelNode->pNext;}delete pDelNode;return true;
}// 遍历操作
void TraverseList(Node* pNode)
{if (pNode == NULL){cout << "List is empty" << endl;return;}Node* pCurrent = pNode;do{cout << pCurrent->nData << " -> ";pCurrent = pCurrent->pNext;} while (pCurrent != pNode);cout << "(back to head)" << endl;
}int main()
{Node* pHead = NULL;Node* pTail = NULL;InsertAtTail(pTail, 77);pHead = pTail;InsertAtTail(pTail, 88);InsertAtHead(pHead, 66);InsertAfter(pTail, 99);// 输出：66 -> 77 -> 88 -> 99 -> (back to head)TraverseList(pHead);return 0;
}