双向链表专题

在之前的单链表专题中，了解的单链表的结构是如何实现的，以及学习了如何实现单链表得各个功能。单链表虽然也能实现数据的增、删、查、改等功能，但是要找到尾节点或者是要找到指定位置之前的节点时，还是需要遍历链表，这就会使得程序的效率受到影响。因此在本篇中就要来学习另外一种链表——双向链表，在此链表中在实现以上的功能时，不再需要遍历。接下来就开始双向链表专题的学习吧！！！

---

1.链表的分类 

在学习双向链表的实现前我们先要来了解链表可以分为哪些，链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构

 

列表的带头是指在链表中存在“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的” 。单向还是双向就表示链表是在一个链表的节点中是只能找到下一个节点还是能找到下一个节点并且还能找到前一个节点。循环还是不循环是指链表是否能通过尾节点找到头节点。

因此这些链表就可以按照带头还是不带头，单向还是双向，循环还是不循环分为以下的形式

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

单链表就是之前我们实现过的，其具体是不带头单向不循环的链表，而在本篇中要学习的双链表具体就是带头双向循环的链表。

2. 双向链表的实现 

2.1双链表的结构 

在实现双链表中也是和单链表一样用结构体来表示节点，但在双链表中中表示结构体的节点内部与单链表中有所不同，在其内部会多一个指向前节点的指针变量。

在此在实现节点时定义一个结构体struct ListNode来表示结构体的节点，在其内部有三个成员变量，第一个是一个整型变量data来表示节点中存放的数据信息，第二个是一个结构体指针来存放上一个节点的地址，第三个是一个结构体指针来存放下一个节点的地址。

typedef int LTDataType;//将int重命名，方便之后要修改数据类型时修改
typedef struct ListNode//将结构体重命名，简化结构体的名称
{
	LTDataType data;//节点内数据
	struct ListNode* prev;//上一个节点的指针
	struct ListNode* next;//下一个节点的指针
}LTNode;

2.2程序文件的设置

以下是双链表文件的设置以及各文件中要实现的内容

注：在SList.h中在文件的头部写入以下代码中要使用到的库函数的头文件

2.3初始化双链表

由于我们实现的双链表是带头的，也就是带有哨兵位节点的，所以在双链表中不同于单链表是需要先初始化的。在初始化中就是要创建一个哨兵位的节点。

首先要在List.h内内完成初始化双链表函数的声明

void LTInit(LTNode** pphead);//初始化双链表

将该函数命名为LTInit，该函数的的参数是链表中第一个结构体指针的地址

由于在双链表中也是要在插入等函数中都创建新的节点，所以将创建新节点封装到函数NewNode内，之后再要创建新节点就只需调用该函数

LTNode* NewNode(LTDataType x)//创建新节点
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("newnode!");
		exit(1);
	}
	newnode->data = x;
	newnode->prev = newnode->next = newnode;
}

在NewNode函数内在使用malloc申请内存空间后就将要存入的数据赋值给节点中的data，并且要在创建新的节点后就要使得该节点是循环的，这就要让newnode内的next指针和prev指针都指向该新节点

 

之后就是在List.c内完成函数的实现

因为在哨兵位节点内的数据应是随机的，所以在此初始化双链表中创建哨兵位节点时就只需要在调用NewNode函数时传的参数为之后都不会使用到的值，在此传的是-1 

void LTInit(LTNode** pphead)//初始化双链表(即创建哨兵位节点)
{
  *pphead = NewNode(-1);
}

 2.4展示双链表

首先要在List.h内完成对打印双链表函数的声明

void LTPrint(LTNode* phead);//打印双链表

将该函数命名为LTPrint，由于不用改变函数的参数，也就是不需要改变指向链表中第一个节点的指针的指向，使用该打印函数进行的是传值调用，函数的参数就是指向链表第一个节点的指针

之后就是在List.c内完成对打印函数的实现

 在实现打印函数的代码前先来分析如何来遍历双链表，如以下双链表

