数据结构之双链表的相关知识点及应用-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构之双链表的相关知识点及应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

个人主页：我要学编程(ಥ_ಥ)-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);
}

在双链表中尾插数据

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

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

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

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

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

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

//尾插数据
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");
}

在双链表中尾删数据

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

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

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

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

//尾删数据
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;
}

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

在双链表中头插数据

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

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

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

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

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

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

//头插数据
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;
}

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

在双链表中头删数据

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

//头删数据
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是哨兵位：

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

情况二：pos是中间位置：

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

情况三：pos是尾节点：

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

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

//在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在中间位置

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

情况二：pos在结尾位置：

数据结构之双链表的相关知识点及应用,数据结构（C语言版）,数据结构,c语言,链表

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

//在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);

好啦！本期数据结构双链表的学习就到此为止啦！我们下一期再一起学习吧！文章来源地址https://www.toymoban.com/news/detail-858575.html

到了这里，关于数据结构之双链表的相关知识点及应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！