在之前的文章中，我寫過一篇關(guān)于C語言實現(xiàn)雙向鏈表博文，介紹了雙向鏈表的實現(xiàn)過程以及雙向鏈表的優(yōu)勢，接下來我首先給大家介紹一下循環(huán)鏈表和雙向鏈表的區(qū)別，之后再給大家介紹雙向循環(huán)鏈表的具體實現(xiàn)。

循環(huán)鏈表和雙向鏈表的區(qū)別

1、最后一個結(jié)點指針指向不同

在建立一個循環(huán)鏈表時，必須使其最后一個結(jié)點的指針指向表頭結(jié)點，而不是像雙向鏈表那樣置為NULL。此種情況還用于在最后一個結(jié)點后插入一個新的結(jié)點。

2、判斷鏈域值不同

在判斷是否到表尾時，是判斷該結(jié)點鏈域的值是否是表頭結(jié)點，當鏈域值等于表頭指針時，說明已到表尾。而非像單鏈表那樣判斷鏈域值是否為NULL。

3、訪問方式：

循環(huán)鏈表：可以從任何一個結(jié)點開始，順序向后訪問到達任意結(jié)點

雙向鏈表：可以從任何結(jié)點開始任意向前向后雙向訪問

4、操作：

循環(huán)鏈表：只能在當前結(jié)點后插入和刪除

雙鏈表：可以在當前結(jié)點前面或者后面插入，可以刪除前趨和后繼（包括結(jié)點自己）

5、存儲：循環(huán)鏈表存儲密度大于雙鏈表

雙向循環(huán)鏈表的具體實現(xiàn)

雙向循環(huán)鏈表：最后一個節(jié)點的next指向head，而head的prior指向最后一個節(jié)點，構(gòu)成一個環(huán)。

struct doubleCircularLinkedList
{
    struct doubleCircularLinkedList* prior;//結(jié)點的前驅(qū)指針
    int data;//結(jié)點的數(shù)據(jù)項
    struct doubleCircularLinkedList* next;//結(jié)點的后繼指針
};

雙向循環(huán)鏈表的初始化

只有一個頭節(jié)點head，就讓prior和next都指向自己，形成一個環(huán)。

初始化頭結(jié)點代碼實現(xiàn)：

struct doubleCircularLinkedList* createList()
{
    //創(chuàng)建一個頭結(jié)點，數(shù)據(jù)差異化當作表頭
    struct doubleCircularLinkedList* headNode = (struct doubleCircularLinkedList*)malloc(sizeof(struct doubleCircularLinkedList));
    //循環(huán)鏈表，所以初始化頭指針，尾指針都是指向自身的，data數(shù)據(jù)域不做初始化
    headNode->prior = headNode;//頭結(jié)點指向自身
    headNode->next = headNode;//尾結(jié)點指向自身
    return headNode;
}

創(chuàng)建一個新的結(jié)點

與單向循環(huán)鏈表類似的，只是多了一個prior要考慮，為插入做準備。

struct doubleCircularLinkedList* createNode(int data)
{
    //動態(tài)申請內(nèi)存malloc+free c語言的特點
    struct doubleCircularLinkedList* newNode = (struct doubleCircularLinkedList*)malloc(sizeof(struct doubleCircularLinkedList));
    //創(chuàng)建結(jié)點過程相當于初始化過程
    newNode->data = data;//傳入data數(shù)值初始化數(shù)據(jù)域
    newNode->prior = NULL;//初始化頭結(jié)點為null
    newNode->next = NULL;//初始化尾結(jié)點為null
    return newNode;
}

插入新的元素

與單向循環(huán)鏈表類似，只是多了一個prior要考慮。這里就不需判斷插入的位置是不是在最后了，已經(jīng)構(gòu)成一個環(huán)。

表頭插入實現(xiàn)

void insertNodeByHead(struct doubleCircularLinkedList* headNode,int data)
{
    //創(chuàng)建一個新的結(jié)點，調(diào)用創(chuàng)建新結(jié)點的函數(shù)
    struct doubleCircularLinkedList* newNode = createNode(data);
    //修改四個指針變量
    newNode->prior = headNode;
    newNode->next = headNode->next;
    headNode->next->prior=newNode;
    headNode->next = newNode;
}

