【数据结构】庖丁解牛，图文结合带你轻松上手带头循环链表

￡神魔★判官ぃ 2024-03-23 19:02 44阅读 0赞

![在这里插入图片描述][3b5ce6acb987412b9ce66515e086c46d.png_pic_center]

[君兮\_的个人主页][Link 1]

**勤时当勉励 岁月不待人**

**C/C++ 游戏开发**

> ***Hello,米娜桑们，这里是君兮\_，我们今天接着上回的单链表来讲讲带头双向循环链表，这种链表也是我们在实际应用中最常用的几种链表之一，学好这种链表是是非常重要的，我会尽量用通俗易懂的文字配合逻辑图来帮助更好的理解的  
> 好了，废话不多说，开始今天的学习吧！***—

## 带头双向循环链表 ##

*  下面的是带头双向的循环链表逻辑图  
    ![在这里插入图片描述][66bb1324a78744b78411e79ba08e3a06.png]

### 1.不同于单链表的特点 ###

*  1.双向：双向是指在带头双向循环链表的结构中，存在两个指针来链接链表，其中一个指针是指向前一个结点，另一个指针指向后一个结点。
 *  2.循环：单链表的尾部结点指向的是NULL，而双向循环链表的尾部结点指向头部的结点head，而head中指向前一个结点的指针则指向尾部结点（没理解了结合图看看哦）
 *  3.带头：带头是指在双向循环链表中存在一个哨兵位作为链表的头部（这里别急，先知道有这个东西就行，下面会重点解释的）

### 2.一个结点中存储的元素 ###

typedef int LTDataType;
    typedef struct ListNode
    {
        
    	LTDataType data;//链表中存的值
    	struct ListNode* next;//指向下一个结点的指针
    	struct ListNode* prev;//指向上一个结点的指针
    }ListNode;

--------------------

### 3.初始化链表的函数 BuyListNode ###

//初始化双链表,创建节点
    ListNode* BuyListNode(LTDataType x)
    {
        
        ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//malooc开辟一个结点的空间
        if (newnode == NULL)//判断一下是否开辟空间成功
        {
        
            perror("malloc failed\n");
            exit(-1);
        }
        //初始化时把两个指针都置空
        newnode->next = NULL;
        newnode->prev = NULL;
        newnode->data = x;
        return newnode;//返回创建好的链表节点
    }

*  这一步比较简单，看看注释相信代码非常容易理解就不过多解释了。

--------------------

### 4.创建链表的头节点 ListCreate ###

// 创建返回链表的头结点.
    ListNode* ListCreate()
    {
        
        ListNode* phead = BuyListNode(0);//开辟结点所需动态空间
        phead->next = phead;
        phead->prev = phead;
        return phead;
        
    }

*  我们刚才介绍了链表的头是有一个哨兵位的，这个哨兵位在链表没有节点时，它中的头指针和尾指针都是指向自己的，那么这个哨兵位存在的意义是什么呢？

#### 什么是哨兵位以及哨兵位存在的意义 ####

*  **哨兵位是一种在数据结构中使用的特殊值或节点，它的作用是简化算法的实现并提高效率。在查找操作中，可以将哨兵位预置在适当的位置上，以避免边界越界和找不到的情况。比如在链表中，哨兵位用来定位链表的位置，即使是空链表也会有哨兵位。在插入排序中，哨兵位用于辅助移动数据的循环处理，它可以存储需要移动的数据，并且不会受到后续操作的覆盖。通过使用哨兵位，可以简化算法的实现，减少边界判断的次数，提高程序的执行效率**
 *  在我们这个链表中具体来讲有什么意义呢？
 *  在我们使用链表时，如果没有这个哨兵位，为了防止出现越界访问和空链表的情况，我们每一次使用链表时都得进行判空操作，这样会很影响程序运行的效率。而当存在这个哨兵位，当这是个空链表时，此时的phead就是一个指向自己的结点，不会导致出错，而当链表中存在结点时，它就是一个指向头结点的结点，同时也方便了我们的循环，我们直接把尾结点的next指向这个phead就行。

--------------------

### 5.打印链表的函数 ListPrint ###

// 双向链表打印
    void ListPrint(ListNode* phead)
    {
        
        assert(phead);//断言，判断是否有结点，
        printf("Phead");//没有其他结点，打印phead
        ListNode* cur = phead->next;     
        while (cur!= phead)
        {
        
            printf(" <==> %d", cur->data);
            cur = cur->next;
    
        }
        printf("\n");
    }

*  **与之前单链表的打印基本相同，但是由于我们是循环链表，链表的尾部不再指向NULL，刚才我们说了此时链表的尾部的next指向phead，因此当我们遍历链表时，当链表再次等于phead时说明已经遍历过一次链表了，这就是我们遍历时循环停止的条件**

