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

双向链表的定义

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

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

这里我们在定义双向链表的时候，一个结点里面的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、不支持随机访问。(下标访问)意味着一些快排，二分查找在这种结构上不适用