一开始让pcur指向头节点的下一个节点，之后打印节点数据后就使得pcur指向该节点的下一个节点，也就是让pcur等于pcur->next，在此一直遍历下去直到pcur指向头节点时就停止pcur的移动。这样就可以完成对双链表的遍历。

因此通过以上的示例分析就可以得出循环的结束条件为pcur=phead，所以在while循环的判断部分就为pcur！=phead 

void LTPrint(LTNode* phead)//打印双链表
{
	LTNode* pcur = phead->next;
	while (pcur!=phead)
	{
		printf("%d ->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

2.5在链表中查找指定数据

要实现一个函数能查找在双链表中是否存在要查找的数据，首先就要在List.h内声明该函数 

LTNode* LTFind(LTNode* phead, LTDataType x);//查找指定数据

将该函数命名为LTFind，由于查找是未对函数的参数作出改变，所以该函数进行的也是传值调用，函数的参数有两个，一个是节点的结构体指针，另一个是要查找的数据，函数的返回类型是LTNode*的结构体指针

之后就是在List.c内完成查找函数的实现

在查找数据是否存在也是要遍历双链表，判断每个节点内的数据是否与要查找的数据相同，若相同就返回节点的指针。如果在遍历完双链表后都未找到与要查找数据相同的节点，这时就返回NULL

LTNode* LTFind(LTNode* phead, LTDataType x)//查找
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur ->next;
	}
	return NULL;
}

2.6双链表各功能的实现

2.6.1尾插

要实现一个函数能在双链表的尾部插入数据，首先要在List.h内完成对尾插函数的声明

void LTPushBack(LTNode* phead, LTDataType x);//尾插

将该函数命名为LTPushBack，函数的参数有两个，一个是节点的结构体指针 ，另一个是要插入的数据

接下来我们就来分析如何在双链表中实现尾插，例如以下图示要在双链表的末尾插入节点，也就是要在在d3节点后插入新的节点要进行什么样的操作呢？

这时就只需要作出以下的改变就可以实现尾插

将新节点内的prev指针指向d3节点；next指针指向phead节点，再将d3的next指针指向新节点，再将phead的prev指针指向新节点。完成这些操作就可以实现在原本的双链表中尾插新的节点 

完成的尾插的分析后之后就是在List.c内完成尾插函数的实现

在尾插过程中本质就是按照以上图所示进行相关的更改，将新节点newnode的prev指针指向头节点phead；将nownode的next指针指向原尾节点。将头节点phead的prev指针指向newnode，将原链表的尾节点phead->prev的next指针指向newnode

在尾插过程中要对头节点的结构体指针进行解引用，所以头节点指针不能为空，所以要给phead进行assert断言

void LTPushBack(LTNode* phead, LTDataType x)//尾插
{
	assert(phead);
	LTNode* newnode = NewNode(x);
	//phead   phead->prev newnode 
    //改变新节点newnode的指向
	newnode->next = phead;
	newnode->prev = phead->prev;
    //改变尾节点的指向
	phead->prev->next = newnode;
    //改变头节点的指向
	phead->prev = newnode;
}

2.6.2头插 

要实现一个函数能在双链表的头部插入数据，首先要在List.h内完成对头插函数的声明

void LTPushFront(LTNode* phead, LTDataType x);//头插

将该函数命名为LTPushFront，函数的参数有两个，一个是节点的结构体指针 ，另一个是要插入的数据

接下来我们就来分析如何在双链表中实现头插，例如以下图示要在双链表的头部插入节点，也就是要在在head节点后插入新的节点要进行什么样的操作呢？

这时就只需要作出以下的改变就可以实现头插

将新节点内的prev指针指向phead节点；next指针指向d1节点，再将phead的next指针指向新节点，再将d1的prev指针指向新节点。完成这些操作就可以实现在原本的双链表中头插新的节点 

完成的头插的分析后之后就是在List.c内完成头插函数的实现

在头插过程中本质就是按照以上图所示进行相关的更改，将新节点newnode的prev指针指向头节点phead；将nownode的next指针指向原头节点的下一个节点phead->next。将头节点phead的next指针指向newnode，将原链表的原头节点的下一个节点phead->next的prev指针指向newnode 

在头插过程中要对头节点的结构体指针进行解引用，所以头节点指针不能为空，所以要给phead进行assert断言 

void LTPushFront(LTNode* phead, LTDataType x)//头插
{
	assert(phead);
	LTNode* newnode = NewNode(x);
	//phead newnode phead->next
    //改变新节点newnode的指向
	newnode->next = phead->next;
	newnode->prev = phead;
    //改变头节点下一个节点的指向
	phead->next->prev = newnode;
    //改变头节点的指向
	phead->next = newnode;
}

2.6.3尾删

要实现一个函数能删除双链表尾部的数据，首先要在List.h内完成对尾删函数的声明

void LTPopBack(LTNode* phead);//尾删

将该函数命名为LTPopBack，函数的参数为节点的结构体指针 

接下来我们就来分析如何在双链表中实现尾部删除，例如以下图示要删除双链表尾部节点，也就是要释放d3节点的空间要进行什么样的操作呢？

这时就只需要作出以下的改变就可以实现尾删

先让头节点的prev指针指向原尾节点前的节点，再让原尾节点前的节点的next指针指向头节点，再释放原来的尾节点。完成这些操作就可以实现在原本的双链表中删除尾部的节点 

 

完成的尾删的分析后之后就是在List.c内完成尾删函数的实现

在尾删过程中本质就是按照以上图所示进行相关的更改，以上创建一个指向原尾节点的指针del，这样可以避免改变指针节点指向后找不到原来的尾节点。之后将头节点phead的prev指针指向del之前的节点del->prev，将原链表的del指向的节点的前一个节点del->next的next指针指向phead。最后再将del指针指向的节点释放，后将指针del置为NULL  

在尾删过程中要对头节点的结构体指针进行解引用，所以头节点指针不能为空，所以要给phead进行assert断言 
同时尾删过程中只有哨兵节点时，无法完成删除，所以要给phead->next!=phead进行assert断言 

void LTPopBack(LTNode* phead)//尾删
{
	assert(phead && phead->next != phead);
	//phead phead->prev->prev  phead->prev
	LTNode* del = phead->prev;
	//phead del->prev del
	phead->prev = del->prev;
	del->prev->next = phead;
	free(del);//删除del节点
	del = NULL;
}

2.6.4头删 

要实现一个函数能删除双链表尾部的数据，也就是删除头节点之后的第一个节点，首先要在List.h内完成对头删函数的声明

void LTPopFront(LTNode* phead);//头删

将该函数命名为LTPopFront，函数的参数为节点的结构体指针

接下来我们就来分析如何在双链表中实现头部删除，例如以下图示要删除双链表头部节点，也就是要释放d1节点的空间要进行什么样的操作呢？ 

这时就只需要作出以下的改变就可以实现尾删

先让头节点的next指针指向原尾节点前的节点，再让原尾节点后两位的节点的prev指针指向头节点，再释放原来的head节点之后的节点。完成这些操作就可以实现在原本的双链表中删除尾部的节点 

 

 完成的头删的分析后之后就是在List.c内完成头删函数的实现

在头删过程中本质就是按照以上图所示进行相关的更改，以上创建一个指向原头节点之后的第一个节点的指针del，这样可以避免改变指针节点指向后找不到原来的尾节点。之后将头节点phead的next指针指向del之后的节点del->next，将原链表的del指向的节点的后一个节点del->next的prev指针指向phead。最后再将del指针指向的节点释放，后将指针del置为NULL  

在头删过程中要对头节点的结构体指针进行解引用，所以头节点指针不能为空，所以要给phead进行assert断言 
同时头删过程中只有哨兵节点时，无法完成删除，所以要给phead->next!=phead进行assert断言 

void LTPopFront(LTNode* phead)//头删
{
	assert(phead &&phead->next!=phead);
	//phead phead->next phead->next->next
	LTNode* del = phead->next;
	//phead del del->next
	phead->next = del->next;
	del->next->prev = phead;
	free(del);//删除del节点
	del = NULL;
}

 

2.6.5 在指定位置之后插入

要实现一个函数能在双链表指定位置后插入数据，首先要在List.h内完成对在指定位置之后插入函数的声明

void LTInsert(LTNode* pos, LTDataType x);//在指定pos位置插入

将该函数命名为LTInsert，函数的参数有两个，一个是要插入位置节点的结构体指针，另一个是要插入的数据

接下来我们就来分析如何在双链表中实现在指定位置之后插入节点，例如以下图示要在双链表d1节点后插入新的节点，要进行什么样的操作呢？ 

这时就只需要作出以下的改变就可以实现在指定位置之后插入

将新节点内的prev指针指向d1节点；next指针指向d2节点，再将d1的next指针指向新节点，再将d2的prev指针指向新节点。完成这些操作就可以实现在原本的双链表中在指定位置之后插入新的节点 

 

 完成的在指定位置之后插入的分析后之后就是在List.c内完成在指定位置之后插入函数的实现

在在指定位置之后插入的过程中本质就是按照以上图所示进行相关的更改，将新节点newnode的prev指针指向pos节点；将nownode的next指针指向原pos节点的下一个节点pos->next。将pos节点的next指针指向newnode，将原链表的原pos节点的下一个节点pos->next的prev指针指向newnode

在指定位置之后插入过程中要对pos节点的结构体指针进行解引用，所以pos指向的节点指针不能为空，所以要给pos进行assert断言 

void LTInsert(LTNode* pos, LTDataType x)//在指定pos位置之后插入
{
	assert(pos);
	//pos newnode pos->next
	LTNode* newnode = NewNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

2.6.6删除指定位置

要实现一个函数能删除双链表指定位置的数据，首先要在List.h内完成对指定位置删除函数的声明

void LTErase(LTNode* pos);//删除指定pos位置的节点

将该函数命名为LTErase，函数的参数为要删除位置节点的结构体指针 

接下来我们就来分析如何在双链表中实现指定位置删除，例如以下图示要删除d2节点，也就是要释放d2节点的空间要进行什么样的操作呢？ 

这时就只需要作出以下的改变就可以实现删除指定位置的节点

先让d1节点的next指针指向d3节点，再让d3节点的prev指针指向d1节点，再释放原来的d2节点。完成这些操作就可以实现在原本的双链表中删除d2节点

 

完成的指定位置删除的分析后之后就是在List.c内完成指定位置删除函数的实现

在删除指定位置也就是删除pos指针指向的节点过程中本质就是按照以上图所示进行相关的更改，将pos指针指向的节点的前一个节点pos->prev的next指针指向pos指针指向的节点之后的节点pos->next，将pos指针指向的节点的后一个节点pos->next的prev指针指向pos指针指向的节点之前的节点pos->prev。最后再将pos指针指向的节点释放，后将指针pos置为NULL  

在删除指定位置过程中要对pos节点的结构体指针进行解引用，所以pos指向的节点指针不能为空，所以要给pos进行assert断言 

void LTErase(LTNode* pos)//删除指定pos位置的节点
{
	assert(pos);
	//pos->prev pos pos->next
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

 但这时就会存在一个问题：销毁双链表函数进行的是传值调用，形参的改变无法影响实参，所以在以下代码中最后将pos=NULL，不会使得调用函数外的结构体指针置为NULL，这就需要在调用完该函数后再将结构体指针置为NULL

 

2.7销毁双链表 

由于我们实现的双链表的节点空间是动态内存开辟的，所以在双链表中是需要在使用完后销毁节点的。

首先要在List.h内内完成销毁双链表函数的声明

void LTDestory(LTNode* phead);//销毁双链表

将该函数命名为LTDestory，该函数的的参数是链表中第一个结构体指针的地址

之后就是在List.c内实现销毁函数
以下函数是通过遍历的方法来将链表中的节点一个个释放，最后遍历完出函数时就只剩下phead指向的头节点，这时再释放该节点就可以将双链表全部销毁

void LTDestory(LTNode* phead)//销毁双链表
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

但这时就会存在一个问题：销毁双链表函数进行的是传值调用，形参的改变无法影响实参，所以在以下代码中最后将phead=NULL，不会使得调用函数外的结构体指针置为NULL，这就需要在调用完该函数后再将结构体指针置为NULL

#include"List.h"
void test()
{
	LTNode* plist = NULL;
	plist=LTInit();
	//测试尾插
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPrint(plist);
	//测试销毁双链表
	LTDestory(plist);
	plist = NULL;
}
int main()
{
	test();
	return 0;
}

那么有的读者就会发出疑问：为什么不直接在LTErase函数和LTDestory的参数直接传传二级指针呢？
其实理论上LTErase和LTDestory参数理论上是要传二级，因为我们需要让形参的改变影响到实参，但是为了保持接口的一致性才传的一级指针

传一级指针的问题是：当形参phead置为NULL后，实参plist不会被修改为NULL，因此解决方法是调用完函数后手动将实参置为NULL

 

3.双链表完整代码

为了保持接口的一致性可以将初始化函数修改为以下形式

LTNode* LTInit()//初始化双链表
{
	LTNode* phead = NewNode(-1);
	return phead;
}

 

List.h

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma once 
#include
#include
#include
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;
//void LTInit(LTNode** pphead);//初始化双链表
LTNode* LTInit();//初始化双链表
void LTDestory(LTNode* phead);//销毁双链表
void LTPrint(LTNode* phead);//打印双链表
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopFront(LTNode* phead);//头删
void LTPopBack(LTNode* phead);//尾删
void LTInsert(LTNode* pos, LTDataType x);//在指定pos位置插入
void LTErase(LTNode* pos);//删除指定pos位置的节点

 

List.c

#include"List.h"
LTNode* NewNode(LTDataType x)//创建新节点
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("newnode!");
		exit(1);
	}
	newnode->data = x;
	newnode->prev = newnode->next = newnode;
}
void LTPrint(LTNode* phead)//打印双链表
{
	LTNode* pcur = phead->next;
	while (pcur!=phead)
	{
		printf("%d ->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
LTNode* LTFind(LTNode* phead, LTDataType x)//查找
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur ->next;
	}
	return NULL;
}

//void LTInit(LTNode** pphead)//初始化双链表(即创建哨兵位节点)
//{
//	*pphead = NewNode(-1);
//}
LTNode* LTInit()//初始化双链表
{
	LTNode* phead = NewNode(-1);
	return phead;
}
void LTDestory(LTNode* phead)//销毁双链表
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

void LTPushFront(LTNode* phead, LTDataType x)//头插
{
	assert(phead);
	LTNode* newnode = NewNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

void LTPushBack(LTNode* phead, LTDataType x)//尾插
{
	assert(phead);
	LTNode* newnode = NewNode(x);
	//phead   phead->prev newnode 
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}
void LTPopFront(LTNode* phead)//头删
{
	assert(phead &&phead->next!=phead);
	//phead phead->next phead->next->next
	LTNode* del = phead->next;
	//phead del del->next
	phead->next = del->next;
	del->next->prev = phead;
	free(del);//删除del节点
	del = NULL;
}
void LTPopBack(LTNode* phead)//尾删
{
	assert(phead && phead->next != phead);
	//phead phead->prev->prev  phead->prev
	LTNode* del = phead->prev;
	//phead del->prev del
	phead->prev = del->prev;
	del->prev->next = phead;
	free(del);//删除del节点
	del = NULL;
}
void LTInsert(LTNode* pos, LTDataType x)//在指定pos位置插入
{
	assert(pos);
	//pos newnode pos->next
	LTNode* newnode = NewNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
	
}
void LTErase(LTNode* pos)//删除指定pos位置的节点
{
	assert(pos);
	//pos->prev pos pos->next
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}