### 6.销毁链表的函数 ListDestory ###

// 双向链表销毁
    void ListDestory(ListNode* phead)
    {
        
        assert(phead);
    
        ListNode* cur = phead->next;
        while (cur!=phead) 
        {
        
            ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
        free(phead);
           
        
    }

*  我们遍历整个链表，把每个结点都释放掉即可，遍历链表的循环条件与上面打印链表的相同。
 *  好了，讲完上面的几个基础的接口，接下来才是重头戏，我们怎样往我们的链表中插入结点呢？

--------------------

### 7.链表的头插与头删 ###

*  其实关于插入与删除这一块，如果你能理解之前单链表的插入与删除，这一块的逻辑其实非常好理解。

#### 头插 ####

// 双向链表头插
    void ListPushFront(ListNode* phead, LTDataType x)
    {
        
        assert(phead);//断言，
        
        ListNode* frist = BuyListNode(x);//创建节点
        ListNode* cur = phead->next;
        frist->next = cur;
        frist->prev = phead;
        cur->prev = frist;
        phead->next = frist;
    
    }

*  我们先通过图来看看这里想要达到的目标  
    ![在这里插入图片描述][f319c525833c4eac929debd06f7e651d.png]
 *  **`首先，我们需要保存一下第一个位置的地址，也就是图中的cur，然后我们让first的next指向此时的cur，first的prev指向头head，这样就建立起了结点间的联系`**  
    ![在这里插入图片描述][4d7d551b39954aeca8445dae0d66101f.png]
 *  **`但是由于我们需要链表是一个双头链表，我们此时还需要让head的next指向插入的first，cur的prev也指向first这样才算真正完成我们的头插`**  
    ![在这里插入图片描述][75a253f7fa3148f38cac45c508300b7a.png]

#### 头删 ####

// 双向链表头删
    void ListPopFront(ListNode* phead)
    {
        
        assert(phead);
        ListNode* frist = phead->next;
       
        phead->next = frist->next;
        frist->next->prev = phead;
        free(frist);
    }

*  **让phead的next指向first下一个结点，让first的下一个结点的prev指向phead，释放此时的free，头删完成**
 *  与头插类似，大家把上面的逻辑图反着看即可，就不再浪费篇幅画图了。

--------------------

### 8.链表的尾插和尾删 ###

#### 尾插 ####

// 双向链表尾插
    void ListPushBack(ListNode* phead, LTDataType x)
    {
        
        assert(phead);
        assert(phead->prev);
        ListNode* newnode = BuyListNode(x);
        //ListInsert(phead, x);
        ListNode* tail = phead->prev;//起初的尾
        newnode->next = phead;//插入的结点指向头
        tail->next = newnode;//之前的尾指向现在的尾
        newnode->prev = tail;
        tail = newnode;
       
    }

*  **`不同于单链表的是，由于我们的链表是循环链表，其实尾部的结点就保存在phead的prev中，因此不再需要遍历就能轻易的找到我们的尾部`**  
    ![在这里插入图片描述][013063884516443da7e7b5ad14a839f3.png]
 *  **`此时，就比较简单啦，我们让现在的尾（d3）的next指向插入的newnode，让newnode的prev指向d3，next指向phead，再让phead的prev指向插入的newnode，即可完成尾插`**

![在这里插入图片描述][681bcff686434ac8af79a74f5e50deb4.png]

#### 尾删 ####

// 双向链表尾删
    void ListPopBack(ListNode* phead)
    {
        
        assert(phead);
        assert(phead->prev);
        ListNode* tail = phead->prev;
        ListNode* tailprev = phead->prev->prev;
        tailprev->next = phead;
        tail = tailprev;
        free(phead->prev);  
       // ListErase(phead->prev);
    
    }

*  **尾删需要我们找到现在尾的前一个结点，把它变成现在的尾，最后free掉现在的尾即可。**  
    ![在这里插入图片描述][1d0ac63403d345aab41a6ef31789954e.png]  
    ![在这里插入图片描述][7f5ac01552984ebe9b8e5059de27573f.png]

--------------------

### 9.查找某个值是否在链表中的函数 ListFind ###

// 双向链表查找
    ListNode* ListFind(ListNode* phead, LTDataType x)
    {
        
        assert(phead);
       
        ListNode* cur = phead;
        while (cur->next != phead)
        {
        
            if (cur->data == x)
            	return cur;
            
            else
             cur = cur->next;
        }
        
        return NULL;
    }

*  这个也非常简单，我们通过遍历链表的方式，通过比较结点中存储的值于我们需要查找的值来比较，找到了就返回当前结点位置的地址，没找到就返回NULL

--------------------

### 10.修改pos前一个位置的值的函数 ListInsert ###

*  在这里先简单提一嘴修改pos位置的值的函数，非常简单所以就不浪费篇幅了，我们通过上面的ListFind找到后，直接把此位置的data修改成我们需要的x即可

cur->data=x;

*  进入正题

// 双向链表在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x)
    {
        
        
        
        ListNode* newnode = BuyListNode(x);//创建结点
        ListNode* posPrev = pos->prev;
        newnode->next = posPrev->next;
        posPrev->next = newnode;
        pos->prev = newnode;
        newnode->prev = posPrev;
        
    
    }

*  这里的pos位置是通过我们上面的查找函数找到的。
 *  找到后就很简单啦,我们把pos位置之前的结点posprev的next指向newnode，让newnode的prev指向posprev，再让newnode的next指向pos，最后pos的prev指向插入的newnode即可。  
    ![在这里插入图片描述][6863fdfdd6254861830e72acbc658aa9.png]  
    ![在这里插入图片描述][255014811a0549eea973f148eef5c6c7.png]

--------------------

### 11.删除pos位置的结点 ListErase ###

// 双向链表删除pos位置的节点
    void ListErase(ListNode* pos)
    {
        
        assert(pos);
        ListNode* posPrev = pos->prev;
        ListNode* posNext = pos->next;
        posPrev->next = posNext;
        posNext->prev = posPrev;
        
        free(pos);
        //pos = NULL;
    }

*  **这个也是非常容易理解的，我们让pos位置的前一位置的结点posPrev指向pos后一位置的结点posNext即可。**  
    ![在这里插入图片描述][0af72188fe884b14b25aace6803147b5.png]  
    ![在这里插入图片描述][a68662b20db54960bd68fe7a7c7b1810.png]
 *  **最后一个小小的细节优化，当你在面试或者笔试等限定时间的时候，要求你完成一个带头双向循环链表，对于里面的头插头删，尾插尾删你也可以这样写，只需要引用上面这两个函数即可**

//头插与头删
    ListInsert(phead->next, x);
    ListErase(phead->next);
    //尾插与尾删
    ListInsert(phead, x);
    ListErase(phead->prev);

*  想想看为啥
 *  **其实我们的头插头删与尾插尾删无非是对特殊pos位置的操作嘛，因此自然可以引用上面的这两个函数啦**

--------------------

## 总结 ##

*  今天的内容到这里就结束了，带头双向循环链表可能不是那么好理解，如果你真的想要深入看懂的话一定要配合逻辑图自己尝试去敲一敲，光看不练是不可能学好的哦！！
 *  好了，如果你有任何疑问欢迎在评论区或者私信我提出，大家下次再见啦！

> ***新人博主创作不易，如果感觉文章内容对你有所帮助的话不妨三连一下这个新人博主再走呗。你们的支持就是我更新的动力！！！***

**\*\*（可莉请求你们三连支持一下博主！！！点击下方评论点赞收藏帮帮可莉吧）\*\***

![在这里插入图片描述][20fa3306e76244de9879742c165c792a.gif_pic_center]

[3b5ce6acb987412b9ce66515e086c46d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d4540f52792d4629b6afeb1deff71746.png
[Link 1]: https://blog.csdn.net/syf666250?spm=1010.2135.3001.5343
[66bb1324a78744b78411e79ba08e3a06.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/1dabb359225346509ed9c774cef5357c.png
[f319c525833c4eac929debd06f7e651d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/5aae717b3aa1479f91f9b586f761b5b3.png
[4d7d551b39954aeca8445dae0d66101f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/3333c8ac9a3244feb36d65ec1e8d31ef.png
[75a253f7fa3148f38cac45c508300b7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f50ae8ee838d430fb39e2307321b7143.png
[013063884516443da7e7b5ad14a839f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/0686c368a35e4b3087fb0573d679c7e6.png
[681bcff686434ac8af79a74f5e50deb4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/05bf5198189c41e8a96b0053a7bcc055.png
[1d0ac63403d345aab41a6ef31789954e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a2b01d9388b44e33974b082523d78145.png
[7f5ac01552984ebe9b8e5059de27573f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e3ba24285c2e414a8db7655aa150d8ea.png
[6863fdfdd6254861830e72acbc658aa9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/880ac1b008f04816a740512fa0608da6.png
[255014811a0549eea973f148eef5c6c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f8f73056309f4a45a546c47623f7a0d9.png
[0af72188fe884b14b25aace6803147b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/2f755d0f5aa04983b74ccd36e8cd5681.png
[a68662b20db54960bd68fe7a7c7b1810.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/31e1dc1d7d664a69a882ac1d875e5188.png
[20fa3306e76244de9879742c165c792a.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/822d788e08a641d7ba0ec20b2a3e1f83.png