实现带头双向循环链表

🌈带头双向循环链表

描述：一个节点内包含两个指针，一个指向上一个节点，另一个指向下一个节点。哨兵位指向的下一个节点为头节点，哨兵位的上一个指向尾节点。
结构优势：高效率找尾节点；高效率插入与删除；无需判断多种复杂情况，如尾节点、空节点等。

🌈实现带头双向循环链表

☀️list.h

#define_CRT_SECURE_NO_WARNINGS#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint DataType;typedefstructListNode{structListNode* prev;structListNode* next;
    DataType data;}ListNode;

ListNode*BuyListNode(DataType x);
ListNode*InitList();voidDestroyList(ListNode* phead);voidPrint(ListNode* phead);intCountSize(ListNode* phead);voidPushBack1(ListNode* phead, DataType x);voidPushBack2(ListNode* phead, DataType x);voidPopBack1(ListNode* phead);voidPopBack2(ListNode* phead);voidPushFront1(ListNode* phead, DataType x);voidPushFront2(ListNode* phead, DataType x);voidPopFront1(ListNode* phead);voidPopFront2(ListNode* phead);voidInsert(ListNode* pos, DataType x);voidErase(ListNode* pos);

☀️list.c

BuyListNode节点创建函数（）

ListNode*BuyListNode(DataType x){
    ListNode* node =(ListNode*)malloc(sizeof(ListNode));if(node ==NULL){perror("malloc fail");exit(-1);}
    node->data = x;
    node->prev =NULL;
    node->next =NULL;return node;}

InitList链表初始化函数（）

ListNode*InitList(){
    ListNode* phead =BuyListNode(0);
    phead->next = phead;
    phead->prev = phead;return phead;}

DestroyList链表销毁函数（）

voidDestroyList(ListNode* phead){assert(phead);
    ListNode* cur = phead->next;while(cur != phead){
        ListNode* curnext = cur->next;free(cur);
        cur = curnext;}free(phead);}

打印节点信息函数Print（）

voidPrint(ListNode* phead){assert(phead);printf("phead<=>");
    ListNode* cur = phead->next;while(cur != phead){printf("%d<=>", cur->data);
        cur = cur->next;}printf("\n");}

统计节点个数函数CountSize（）

intCountSize(ListNode* phead){assert(phead);int size =0;
    ListNode* cur = phead->next;while(cur != phead){
        size++;
        cur = cur->next;}return size;}

在pos位置节点前插入函数Insert（）

//在pos前插入voidInsert(ListNode* pos, DataType x){assert(pos);
    ListNode* posprev = pos->prev;
    ListNode* newnode =BuyListNode(x);
    posprev->next = newnode;
    newnode->prev = posprev;
    newnode->next = pos;
    pos->prev = newnode;}

删除pos位置节点函数Erase（）

voidErase(ListNode* pos){assert(pos);
    ListNode* posprev = pos->prev;
    ListNode* posnext = pos->next;free(pos);
    posprev->next = posnext;
    posnext->prev = posprev;}

尾插（两种方法）PushBack1（）&PushBack2（）

voidPushBack1(ListNode* phead, DataType x){
    ListNode* tail = phead->prev;
    ListNode* newnode =BuyListNode(x);
    newnode->next = phead;
    phead->prev = newnode;
    tail->next = newnode;
    newnode->prev = tail;}voidPushBack2(ListNode* phead, DataType x){//尾插就相当于在哨兵位head前插入Insert(phead, x);}

尾删（两种方法）PopBack1（）&PopBack2（）

voidPopBack1(ListNode* phead){assert(phead);assert(phead->next != phead);
    ListNode* tail = phead->prev;
    ListNode* tailprev = tail->prev;free(tail);
    tailprev->next = phead;
    phead->prev = tailprev;}voidPopBack2(ListNode* phead){//尾节点就是phead的prev节点Erase(phead->prev);}

头插（两种方法）PushFront1（）&PushFront2（）

voidPushFront1(ListNode* phead, DataType x){assert(phead);
    ListNode* newnode =BuyListNode(x);
    ListNode* pheadnext = phead->next;
    newnode->next = pheadnext;
    pheadnext->prev = newnode;
    phead->next = newnode;
    newnode->prev = phead;}voidPushFront2(ListNode* phead, DataType x){//头插就相当于在phead后一个节点的前面插入assert(phead);Insert(phead->next, x);}

头删（两种方法）PopFront1（）&PopFront2（）

voidPopFront1(ListNode* phead){assert(phead);assert(phead->next != phead);
    ListNode* first = phead->next;
    ListNode* second = first->next;free(first);
    phead->next = second;
    second->prev = phead;}voidPopFront2(ListNode* phead){//头节点时哨兵位phead的下一个节点Erase(phead->next);}

☀️测试

测试尾插：test_PushBack(（）

#define_CRT_SECURE_NO_WARNINGS#include"list.h"voidtest_PushBack(){
    ListNode* plist =InitList();PushBack1(plist,1);PushBack1(plist,2);PushBack1(plist,3);PushBack2(plist,1);PushBack2(plist,2);PushBack2(plist,3);Print(plist);DestroyList(plist);}

测试结果：

测试尾删：test_PopBack（）

voidtest_PopBack(){
    ListNode* plist =InitList();PushBack1(plist,1);PushBack1(plist,2);PushBack1(plist,3);PushBack2(plist,1);PushBack2(plist,2);PushBack2(plist,3);Print(plist);PopBack1(plist);Print(plist);PopBack2(plist);Print(plist);DestroyList(plist);}

测试结果：

测试头插：test_PushFront（）

voidtest_PushFront(){
    ListNode* plist =InitList();PushFront1(plist,1);PushFront1(plist,2);PushFront1(plist,3);PushFront2(plist,1);PushFront2(plist,2);PushFront2(plist,3);Print(plist);DestroyList(plist);}

测试结果：

测试头删：test_PopFront（）

voidtest_PopFront(){
    ListNode* plist =InitList();PushFront1(plist,1);PushFront1(plist,2);PushFront1(plist,3);PushFront2(plist,1);PushFront2(plist,2);PushFront2(plist,3);Print(plist);PopFront1(plist);Print(plist);PopFront2(plist);Print(plist);DestroyList(plist);}

测试结果：

测试用主函数

intmain(){//测试尾插test_PushBack();//测试尾删test_PopBack();//测试头插test_PushFront();//测试头删test_PopFront();}