实现带头双向循环链表

顺序表的实现：顺序表的实现_i跑跑的博客-CSDN博客

单链表的实现：单链表的实现_i跑跑的博客-CSDN博客

一、定义

从图示可清楚看到它有头结点，每个结点都有双指针，指向前一个结点和后一个节点，根据图示进行定义

typedef int Datatype;

typedef struct ListNode
{
    Datatype data;
    struct ListNode* next;
    struct ListNode* prev;
}ListNode;

二、创建结点

创建一个双指针的结点，带值进入，双指针置空。因为下一步初始化时要用到一个结点，因此创建结点写在前。

//创建结点
ListNode* Buynode(int x)
{
    ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
    if (tmp==NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    else
    {
        tmp->data = x;
        tmp->next = NULL;
        tmp->prev = NULL;
    }
    return tmp;
}

三、初始化和销毁

初始化

头结点的数值我们传0(一般无多大意义)。要明白什么时候双向循环链表为空，那就是他的头指向他的尾。并且我们要改变他的头指针，因此传的是头指针的地址，接收用二级指针来接收。

            ![](https://img-blog.csdnimg.cn/cc567553027c4fe5890aabb3c44a4f4b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAaei3kei3kQ==,size_20,color_FFFFFF,t_70,g_se,x_16)

//初始化
void ListInit(ListNode** phead)
{
    assert(phead);
    *phead = Buynode(0);
    (*phead)->next = *phead;
    (*phead)->prev = *phead;
}

销毁

销毁就是将每个结点释放置空，最后在释放头结点，完成链表的销毁

注：不能从头结点开始，会造成野指针，头结点要最后释放。要提前保存释放结点的下一个结点，方便更新释放结点。

//销毁
void ListDestroy(ListNode* phead)
{
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }

    free(phead);
}

四、尾部操作

尾插

此链表有很大优势，不需要遍历即可找到尾巴，即头结点的前一个结点。

创建新结点，尾结点的next指向新结点，新结点的next指向头结点，新结点的prev指向尾结点，最后头结点的prev指向新结点（这一步即更新了尾结点）。

//尾插
void ListPushBack(ListNode* phead, Datatype x)
{
    assert(phead);
    ListNode* newnode = Buynode(x);
    ListNode* tail = phead->prev;
    tail->next = newnode;
    newnode->next = phead;
    newnode->prev = tail;
    phead->prev = newnode;
    
}

尾删

尾巴删除，直接找到尾巴，将尾巴的前一个和头结点建立联系，释放尾巴结点，最后置空即可。

//尾删
void ListPopBack(ListNode* phead)
{
    assert(phead);
    if (phead->next == phead)
    {
        return NULL;
    }
    ListNode* tail = phead->prev;
    tail->prev->next = phead;
    phead->prev = tail->prev;
    free(tail);
    tail = NULL;
}

五、 在pos位置操作

固定位置插入删除，就必须先找到pos位置，我们先可以创建一个查找函数对pos进行定位。

查找函数

//查找
ListNode* ListFind(ListNode* phead, Datatype x)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

pos位置插入

这个插入是前插，在pos位置前插入，具体就是将pos的prev、要插入结点、pos，三个结点相连接。

//pos位置插入
void ListInsert(ListNode* pos, Datatype x)
{
    ListNode* newnode = Buynode(x);
    pos->prev->next = newnode;
    newnode->next = pos;
    newnode->prev = pos->prev;
    pos->prev = newnode;
}

pos位置删除

这就更简单，将pos位置前后的两结点相连接，释放掉pos即可。

//pos位置删除
void ListErase(ListNode* pos)
{
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
    pos = NULL;
}

六、头部操作

头部操作是对头结点的next进行操作，头结点不改变，务必注意这一点。

头插

在头结点和头结点的next结点中间插入一个结点，更新三个结点间的联系，与pos位置插入相同，我们可以简化代码，直接用ListInsert函数进行操作。

//头插
void ListPushFront(ListNode* phead, Datatype x)
{
    assert(phead);
    ListInsert(phead->next,x);
}

头删

与pos位置删除操作相同，直接用ListErase函数进行操作。

//头删
void ListPopFront(ListNode* phead)
{
    assert(phead);
    ListErase(phead->next);
}

附用 ListErase函数和ListInsert函数时，要清楚传的是头结点的next，头结点一定不能动。

补充说明

既然头部操作可以附用ListErase函数和ListInsert函数，那么尾部操作当然也可以对ListErase函数和ListInsert函数进行服用来简化代码。

尾插

在尾巴后面加结点，即是在头结点前面加结点，ListInsert函数是在pos前加结点，我们只需将pos换成头结点，即可附用简化代码：

//尾插
void ListPushBack(ListNode* phead, Datatype x)
{
    assert(phead);
    ListInsert(phead, x);
    
}

尾删

删除最后一个结点，和删除pos位置结点操作相同，将pos换成尾结点即可附用ListErase函数简化代码：

//尾删
void ListPopBack(ListNode* phead)
{
    assert(phead);
    ListErase(phead->prev);

}

七、打印链表

不打印头结点，打印从头结点的next开始即可：

//打印
void PrintList(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead;
    cur = cur->next;
    while (cur!=phead)
    {
        printf("%d ",cur->data);
        cur=cur->next;
    }
}

到这一个带头双向循环链表的各个功能接口就实现了，菜单和主函数各位看官可根据自己的需求来进行设计噢！感谢大家支持，欢迎评论指正！