【数据结构】双向链表（详细代码及配图）

荔枝成为编程大师

939人浏览 · 2026-04-07 21:00:44

荔枝成为编程大师 · 2026-04-07 21:00:44 发布

小编主页详情<-请点击
 小编gitee代码仓库<-请点击

本文主要介绍了数据结构的双向链表，内容全由作者原创（无AI），同时深度解析了双向链表增删查等功能，并带有配图帮助博友们更好的理解，点个关注不迷路，下面进入正文~~

前言：链表的分类

1.单向或者双向
2.带头或者不带头
3.循环或者不循环

总共有8种（2*2*2），而常见的主要有两种，分别是无头单向不循环链表（简称单链表），以及带头双向循环链表（简称双向链表），本文主要介绍的是双向链表。

1.双向链表节点的结构

双向链表的特点是既能找到前一个节点又能找到后一个节点，因此双向链表的节点除了存放需要存储的数据，还应该存储前后两个节点的地址

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

2.双向链表需要实现的方法

//声明双向链表中提供的方法

//初始化
void LTInit(LTNode** pphead);
//LTNode* LTInit();
void LTDesTroy(LTNode* phead);

void LTPrint(LTNode* phead);

//插入数据之前，链表必须初始化到只有一个头结点的情况
//不改变哨兵位的地址，因此传一级即可
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);

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


//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);

3.双向链表的具体实现方法

3.1创建节点

这里需要注意：双向链表是循环的，尾节点应当指向头节点，不应该指向NULL，所以在创建节点的时候newnode的next节点和prev节点都应该指向自己，这样才能循环。

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

3.2双向链表的初始化

双向链表的哨兵位不会被读取数据，因此只用给他赋值一个无效数据，这里赋值-1
双向链表的头指针在初始化的时候需要改变，所以这里传的是二级指针

void LTInit(LTNode** pphead)
{
	//给双向链表创建一个哨兵位
	*pphead = LTBuyNode(-1);
}

3.3双向链表的打印

双向链表的打印比较简单，不在过多赘述

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

3.4双向链表的尾插

思路：

1.尾插需要改变三个节点，分别是phead、phead->prev、newnode
2.没有顺序的改变节点很容易找不到下一个需要修改的节点，因此我们先修改不会影响链表顺序的newnode节点
3.将newnode节点的prev指向phead->prev，newnode节点的next指向phead
4.将phead->prev节点的next指向newnode，head节点的prev指向newnode
5.插入数据之前，链表必须初始化到只有一个头结点的情况，不改变哨兵位的地址，因此传一级指针即可

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

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

	phead->prev->next = newnode;
	phead->prev = newnode;
}

问题：phead->prev->next = newnode;和 phead->prev = newnode;可以完全对换位置吗？
答案：不行！先执行phead->prev = newnode会导致找不到原来的phead->prev

3.5双向链表的头插

往头节点前面插入叫尾插，往头节点后面插入叫头插

思路：

1.尾插需要改变三个节点，分别是phead、phead->next、newnode
2.没有顺序的改变节点很容易找不到下一个需要修改的节点，因此我们先修改不会影响链表顺序的newnode节点
3.将newnode节点的prev指向phead，newnode节点的next指向phead->next
4.将phead->next节点的prev指向newnode，head节点的next指向newnode
5.插入数据之前，链表必须初始化到只有一个头结点的情况，不改变哨兵位的地址，因此传一级指针即可

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

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

	phead->next->prev = newnode;
	phead->next = newnode;
}

3.6双向链表的尾删

思路：

1.当我们完成链表的尾删后，还需要将该节点释放掉，为了避免找不到这个节点，我们将创建一个临时变量del=phead->prev来记录我们要删除的尾节点
2.phead节点的prev指向del->prev
3.del->prev节点的next指向phead
4.将del释放掉
5.链表必须有效且链表不能为空（只有一个哨兵位）

void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next!=NULL);
	LTNode* del = phead->prev;

	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}

3.7双向链表的头删

思路：

1.当我们完成链表的头删后，还需要将该节点释放掉，为了避免找不到这个节点，我们将创建一个临时变量del=phead->next来记录我们要删除的头节点
2.phead节点的next指向del->next
3.del->next节点的prev指向phead
4.将del释放掉
5.链表必须有效且链表不能为空（只有一个哨兵位）

void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != NULL);
	LTNode* del = phead->next;

	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

3.8双向链表的查找

双向链表的查找比较简单，不在过多赘述

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

3.9在指定位置之后插入数据

思路：

1.在指定位置之后插入数据需要改变三个节点，分别是pos、pos->next、newnode
2.没有顺序的改变节点很容易找不到下一个需要修改的节点，因此我们先修改不会影响链表顺序的newnode节点
3.将newnode节点的prev指向pos，newnode节点的next指向pos->next
4.将pos->next节点的prev指向newnode，pos节点的next指向newnode
5.插入数据之前，链表必须初始化到只有一个头结点的情况，不改变哨兵位的地址，因此传一级指针即可

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

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

3.10删除指定位置的节点

思路：

1.将pos->prev节点的next指向pos->next
2.将pos->next节点的prev指向pos->prev
3.释放pos

void LTErase(LTNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

注意：
1.这里的pos理论上不能等于phead，但是没有参数phead，无法增加校验。
2.这里理论上需要传二级指针，但为了接口一致性，这里传一级指针，在使用完这个函数后需要手动将find置为空指针。

3.11将双向链表的初始化保持接口一致性

上面我们说的双向链表的初始化我们传入的二级指针，下面我们进行修改

LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

这样我们做到了保持接口一致性，使传入的参数要么为空，要么为一级指针

3.12双向链表的销毁

思路：

1.定义pcur为phead->next节点
2.next指针记录pcur下一个节点的地址，每当pcur释放掉一个节点时就赋值为next，知道pcur走到phead时停止循环
3.将phead释放掉

void LTDesTroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur指向phead，而phead还没有被销毁
	free(phead);
	phead = NULL;
}

LTErase和LTDestory参数理论上都要传二级指针，因为我们需要让形参的改变影响到实参，但为了保持接口一致性才传的一级~
传一级指针存在的问题是，当形参phead置为NULL后，实参plist并不会被修改为NULL，因此解决办法是：调用完方法后手动将实参置为NULL~