表尾插入實現(xiàn)

在表尾插入，比表頭插入更容易出錯，大家多加注意！首先找到尾部最后一個元素，然后再進行插入操作

void insertNodeBynext(struct doubleCircularLinkedList* headNode,int data)
{
    struct doubleCircularLinkedList* newNode = createNode(data);
    //首先找到最后一個結(jié)點的位置
    struct doubleCircularLinkedList* lastNode = headNode;
    while(lastNode->next != headNode)
    {
        lastNode = lastNode->next;
    }
    //找到之后調(diào)整四個指針
    headNode->prior = newNode;
    newNode->next = headNode;
    lastNode->next = newNode;
    newNode->prior = lastNode;
}

刪除指定元素

雙鏈表刪除結(jié)點時，只需遍歷鏈表找到要刪除的結(jié)點，然后將該節(jié)點從表中摘除即可，刪除之后不要忘了釋放空間喲！

void SpecifyLocationToDelete(struct doubleCircularLinkedList* headNode,int posData)
{
    struct doubleCircularLinkedList* posNode = headNode->next;//指定結(jié)點指針
    struct doubleCircularLinkedList* posNodeprior = headNode;//指定結(jié)點前一個結(jié)點的指針
    //找到指定位置
    while(posNode->data != posData)
    {
        posNodeprior = posNode;
        posNode = posNodeprior->next;
        //如果沒有找到特殊處理
        if(posNode->next == headNode)
        {
            printf("不存在指定位置，無法刪除！\n");
            return;
        }
    }
    posNodeprior->next = posNode->next;
    posNode->next->prior=posNodeprior;
    free(posNode);//刪除之后，釋放空間
}

查找指定元素

雙鏈表查找指定元素的實現(xiàn)同單鏈表類似，都是從表頭依次遍歷表中元素。

void searchSpecifiedElement(struct doubleCircularLinkedList* headNode,int posData)
{
    struct doubleCircularLinkedList* posNode = headNode->next;//指定結(jié)點指針
    struct doubleCircularLinkedList* posNodeprior = headNode;//指定結(jié)點前一個結(jié)點的指針
    //找到指定位置
    while(posNode->data != posData)
    {
        posNodeprior = posNode;
        posNode = posNodeprior->next;
        //如果沒有找到特殊處理
        if(posNode->next == headNode)
        {
            printf("不存在元素！\n");
            return ;
        }
    }
    printf("該元素存在！\n");
}

查找指定元素

通過遍歷找到存儲有該數(shù)據(jù)元素的結(jié)點，直接更改其數(shù)據(jù)域即可。

void modifySpecifiedElement(struct doubleCircularLinkedList* headNode,int posData,int elem)
{
    struct doubleCircularLinkedList* posNode = headNode->next;//指定結(jié)點指針
        struct doubleCircularLinkedList* posNodeprior = headNode;//指定結(jié)點前一個結(jié)點的指針
        //找到指定位置
        while(posNode->data != posData)
        {
            posNodeprior = posNode;
            posNode = posNodeprior->next;
            //如果沒有找到特殊處理
            if(posNode->next == headNode)
            {
                printf("不存在元素！\n");
            }
        }
        posNode->data = elem;
        printf("修改成功！\n");
}

打印數(shù)據(jù)

void printList(struct doubleCircularLinkedList* headNode)
{
    //從第二個結(jié)點開始打印，表頭不含數(shù)據(jù)
    //也可以通過前指針進行打印，只需將next改為prior即可
    struct doubleCircularLinkedList* pMove = headNode->next;
    while(pMove != headNode)//如果pMove->next != headNode這樣寫，最后一個結(jié)點是不會打印的
    {
        printf("%d ",pMove->data);
        pMove = pMove->next;//移動指針
    }
    printf("\n");
}

參考博文：
https://blog.csdn.net/baweiyaoji/article/details/76071053

以上就是本次給大家分享的C語言實現(xiàn)雙向循環(huán)鏈表，完整的代碼已經(jīng)push到了githubs上面（傳送門），歡迎各位clone，如果覺得還不錯的話，歡迎Star! 如果還想了解其他的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)算法，歡迎訪問我的博客，如果有哪里有問題，歡迎大家留言，我及時修改更正，堅持就是勝利！