三分钟带你手撕带头双向循环链表

数据结构——带头双向循环链表

🏖️专题：数据结构
🙈作者：暴躁小程序猿
⛺简介：双非大二小菜鸟一枚，欢迎各位大佬指点~

文章目录

前言

  我们从进入数据结构模块开始，首先学习了顺序表，顺序表其实就是数组，它需要一组连续的物理空间来存储数据，所以它的缺点很明确，但是优点就是查找起来很方便，可以根据下标直接访问，然后我们学习了单链表，单链表就弥补了顺序表必须是连续物理空间的缺点，它的特点是不需要连续的空间，每个结点通过指针来连接，但是它的缺点也很明显就是查找起来很麻烦，如果想要在指定位置插入数据，或者头插等功能不容易找到对应的位置，往往需要设置一个或多个指针来达到目的，所以我们今天来讲一下双向链表。

一、什么是双向链表？

  双向链表，顾名思义就是有两个方向，说具体就是有两个指针域，一个可以指向该结点的前驱，一个可以指向该结点的后继，next指针指向后继，prev指向前驱。这样可以找到每个结点的前一个结点和后一个结点，大大方便了我们的操作，但是我们很多时候是使用的带头的双向循环链表。
  带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了

二、带头双向循环链表图示

  我们头结点里面放的是0，不需要做其他的考虑，从phead后面的那个结点开始存储数据。需要注意的是phead->prev指向最后一个结点，最后一个结点的next指针指向phead，所以就形成了上图的循环，这样会大大方便我们后续的操作，虽然结构复杂了，但是代码实现却简单了。

三、带头双向循环链表代码实现

1.头文件

代码如下（示例）：

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<assert.h>#include<stdlib.h>typedefint LTDataType;typedefstructListNode{structListNode* prev;structListNode* next;
    LTDataType data;}LTNode;//结点初始化
LTNode*ListInit();//申请新结点
LTNode*BuyLTNode(LTDataType x);//打印链表voidListPrint(LTNode* phead);//尾插法voidListPushBack(LTNode* phead, LTDataType x);//尾删法voidListPopBack(LTNode* phead);//头删法voidListPopFront(LTNode* phead);//头插法voidListPushFront(LTNode* phead, LTDataType x);//查找结点
LTNode*ListFind(LTNode* phead, LTDataType x);//指定位置插入voidListInsert(LTNode* pos, LTDataType x);

  我们在头文件中可以看出我们的带头双向循环列表的基本功能，增删改查指定位置插入等，大家也可以根据自己的需要添加新的功能。头文件种放的是结点结构体的定义以及函数的声明，具体的函数功能实现在下面展示。

2.功能实现文件

代码如下（示例）：

#define_CRT_SECURE_NO_WARNINGS#include"List.h"
LTNode*BuyLTNode(LTDataType x){
    LTNode* newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){perror("malloc fail");exit(-1);}
    newnode->data = x;
    newnode->next =NULL;
    newnode->prev =NULL;return newnode;}
LTNode*ListInit(){
    LTNode* phead=BuyLTNode(0);
    phead->next = phead;
    phead->prev = phead;return phead;}voidListPrint(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur!=phead){printf("%d ", cur->data);
        cur = cur->next;}printf("\n");}//void ListInit(LTNode** pphead)//{//    assert(pphead);//    *pphead = BuyLTNode(0);//    (*pphead)->next = *pphead;//    (*pphead)->prev = *pphead;//}voidListPushBack(LTNode* phead, LTDataType x){assert(phead);
    LTNode* newnode =BuyLTNode(x);
    LTNode* tail = phead->prev;
    newnode->prev = tail;
    newnode->next = tail->next;
    tail->next = newnode;
    phead->prev = newnode;}voidListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);
    LTNode* tail = phead->prev;
    LTNode* prev = tail->prev;
    prev->next = phead;
    phead->prev = prev;free(tail);
    tail =NULL;}voidListPopFront(LTNode* phead){assert(phead);
    LTNode* first = phead->next;
    LTNode* second = first->next;
    second->prev = phead;
    phead->next = second;free(first);
    first =NULL;}voidListPushFront(LTNode* phead, LTDataType x){assert(phead);
    LTNode* newnode =BuyLTNode(x);
    LTNode* first = phead->next;
    newnode->prev = phead;
    newnode->next=first;
    first->prev = newnode;
    phead->next = newnode;}//void ListFind(LTNode** phead, LTDataType x)//{//    assert(phead);//    LTNode* cur = (*phead)->next;//    while (cur != *phead)//    {//        if (cur->data == x)//        {//            printf("找到了\n");//            return;//        }//        cur = cur->next;//    }//    printf("没有找到\n");//}
