【双向链表】

带头双向循环链表的实现

今天我们来实现一下带头双向循环链表，顾名思义，带头就是有哨兵位，哨兵位不是链表的头，它是连接头节点的一个节点，方便操作链表而已；双向就是一个节点可以找到下一个节点，也可以找到上一个节点，所以每个节点应该有两个结构体指针；循环就是没有空指针，哨兵位的上一个节点是尾，尾的下一个节点是哨兵位；如下图为带头双向循环链表：

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;}

以上就是带头双向循环链表的基本实现，感兴趣的伙伴可以自行尝试噢！！！