数据结构之双向带头循环链表函数功能实现与详细解析

个人主页：点我进入主页

专栏分类：C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶

C语言刷题 数据结构初阶

欢迎大家点赞，评论，收藏。

一起努力，一起奔赴大厂。

1.前言

    在前面我们写过单链表，循环链表的博客，今天我主要给大家来带关于双向带头循环链表函数的功能与实现，双向带头循环链表相对于单链表，循环链表非常的容易实现，他的函数的功能和 单链表，循环链表一样，如果你想要快速实现一个链表的所有功能，带头双向循环链表非常的容易，接下来让我们看看带头双向链表的奥妙把，看完你绝对会佩服写出这种结构的人。

2.带头双向循环链表函数实现

#include<stdio.h>
#include<stdlib.h>
#include <assert.h>
typedef struct ListNode {
    int data;
    struct ListNode* prev, * next;
}ListNode;
ListNode* ListCreate(int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        perror("malloc");
        return NULL;
    }
    newnode->next = NULL;
    newnode->prev = NULL;
    newnode->data = x;
    return newnode;
}
ListNode* LInit()
{
    ListNode* head = ListCreate(-1);
    head->next = head;
    head->prev = head;
    return head;
}
void ListDestory(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next, * prev = phead;
    while (prev != phead)
    {
        free(prev);
        prev = cur;
        cur = cur->next;
    }
}
void ListPrint(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    printf("哨兵位<=>");
    while (cur != phead)
    {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
void ListPushBack(ListNode* phead, int x)
 {
    assert(phead);
    ListNode* newnode = ListCreate(x);
    ListNode* tail = phead->prev;
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
}
void ListPushFrount(ListNode* phead, int x)
{
    assert(phead);
    ListNode* newnode = ListCreate(x);
    ListNode* cur = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = cur;
    cur->prev = newnode;
}
void ListPopBack(ListNode* phead)
{
    assert(phead && phead->next != phead);
    ListNode* cur = phead->prev;
    cur->prev->next = phead;
    phead->prev = cur->prev;
    free(cur);
}
void ListPopFrount(ListNode* phead)
{
    assert(phead && phead->next != phead);
    ListNode* cur = phead->next;
    phead->next = cur->next;
    cur->next->prev = phead;
    free(cur);
}
ListNode* ListFind(ListNode* phead, int x)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur->data != x)
    {
        cur = cur->next;
    }
    return cur;
}
void ListInsert(ListNode* pos, int x)
{
    assert(pos);
    ListNode* newnode = ListCreate(x);
    ListNode* cur = pos->prev;
    cur->next = newnode;
    newnode->prev = cur;
    newnode->next = pos;
    pos->prev = newnode;
}
void ListErase(ListNode* pos)
{
    assert(pos);
    ListNode* cur = pos->next;
    ListNode* prev = pos->prev;
    free(pos);
    cur->prev = prev;
    prev->next = cur;
}
void text1()
{
    ListNode* head = LInit();
    ListPushBack(head, 1);
    ListPushBack(head, 2);
    ListPushBack(head, 3);
    ListPushBack(head, 4);
    ListPushBack(head, 5);
    ListPushFrount(head, 0);
    ListPrint(head);
    ListPopBack(head);
    ListPrint(head);
    ListPopBack(head);
    ListPrint(head);
    ListPopFrount(head);
    ListPrint(head);
    ListPopFrount(head);
    ListPrint(head);
    ListPushBack(head, 4);
    ListPushBack(head, 5);
    ListNode* cur = ListFind(head,3);
    ListPushFrount(head, 1);
    ListPushFrount(head, 0);    
    printf("%d\n", cur->data);
    ListPrint(head);
    ListInsert(head, 10);
    ListPrint(head);
}

3.总结

    带头双向循环的链表非常的好，接下俩我们对顺序表和链表的存储空间，随机访问，任意位置插入或删除元素，插入，缓存利用率，应用场景进行分析

不同点顺序表链表存储空间上物理上一定连续逻辑上连续，但物理上不一定连
续随机访问支持O(1)不支持：O(N)任意位置插入或者删除元
素可能需要搬移元素，效率低O(N)只需修改指针指向插入动态顺序表，空间不够时需要扩
容没有容量的概念应用场景元素高效存储+频繁访问任意位置插入和删除频繁缓存利用率高低