数据结构之双链表的相关知识点及应用

 找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构

目录

双链表的实现 

初始化双链表 

在双链表中尾插数据 

在双链表中尾删数据

在双链表中头插数据 

在双链表中头删数据 

在双链表中的指定位置之后插入数据 

在双链表中删除指定位置的数据

在双链表中查找指定位置

销毁双链表 

双链表源码 

---

学习完单链表后，就要开始学习链表中最重要的双链表了。

双链表是双向带头循环链表。与单链表是恰恰相反。

接下来就用双链表来实现一系列增删查改的功能。 

双链表的实现 

 在创建双链表之前，还得要做一些提起准备。创建三个文件：List.h  List.c  test.c  前面两个是实现双链表的，后面的 test.c 文件是测试双链表的各种功能。同样链表是由一个一个的节点组成的。我们就得由节点的结构。

创建节点：

typedef int LTDataType;
 
typedef struct ListNode
{
	struct ListNode* next; //指针保存下⼀个节点的地址
	struct ListNode* prev; //指针保存前⼀个节点的地址
	LTDataType data;
}LTNode;

初始化双链表 

因为双链表带头，因此，我们就得创建一个哨兵位。这个函数也可以叫做初始化函数。

//初始化
void LTInit(LTNode** pphead)//注意这里需要改变哨兵位，因此用二级指针接收
{
	//创建一个新的节点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		perror("malloc:");
		exit(1);
	}
	//把哨兵位的数据初始化为-1(无效数据)，后驱指针指向自己，前驱指针指向自己
	*pphead = phead;
	(*pphead)->data = -1;
	(*pphead)->next = (*pphead)->prev = *pphead;
}

只要是增加节点，就会有重复的代码因此我们分装成一个函数，并且我们在初始化函数也可以传我们想要设置的无效数据。

//增加节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

//初始化
void LTInit(LTNode** pphead)
{
	*pphead = LTBuyNode(-1);
}

在双链表中尾插数据 

情况一：链表中只有哨兵位：

情况二：链表中不止有哨兵位：

我们要尾插数据，就是要d3的next指针的指向，还要改变head的prev指针的指向。此外还得把新增加的节点prev指针指向d3，next指向head。

不能改变顺序的原因：如果改变了，就先把哨兵位的指向改变了，后面我们就找不到原链表的尾节点了，除非能把原链表的尾节点的地址提前存起来。

//尾插数据
void LTPushBack(LTNode* phead, LTDataType x)//哨兵位已经确定，不再改变，因此用一级指针
{
    assert(phead);//链表不能为空
	LTNode* newnode = LTBuyNode(x);
	//开始尾插节点  
	//链表中只有哨兵位
	if (phead->next == phead)
	{
		//先把新节点安排好
		newnode->next = phead;
		newnode->prev = phead;
		//哨兵位
		phead->next = newnode;
		phead->prev = newnode;
	}
	else
	{
		//先把新节点安排好
		newnode->next = phead;
		newnode->prev = phead->prev;
		//头节点：phead  尾节点：phead->prev   新节点：newnode
		phead->prev->next = newnode;
		phead->prev = newnode;
	}
}

写完之后，还得测试一下我们所写的代码是否正确：可以用打印函数来判断看看结果是否和我们的预期一样。

//打印数据
void LTPrint(LTNode* phead)
{
	//遍历寻找
	LTNode* pcur = phead->next;//头节点的数据是无效的，因此就不需要打印
	//因为是循环的，所以不能用空指针来判断，要看看是否指向的哨兵位
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

在双链表中尾删数据

情况一：链表中由多个有效数据：

情况二：链表中只有一个有效数据：

//尾删数据
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表不能为空并且链表中不能没有有效元素
	if (phead->next->next == phead)//只有一个有效数据
	{
		LTNode* freenode = phead->next;
		free(freenode);
		phead->next = phead;
		phead->prev = phead;
	}
	else
	{
		phead->prev->prev->next = phead;
		LTNode* freenode = phead->prev;
		phead->prev = phead->prev->prev;
		free(freenode);
		freenode = NULL;
	}
}

其实上面的写法可以简化为：

//尾删数据
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表不能为空并且链表中不能没有有效元素
	phead->prev->prev->next = phead;
	LTNode* freenode = phead->prev;
	phead->prev = phead->prev->prev;
	free(freenode);
	freenode = NULL;
}

也就是说不管链表的有效元素的个数有多少，都不影响。（把特殊情况带入这个简化版里判断就可以了）。

在双链表中头插数据 

情况一：链表中不止有哨兵位： 

之所以在哨兵位的前面插入数据叫作尾插，是因为双链表是循环的，当遍历到d3后就会找到前面的节点，这就是在尾部，因此也叫作尾插。 

同样顺序不能变的原因也是因为顺序一旦改变，先把phead的next指向给改变了，就找不到了要更改的数据了。

情况二：链表中只有哨兵位：

//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	if (phead->next == phead)//只有哨兵位
	{
		newnode->next = phead;
		newnode->prev = phead;
		phead->next = newnode;
		phead->prev = newnode;
	}
	else
	{
		//先安排新节点
		newnode->next = phead->next;
		newnode->prev = phead;
		//头节点：phead  尾节点（相较于新节点）：phead->prev  新节点：newnode
		phead->next->prev = newnode;
		phead->next = newnode;
	}
}

