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

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

hope_wisdom

632人浏览 · 2025-08-24 08:27:18

hope_wisdom · 2025-08-24 08:27:18 发布

概述

循环链表本质上也是一个单向或双向链表，但其最后一个节点的指针并不指向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;
}