DS：带头双向循环链表的实现

创作不易，友友们给个三连吧！！！

      博主的上篇文章介绍了链表，以及单链表的实现。

单链表的实现（超详细！！）
    其实单链表的全称叫做不带头单向不循环链表，本文会重点介绍链表的分类以及双链表的实现！

一、链表的分类

   链表的结构⾮常多样，组合起来就有8种（2 x 2 x 2）链表结构：

1.1 单向或者双向

    双向链表，即上一个结点保存着下一个结点的地址，且下一个结点保存着上一个结点的地址，即我们可以从头结点开始遍历，也可以从尾结点开始遍历

1.2 带头或者不带头 

     单链表中我们提到的“头结点”的“头”和“带头”链表的头是两个概念！单链表中提到的“头结点”指的是第一个有效的结点，“带头”链表里的“头”指的是无效的结点（即不保存任何有效的数据！）

    

1.3 循环或者不循环

     不循环的链表最后一个结点的next指针指向NULL，而循环的链表，最后一个结点的next指针指向第一个结点！！

      虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构： 单链表（不带头单向不循环链表）和 双向链表（带头双向循环链表）

1. 无头单向非循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结 构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。

2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带 来很多优势，实现反⽽简单了，后⾯我们代码实现了就知道了。

二、带头双向循环链表的结构

      带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的”

“哨兵位”存在的意义：遍历循环链表避免死循环。

三、双向链表结点结构体的创建

     与单链表结点结构体不同的是，双向链表的结点结构体多了一个前驱结点！！

typedef int LTDataType;//对类型进行重命名，后面可以通过修改存储其他数据类型
typedef struct ListNode
{
	LTDataType data;//保存的数据
	struct ListNode* prev;//指针保存前一个结点的地址
	struct ListNode* next;//指针保存后一个结点的地址
}LTNode;

四、带头双向循环链表的实现

4.1 新结点的申请

      涉及到需要插入数据，都需要申请新节点，所以优先封装一个申请新结点的函数！利用返回值返回该结点

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);//申请失败需要强制退出程序
	}
	//申请成功，则新节点的前驱结点和后驱结点都指向自己
	newnode->data = x;
	newnode->prev = newnode->next = newnode;
    return newnode;
}

4.2 初始化（哨兵位结点）

       对于双向链表来说，需要优先创建一个哨兵结点，和其他结点不同的是，该哨兵结点可以不存储数据，这里我们默认给他一个-1。并利用返回值返回该结点。

LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);//哨兵结点可以不存储数据，我们默认给个-1
	return phead;//返回哨兵结点
}

4.3 尾插 

       如图，因为这个一个循环链表，相当于我们要把新节点插在最后一个结点和哨兵结点之间，并且最后一一个结点可以用哨兵结点的前驱结点（phead->prev）就可以找到，然后建立phead phead->prev newnode的联系！

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);//申请新节点
	//建立phead phead->prev newnode的联系
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;//尾结点的后继指针指向新节点
	phead->prev = newnode;//哨兵结点的前驱指针指向新结点
}

 单链表中我们的参数选择二级指针，为什么这里选择一级指针？？？

      对于单链表来收，单链表的头节点是会改变的，所以我们需要用二级指针，但是双链表的头节点相当于哨兵位，哨兵位是不需要被改变的，他是固定死的，所以我们选择了一级指针。（单链表改了完全头节点，但是双链表只会改变头结点的成员——prev和next）

注：phead->prev->next = newnode和phead->prev = newnode不能替换顺序，因为尾结点是通过头节点找到的，所以要优先让他与newnode建立联系，双链表虽然不需要像单链表一样找最后一个结点需要遍历链表，但是要十分注意修改指针指向的先后顺序！！

4.4 头插

       如图可知，相当于将新节点插入在头节点和头节点下一个结点之间，头节点下一个结点可以通过phead->next找到，然后建立phead、phead->next、newnode的联系！！

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);//申请新节点
	//建立phead phead->next newnode的联系
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->next->prev = newnode;//头节点的下一个结点的前驱指针指向新结点
	phead->next = newnode;//头节点的后继指针指向新节点
}

4.5 打印

      因为是循环链表，所以为了避免死循环打印，我们要设置一个指针接收头节点的下一个结点，然后往后遍历，直到遍历到头节点结束。

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

4.6 尾删

      由图可知，要建立phead和phead->prev->prev的联系，同时由于还要释放最后一个结点（phead->prev），所以在建立联系之前要现保存这个被释放的空间，等建立联系完再释放！！同时要注意一条规则，就是当链表中只有哨兵结点的时候，我们称该链表为空链表！因此如果链表只存在哨兵结点，那么删除是没有意义的，所以必须断言！

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//链表只有哨兵结点时删除没意义
	LTNode* del = phead->prev;//del记录最后一个结点
	del->prev->next = phead;//倒数第二个结点的后驱指针指向头结点
	phead->prev = del->prev;//头节点的前驱结点指向倒数第二个结点
	free(del);//释放最后一个结点
	del = NULL;
}

4.7 头删

       由图可知，要建立phead和phead->next->next的联系，同时由于还要释放第二个结点（phead->next），所以在建立联系之前要现保存这个被释放的空间，等建立联系完再释放！！

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//链表只有哨兵结点时删除没意义
	LTNode* del = phead->next;//del记录第二个结点
	del->next->prev = phead;//第二个结点的前驱指针指向头结点
	phead->next = del->next;//头节点的后驱指针指向第三个结点
	free(del);//释放第二个结点
	del = NULL;
}

4.8 查找

     涉及到对指定位置进行操作的时候，需要设置一个查找函数，根据我们需要的数据返回他的结点地址

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)//遍历链表
	{
		if (pcur->data == x)
			return pcur;//找到的话返回该结点
		pcur = pcur->next;
	}
	//循环结束还是没找到
	return NULL;
}

