概述

????????循環鏈表本質上也是一個單向或雙向鏈表，但其最后一個節點的指針并不指向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;
}

總結

????????循環鏈表是一種非常有用的數據結構，它通過改變傳統鏈表最后一個節點的指針指向，形成了一個閉環，使得數據的循環訪問變得簡單而高效。