LTNode*ListFind(LTNode* phead, LTDataType x){assert(phead);

    LTNode* cur = phead->next;while(cur != phead){if(cur->data == x){return cur;}

        cur = cur->next;}returnNULL;}voidListInsert(LTNode* pos, LTDataType x){
    LTNode* newnode =BuyLTNode(x);
    LTNode* posprev = pos->prev;
    posprev->next = newnode;
    newnode->prev = posprev;
    newnode->next = pos;
    pos->prev = newnode;}

  上述代码就一起实现了我们带头双向循环链表的具体功能，接下来我们来详细的看一些比较难实现的功能。

2.1创建新的结点

LTNode*BuyLTNode(LTDataType x){
    LTNode* newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){perror("malloc fail");exit(-1);}
    newnode->data = x;
    newnode->next =NULL;
    newnode->prev =NULL;return newnode;}

  我们链表和顺序表不一样，不需要连续的物理存储空间，所以我们就不用提前开辟大的空间来准备，这样不会造成空间资源的浪费，我们每次要插入新结点的时候再申请一个结点的空间，我们这里定义函数的返回值类型是LTNode*，直接返回一个结构体指针，我们先为新结点malloc动态内存分配一个空间，然后判断一下malloc的返回值是否为NULL，如果为NULL则表示我们malloc申请内存失败，就直接使用perror函数返回代码的错误，然后用exit(-1)中断程序，如果不为NULL，我们将要插入的数据内容放到新结点的data域内，然后将新结点的前驱指针域prev和后继指针域next全部置为NULL，返回一个结构体指针来方便我们之后的操作，到此我们创建新结点的功能就实现了。

2.2 初始化链表

LTNode*ListInit(){
    LTNode* phead=BuyLTNode(0);
    phead->next = phead;
    phead->prev = phead;return phead;}

  既然我们说的是带头的双向循环链表，所以在初始化的时候就该把链表的头创建好，我们说了头的data域存储的是0，然后是循环的，所以我们让phead的prev和next都指向它自己，这样我们链表的头就处理好了。

2.3 尾插

voidListPushBack(LTNode* phead, LTDataType x){assert(phead);
    LTNode* newnode =BuyLTNode(x);
    LTNode* tail = phead->prev;
    newnode->prev = tail;
    newnode->next = tail->next;
    tail->next = newnode;
    phead->prev = newnode;}

  我们首先判断一下phead是否为NULL，如果phead为NULL那就是空表，如果不为空表我们就申请一个新的结点然后将数据放进去，同时找到最后一个结点的位置，我们之前在单链表的时候是用了两个指针，end指针为NULL了说明end的前一个指针prev指向的是最后的结点，而我们带头双向循环链表的优势就在这里显示出来了，我们直接找到phead->prev，这个就是最后一个结点的位置，我们将新结点的的前驱设成tail，然后将新结点的next设成tail的next，然后将新结点给tail->next，最后将新结点给phead->prev，我们就完成了尾插。

2.4 头插法

voidListPushFront(LTNode* phead, LTDataType x){assert(phead);
    LTNode* newnode =BuyLTNode(x);
    LTNode* first = phead->next;
    newnode->prev = phead;
    newnode->next=first;
    first->prev = newnode;
    phead->next = newnode;}

  这里要注意的是我们要找到phead后面的第一个首元结点，因为头插不是在phead之前插入，而是要在phead后面，首元结点的前面插入，操作步骤同上，同时我们将首元结点保存在first这个结构体指针内保存起来，就可以随意改变插入数据指针的改变顺序了。
其余功能的代码实现思想都很容易，这里也就不在多说。

总结

  本篇博客讲了什么是带头双向循环链表，带头有什么好处，循环又有什么好处，以及带头双向循环链表的优势和功能的实现，单链表一般不单独存储数据，查找起来非常的麻烦，效率很低，而带头双向循环链表就是单链表的一次升级，它可以单独的存储数据，但是说到存储数据我们一般也不用这个，因为后面有更好的结构，比如哈希表，红黑树，跳表等等，我们后面也会依次向大家分享自己的心得，欢迎大家私信，我们明天见~