带头双向循环链表的实现
今天我们来实现一下带头双向循环链表，顾名思义，带头就是有哨兵位，哨兵位不是链表的头，它是连接头节点的一个节点，方便操作链表而已；双向就是一个节点可以找到下一个节点，也可以找到上一个节点，所以每个节点应该有两个结构体指针；循环就是没有空指针，哨兵位的上一个节点是尾，尾的下一个节点是哨兵位；如下图为带头双向循环链表：
1. 函数的声明
以下是函数的声明部分，我们主要实现双向链表的增删查改功能；
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //类型的命名 typedef int LTDataType; //定义节点 typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDataType data; }LTNode; //初始化链表 LTNode* ListInit(); //打印链表 void ListPrint(LTNode* phead); //判断是否是空链表 bool IsEmpty(LTNode* phead); //尾插、头插、头删、尾删 void ListPushBack(LTNode* phead, LTDataType x); void ListPushFront(LTNode* phead, LTDataType x); void ListPopFront(LTNode* phead); void ListPopBack(LTNode* phead); //查找 LTNode* LTFindPos(LTNode* phead, LTDataType x); //在pos位置之前插入 void LTInsertPos(LTNode* pos, LTDataType x); //删除pos位置 void LTErasePos(LTNode* pos); //销毁 void LTDestroy(LTNode* phead);
2. 函数的实现
为了防止创建新的节点的时候重复出现，我们将创建节点写成一个函数：
LTNode* BuyListNode(int x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); assert(newnode); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
初始化节点，只需要一个哨兵位，它的next和prev都指向自己；
LTNode* ListInit() { LTNode* phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; }
打印链表的函数：
void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; printf("guard<==>"); while (cur != phead) { printf("%d<==>",cur->data); cur = cur->next; } printf("\n"); }
由于头删尾删的时候不能是空链表，带头的链表的空链表相当于只有一个哨兵位，所以头删尾删的时候链表中不能只剩下哨兵位；
bool IsEmpty(LTNode* phead) { assert(phead); return phead->next == phead; }
尾插函数：
void ListPushBack(LTNode* phead,LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; newnode->next = phead; tail->next = newnode; newnode->prev = tail; phead->prev = newnode; }
头插函数：
void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* next = phead->next; newnode->next = next; newnode->prev = phead; next->prev = newnode; phead->next = newnode; }
头删函数：
void ListPopFront(LTNode* phead) { assert(phead); assert(!IsEmpty(phead)); LTNode* del = phead->next; LTNode* next = del->next; phead->next = next; next->prev = phead; free(del); }
尾删函数：
void ListPopBack(LTNode* phead) { assert(phead); assert(!IsEmpty(phead)); LTNode* tail = phead->prev; LTNode* tailprev = tail->prev; tailprev->next = phead; phead->prev = tailprev; free(tail); }
查找某个节点的函数，返回找到的节点，否则返回空；
LTNode* LTFindPos(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
在pos位置之前插入的插入函数：
void LTInsertPos(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* ptr = pos->prev; ptr->next = newnode; newnode->next = pos; pos->prev = newnode; newnode->prev = ptr; }
删除pos位置的函数：
void LTErasePos(LTNode* pos) { assert(pos); assert(!IsEmpty(pos)); LTNode* ptr = pos->prev; LTNode* next = pos->next; ptr->next = next; next->prev = ptr; free(pos); }
销毁链表的函数：
void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
3. 主函数测试
#include "List.h" int main() { LTNode* phead = ListInit(); ListPushBack(phead, 1); ListPushBack(phead, 2); ListPushBack(phead, 3); ListPushBack(phead, 4); ListPushFront(phead, 10); ListPopBack(phead); ListPopFront(phead); LTNode* pos = LTFindPos(phead, 3); LTInsertPos(pos, 20); LTErasePos(pos); ListPrint(phead); LTDestroy(phead); return 0; }
以上就是带头双向循环链表的基本实现，感兴趣的伙伴可以自行尝试噢！！！
