双向带头循环链表（详解）

双向链表的定义

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
下图为双向链表的带头结构图。

下图为双向链表不带头结构图

这里我们在定义双向链表的时候，一个结点里面的next存储的下一个结点的地址，prev存储的是上一个结点的地址，这里我们就会将其链接起来。

头文件

#pragma once  #include<stdio.h> #include<string.h> #include<assert.h> #include<stdlib.h>   typedef int  LTDateType;  typedef struct ListNode { 	LTDateType data; 	struct ListNode* next; 	struct ListNode* prev; }LTNode;   //初始化 LTNode* ListInit(); //申请新的结点 LTNode* BuyListNode(LTDateType x); //尾插 void ListPushBack(LTNode* phead, LTDateType x); //尾删 void ListPopBack(LTNode* phead); //头插 void ListPushFront(LTNode* phead, LTDateType x); //头删 void ListPopFront(LTNode* phead); //打印 void ListPrint(LTNode* phead); //查找 LTNode* ListFind(LTNode* phead, LTDateType x); //在pos位置之前进行插入 void ListInsert(LTNode* pos, LTDateType x); //删除pos位置的结点 void ListErase(LTNode* pos); 

接口的实现

1、新节点的申请以及初始化链表

//申请新的结点 LTNode* BuyListNode(LTDateType x) { 	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); 	newnode->data = x; 	newnode->next = NULL; 	newnode->prev = NULL; 	return newnode; } //初始化 LTNode* ListInit() { 	//哨兵位的头节点 	LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); 	phead->next = phead; 	phead->prev = phead; 	return phead; } 

2、链表的头插尾插

//头插 void ListPushFront(LTNode* phead, LTDateType x) { 	assert(phead); 	LTNode* newnode = BuyListNode(x); 	LTNode* next = phead->next; 	phead->next = newnode; 	newnode->prev = phead; 	newnode->next = next; 	next->prev = newnode;  	//调用ListInsert也可以实现头插 	//ListInsert(phead->next, x);  } //尾插 void ListPushBack(LTNode* phead, LTDateType x) { 	assert(phead);  	LTNode* tail = phead->prev; 	LTNode* newnode = BuyListNode(x); 	tail->next = newnode; 	newnode->prev = tail; 	newnode->next = phead; 	phead->prev = newnode;  	//调用ListInsert也可以实现尾插 	//ListInsert(phead, x); } 

3、链表的头删尾删

//头删 void ListPopFront(LTNode* phead) { 	assert(phead); 	assert(phead->next != NULL); 	LTNode* next = phead->next; 	LTNode* next2 = next->next; 	phead->next = next2; 	next2->prev = phead; 	free(next); }  //尾删 void ListPopBack(LTNode* phead) { 	assert(phead); 	assert(phead->next != phead); 	//找到尾 	LTNode* tail = phead->prev; 	phead->prev = tail->prev; 	tail->prev->next = phead;  	free(tail);  } 

3、链表的查找

//查找 LTNode* ListFind(LTNode* phead, LTDateType x) { 	assert(phead);  	LTNode* cur = phead->next; 	while (cur != phead) 	{ 		if (cur->data == x) 		{ 			return cur; 		} 		cur = cur->next; 	} 	return NULL; } 

4、在pos位置之前进行插入以及删除pos位置的结点

//在pos位置之前进行插入 void ListInsert(LTNode* pos, LTDateType x) { 	assert(pos); 	LTNode* newnode = BuyListNode(x); 	LTNode* posprev = pos->prev; 	posprev->next = newnode; 	newnode->prev = posprev; 	newnode->next = pos; 	pos->prev = newnode;  } //删除pos位置的结点 void ListErase(LTNode* pos) { 	assert(pos); 	LTNode* posnext = pos->next; 	LTNode* posprev = pos->prev; 	posnext->prev = posprev; 	posprev->next = posnext; } 

5、链表的打印

//打印 void ListPrint(LTNode* phead) { 	assert(phead);  	LTNode* cur = phead->next; 	while (cur != phead) 	{ 		printf("%d ", cur->data); 		cur = cur->next; 	} 	printf("\n"); } 

但是相对于双向带头链表来说，有下面的优缺点：
优点
1、在任意位置插入删除效率高。O(1)
2、按需申请空间
缺点
1、不支持随机访问。(下标访问)意味着一些快排，二分查找在这种结构上不适用