前言：

链表有很多种，上一章结，我复盘了单链表，这一章节，主要针对双链表的知识点进行，整理复盘，如果将链表分类的话，有很多种，我就学习的方向考察的重点，主要针对这两种链表进行整理。

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。带头双向循环链表如下图所示。 

目录

1. 带头双向链表的实现

 1.1封装链表节点结构体

1.2建立新的节点 

 1.3初始化链表

1.4尾插函数 

 1.5尾删

 1.6头插

1.7头删

1.8显示

1.9销毁

1.10查找

1.11插入

1.12擦除

1.13判空

1. 带头双向链表的实现

 1.1封装链表节点结构体

typedef int LDataType;

typedef struct ListNode
{
	LDataType data;//自身数据
	struct ListNode* prev;指向前一个节点指针
	struct ListNode* next;指向后一个节点指针

}LTNode;

1.2建立新的节点 

 链表的增删查改都会有新的节点，所以我们可以封装一个建立节点的函数，具体代码如下:

LTNode* BuyNode(LDataType x)
{
	LTNode* temp = (LTNode*)malloc(sizeof(LTNode));
	if (temp == NULL)
	{
		perror("malloc:fail");
		exit(-1);
	}
	temp->data = x;
	temp->next = NULL;
	temp->prev = NULL;


	return temp;
}

 1.3初始化链表

 因为是带头节点，初始化会改变节点指向，如果按照单链表的操作习惯，我们可能穿指针变量的地址，用二级指针接收，但是也没必要，我们可以让函数返回的类型，为指针，具体代码如下：

LTNode* ListInit()
{
	LTNode* phead = BuyNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

1.4尾插函数 

 因为头结点的prev指向tail，tail的next节点指向head所以我们只要改变节点指向就可以完成尾插，如图所示：

具体代码如下： 

void PushBack(LTNode* pa, LDataType x)
{
	assert(pa);
	LTNode* newnode = BuyNode(x);
	LTNode* tail = pa->prev;
	tail->next = newnode;
	newnode->prev = tail;
	pa->prev = newnode;
	newnode->next = pa;
	
}

 1.5尾删

 删掉最后一个节点，并改变节点指向

具体代码如下：

void PopBack(LTNode* pa)
{
	assert(pa);
	LTNode* tail = pa->prev;
	LTNode* middle = tail->prev;
	middle->next = pa;
	pa->prev = middle;
	free(tail);
    tail = NULL;

}

 1.6头插

代码如下：

void PushFront(LTNode* pa, LDataType x)
{
	assert(pa);
	LTNode* newnode = BuyNode(x);
	LTNode* middle = pa->next;
	newnode->next = middle;
	middle->prev = newnode;
	pa->next = newnode;
	newnode->prev = pa;
}

1.7头删

 代码如下

void PopFront(LTNode* pa)
{
	assert(pa);
	LTNode* middle = pa->next;
	LTNode* cur = middle->next;
	pa->next = cur;
	cur->prev = pa;
	free(middle);
  middle = NULL;
}

1.8显示

 增删查改之后，需要显示在终端，所以要有打印显示函数

void ListPrint(LTNode* pa)
{
	LTNode* cur = pa->next;
	while (cur != pa) 
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("NULL
");
}

1.9销毁

 在堆上创建的空间，使用完成后，要返还给操作系统。

void ListDestroy(LTNode* pa)
{
	LTNode* cur = pa->next;
	LTNode* prev = NULL;
	while (cur != pa)
	{
		LTNode* prev = cur;
		cur = cur->next;
		free(prev);
	}
	free(pa);
	pa->next = pa->prev = NULL;
}

1.10查找

 查找指定数值得节点，当查找到的时候返回该数值得地址，如果没有查找到则返回空指针。

LTNode* ListFind(LTNode* pa, LDataType x)
{
	assert(pa);
	LTNode* cur = pa->next;
	while (cur != pa)
	{
		if (cur->data != x)
		{
			cur = cur->next;
		}
		else
		{
          return cur;
		}
		
	}
	return NULL;

}

1.11插入

 在当前节点的前一个位置插入节点

void ListInsert(LTNode* pa, LTNode* pos, LDataType x)
{
	assert(pa);
	assert(pos);
	LTNode* newnode = BuyNode(x);
	LTNode* prev = pos->prev;

	newnode->next = pos;
	pos->prev = newnode;

	prev->next = newnode;
	newnode->prev = prev;

}

1.12擦除

 将当前节点去除掉。

void ListErase(LTNode* pa, LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;

}

1.13判空

如果头节点的下个指向为自己这个表达式为真的话，则返回true 否则返回false。 

bool LTEmpty(LTNode* pa)
{
	return pa->next == pa;
}