4.9 指定位置之后插入

        由图可知，指定位置插入相当于将新结点插入到指定位置（pos）和指定位置下一个结点的位置（pos->next）,然后建立pos pos->next newnode的联系，而且这里用不到头节点！

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);//保证pos为有效结点
	LTNode* newnode = LTBuyNode(x);//申请新节点
	//建立pos pos->next newnode的联系
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;//pos的后一个结点的前驱结点指向新节点
	pos->next = newnode;//pos结点的后继结点指向新结点
}

4.10 指定位置删除

       右图可知建立指定位置的前一个结点（pos->prev）和指定位置的后一个结点（pos->next）的联系，并释放pos。

void LTErase(LTNode* pos)
{
	assert(pos);//保证pos为有效结点
	pos->prev->next = pos->next;//pos的前一个结点的后继指针指向pos后一个结点
	pos->next->prev = pos->prev;//pos的后一个结点的前驱指针指向pos的前一个结点
	free(pos);//释放pos
	pos = NULL;
}

4.11 销毁链表

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode*next = NULL;
	while (pcur != phead)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//除了头结点都释放完毕
	free(phead);
	//phead = NULL;//没有用！
}

为什么phead=NULL没有用？？

       因为我们使用的是一级指针，这里相当于是值传递，值传递形参改变不了实参，所以将phead置空是没有意义的，其实如果这里使用二级指针，然后传地址就可以了，但是为了保持接口一致性，我们还是依照这种方法，但是phead=NULL必须在主函数中去使用，所以我们在调用销毁链表的函数的时候，别忘记了phead=NULL！！

五、带头双向循环链表实现的全部代码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int LTDataType;//对类型进行重命名，后面可以通过修改存储其他数据类型
typedef struct ListNode
{
	LTDataType data;//保存的数据
	struct ListNode* prev;//指针保存前一个结点的地址
	struct ListNode* next;//指针保存后一个结点的地址
}LTNode;
 
 
LTNode* LTBuyNode(LTDataType x);//申请新的链表结点
LTNode* LTInit();//初始化（申请一个哨兵结点）
void LTPushBack(LTNode* phead, LTDataType x);//尾插 （最后一个结点后插入或哨兵结点前插入）
void LTPushFront(LTNode* phead, LTDataType x);//头插 （哨兵结点后的插入）
void LTPrint(LTNode* phead);//打印
void LTPopBack(LTNode* phead);//尾删
void LTPopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsert(LTNode* pos, LTDataType x);//指定位置之后插入
void LTErase(LTNode* pos);//指定位置删除
void LTDestroy(LTNode* phead);//销毁链表

List.c

#include"List.h"
 
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);//申请失败需要强制退出程序
	}
	//申请成功，则新节点的前驱结点和后驱结点都指向自己
	newnode->data = x;
	newnode->prev = newnode->next = newnode;
	return newnode;
}
 
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);//哨兵结点可以不存储数据，我们默认给个-1
	return phead;//返回哨兵结点
}
 
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);//申请新节点
	//建立phead phead->prev newnode的联系
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;//尾结点的后继结点指向新节点
	phead->prev = newnode;//哨兵结点的前驱指针指向新结点
}
 
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);//申请新节点
	//建立phead phead->next newnode的联系
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->next->prev = newnode;//头节点的下一个结点的前驱指针指向新结点
	phead->next = newnode;//头节点的后继指针指向新节点
}
 
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
 
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//链表只有哨兵结点时删除没意义
	LTNode* del = phead->prev;//del记录最后一个结点
	del->prev->next = phead;//倒数第二个结点的后驱指针指向头结点
	phead->prev = del->prev;//头节点的前驱结点指向倒数第二个结点
	free(del);//释放最后一个结点
	del = NULL;
}
 
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//链表只有哨兵结点时删除没意义
	LTNode* del = phead->next;//del记录第二个结点
	del->next->prev = phead;//第二个结点的前驱指针指向头结点
	phead->next = del->next;//头节点的后驱指针指向第三个结点
	free(del);//释放第二个结点
	del = NULL;
}
 
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)//遍历链表
	{
		if (pcur->data == x)
			return pcur;//找到的话返回该结点
		pcur = pcur->next;
	}
	//循环结束还是没找到
	return NULL;
}
 
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);//保证pos为有效结点
	LTNode* newnode = LTBuyNode(x);//申请新节点
	//建立pos pos->next newnode的联系
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;//pos的后一个结点的前驱结点指向新节点
	pos->next = newnode;//pos结点的后继结点指向新结点
}
 
void LTErase(LTNode* pos)
{
	assert(pos);//保证pos为有效结点
	pos->prev->next = pos->next;//pos的前一个结点的后继指针指向pos后一个结点
	pos->next->prev = pos->prev;//pos的后一个结点的前驱指针指向pos的前一个结点
	free(pos);//释放pos
	pos = NULL;
}
 
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode*next = NULL;
	while (pcur != phead)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//除了头结点都释放完毕
	free(phead);
	//phead = NULL;//没有用！
}

六、顺序表和链表的优缺点分析

1、存储空间

顺序表物理上连续

链表逻辑上连续，但是物理上不连续

2、随机访问

顺序表可以通过下标去访问

链表不可以直接通过下标去访问

3、任意位置插入或者删除元素

顺序表需要挪移元素，效率低

链表只需修改指针指向

4、插入

动态顺序表空间不够时需要扩容

链表没有容量的概念

5、应用场景

顺序表应用于元素高效存储+频繁访问的场景

链表应用于任意位置插入和删除频繁的场景

总之：没有绝对的优劣，都要各自适合的应用场景！！