这个头插也是可以简化的：

//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//先安排新节点
	newnode->next = phead->next;
	newnode->prev = phead;
	//头节点：phead  尾节点（相较于新节点）：phead->prev  新节点：newnode
	phead->next->prev = newnode;
	phead->next = newnode;
}

简化判断的方法就是把特殊情况带入进去，看看能否成功。

在双链表中头删数据 

//头删数据
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表不为空并且链表的有效数据不能为空
	phead->next->next->prev = phead;
	LTNode* freenode = phead->next;
	phead->next = phead->next->next;
	free(freenode);
	freenode = NULL;
}

在双链表中的指定位置之后插入数据 

情况一：pos是哨兵位：

情况二：pos是中间位置：

情况三：pos是尾节点： 

上面的代码不管是在哪个位置都满足。

//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	//先安排好新节点
	newnode->prev = pos;
	newnode->next = pos->next;
	
	pos->next = newnode;
	pos->next->prev = newnode;
}

在双链表中删除指定位置的数据

 情况一：pos在中间位置

情况二：pos在结尾位置：

注意：这个指定位置不能是哨兵位。

//在pos位置删除数据
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
}

在双链表中查找指定位置

这个也比较简单，就是直接遍历整个双链表，如果没找到就返回NULL，找到就返回这个地址。

//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead && phead->next != phead);//链表不能为空并且链表不能只有哨兵位
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

销毁双链表 

就是把链表中的节点一个一个的释放空间就行了。

//销毁链表
void LTDestroy(LTNode* phead)
{
	assert(phead);
	//就是节点一个一个的销毁
	LTNode* pcur = phead->next;
	
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(pcur);
	pcur = NULL;
}

综合上面的代码来看，还有一个地方有点小瑕疵，就是初始化链表时，我们用的是二级指针，为了保持接口一致性，我们要用一级指针或者不传参数。

//初始化
LTNode* LTInit()
{
	LTNode* pplist = LTBuyNode(-1);
	return pplist;
}

双链表源码 

下面就是双链表完整的源码：

List.c

#include "List.h"
 
//增加节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}
 
 
//初始化
LTNode* LTInit()
{
	LTNode* pplist = LTBuyNode(-1);
	return pplist;
}
 
 
//尾插数据
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//开始尾插节点  
	//链表中只有哨兵位
	if (phead->next == phead)
	{
		//先把新节点安排好
		newnode->next = phead;
		newnode->prev = phead;
		//哨兵位
		phead->next = newnode;
		phead->prev = newnode;
	}
	else
	{
		//先把新节点安排好
		newnode->next = phead;
		newnode->prev = phead->prev;
		//头节点：phead  尾节点：phead->prev   新节点：newnode
		phead->prev->next = newnode;
		phead->prev = newnode;
	}
}
 
 
//打印数据
void LTPrint(LTNode* phead)
{
	//遍历寻找
	LTNode* pcur = phead->next;//头节点的数据是无效的，因此就不需要打印
	//因为是循环的，所以不能用空指针来判断，要看看是否指向的哨兵位
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
 
 
//尾删数据
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表不能为空并且链表中不能没有有效元素
	phead->prev->prev->next = phead;
	LTNode* freenode = phead->prev;
	phead->prev = phead->prev->prev;
	free(freenode);
	freenode = NULL;
}
 
 
//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//先安排新节点
	newnode->next = phead->next;
	newnode->prev = phead;
	//头节点：phead  尾节点（相较于新节点）：phead->prev  新节点：newnode
	phead->next->prev = newnode;
	phead->next = newnode;
}
 
 
//头删数据
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表不为空并且链表的有效数据不能为空
	phead->next->next->prev = phead;
	LTNode* freenode = phead->next;
	phead->next = phead->next->next;
	free(freenode);
	freenode = NULL;
}
 
 
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	//先安排好新节点
	newnode->prev = pos;
	newnode->next = pos->next;
	
	pos->next = newnode;
	pos->next->prev = newnode;
}
 
 
//在pos位置删除数据
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}
 
 
//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead && phead->next != phead);//链表不能为空并且链表不能只有哨兵位
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
 
 
//销毁链表
void LTDestroy(LTNode* phead)
{
	assert(phead);
	//就是节点一个一个的销毁
	LTNode* pcur = phead->next;
	
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(pcur);
	pcur = NULL;
}

List.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
typedef int LTDataType;
 
typedef struct ListNode
{
	struct ListNode* next; //指针保存下⼀个节点的地址
	struct ListNode* prev; //指针保存前⼀个节点的地址
	LTDataType data;
}LTNode;
 
//初始化
LTNode * LTInit();
 
//销毁链表
void LTDestroy(LTNode* phead);
 
//打印数据
void LTPrint(LTNode* phead);
 
//尾插数据
void LTPushBack(LTNode* phead, LTDataType x);
 
//尾删数据
void LTPopBack(LTNode* phead);
 
//头插数据
void LTPushFront(LTNode* phead, LTDataType x);
 
//头删数据
void LTPopFront(LTNode* phead);
 
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);
 
//在pos位置删除数据
void LTErase(LTNode* pos);
 
//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x);

好啦！本期数据结构双链表的学习就到此为止啦！我们下一期再一起学习吧！