实现带头双向循环链表

🌈带头双向循环链表

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

🌈实现带头双向循环链表

☀️list.h

#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int DataType;
typedef struct ListNode {struct ListNode* prev;struct ListNode* next;DataType data;
}ListNode;ListNode* BuyListNode(DataType x);
ListNode* InitList();
void DestroyList(ListNode* phead);void Print(ListNode* phead);
int CountSize(ListNode* phead);void PushBack1(ListNode* phead, DataType x);
void PushBack2(ListNode* phead, DataType x);void PopBack1(ListNode* phead);
void PopBack2(ListNode* phead);void PushFront1(ListNode* phead, DataType x);
void PushFront2(ListNode* phead, DataType x);void PopFront1(ListNode* phead);
void PopFront2(ListNode* phead);void Insert(ListNode* pos, DataType x);
void Erase(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链表销毁函数（）

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

打印节点信息函数Print（）

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

统计节点个数函数CountSize（）

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

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

//在pos前插入
void Insert(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（）

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

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

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

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

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

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

void PushFront1(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;
}
void PushFront2(ListNode* phead, DataType x) {//头插就相当于在phead后一个节点的前面插入assert(phead);Insert(phead->next, x);
}

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

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

☀️测试

测试尾插：test_PushBack(（）

#define _CRT_SECURE_NO_WARNINGS
#include"list.h"
void test_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（）

void test_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（）

void test_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（）

void test_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);
}

测试结果：

测试用主函数

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