深入解析数据结构之双向链表

云泽808

发布于 2025-12-30 17:38:19

640

一、链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2×2×2）链表结构

下面细节说明一下

d1，d2，d3就是节点中存储的有效的数据

带头链表中的头节点，不存储任何有效的数据，只用来占位子，也可以称之为“哨兵位” 在之前单链表的文章中，有时候会表述“头节点”，这个表述是不正确的，当时只是为了更方便理解所以这么写的。

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

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而更简单了。

二、双向链表

2.1 概念与结构

双向链表结构有所变化，其有三个成员，存储的数据，指向下一个节点的指针，指向前一个结点的指针

这里区分一下空的单链表和空的双向链表

这是一个空的单链表

这是一个空的双向链表

2.2 双向链表的实现

2.2.1 初始化

List.h

初始化要改变头节点plist，phead接受的是实参plist，初始的情况下头节点为空，初始化需要将其改变为一个哨兵位，形参的改变要影响实参，所以要传一级指针的地址，用二级指针接收

List.c

哨兵位节点，也就是头节点，不存储任何有效的数据，随便存个值就可以

test.c

这样就完成了双向链表的初始化

实参也发生了改变

2.2.2 尾插

函数声明：

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

现在有了哨兵位，在双向链表的增删查改里面哨兵位节点都不会发生改变，所以尾插的参数中是一级指针

这里诈一想尾插操作要对头，尾，新，三个节点动手，很麻烦。没事，看主播的思路，主播是有操作的

这里如果先要对d3动手的话，就要修改原链表，所以先不修改原链表里的节点，先修改newnode节点里的指针，对newnode动手，先改prev再改next
然后修改d3，先要找到d3，这里通过head->prev找到d3，让d3的next指针指向newnode，不需要遍历，如果先对哨兵位的prev动手的话，这里就不能通过哨兵位来找d3了

此时修改哨兵位的prev指向

就算是对空双向链表的尾插也是一样的

对newnode动手，先改prev再改next
哨兵位先next，再prev

在初始化之中也可以直接复用创建节点的代码

2.2.3 头插

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

在单链表中，头插的时候第一个节点会不断发生改变，在双向链表之中，头插并不会影响到哨兵位，而是插入到第一个有效节点的前面，所以依旧使用一级指针

依旧先对newnode动手，让newnode->next指向d1，d1通过head->next找到，newnode-prev指向head
d1的prev指针指向newnode
head->next指向newnode

2.2.4 判断链表是否为空

在双向链表中，如果链表为空（只有一个哨兵位节点），是不能进行删除操作的，所以这里再额外封装一个函数来完成判断操作

//判断双向链表是否为空
bool LTEmpty(LTNode* phead);

这里要包含头文件#include<stdbool.h>

2.2.5 打印

要打印就要遍历双向链表，哨兵位节点只是个站岗放哨的，不需要打印

如果循环条件是节点不为空就进行打印，就会发现形成死循环了，所以循环条件是pcur!=phead

2.2.6 尾删

函数声明：

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

这里如果直接删除d3节点，d2就找不到了。所以先把d3节点用del存起来

先对d2next动手
head的prev指针指向d2

2.2.7 头删

函数声明：

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

d1是phead指针指向的下一个节点，这里用del存起来，d2是del的下一个节点

先对d2进行操作，先prev
对哨兵位进行操作，哨兵位的next指针指向d2

2.2.8 查找

函数声明：

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

2.2.9 在pos位置之后插入数据

函数声明：

//在指定位置之后插入数据
void LTInsertAfter(LTNode* pos, LTDataType x);

pos不能指向头节点，因为头节点不是一个有效的节点，而且前面写的查找方法是不能找到头节点的，因为头节点不存储任何有效的数据

newnode的prev指针指向d2，next指向d3
接下来如果先修改了d2的next指针指向newnode，就不能通过pos找到d3了，只能通过newnode找到d3，如果还想通过pos找d3，就要先修改d3的prev指针，对d2的next指针进行操作

2.2.8 在pos位置之前插入数据

函数声明：

//在指定位置之前插入数据
void LTInsertBefore(LTNode* pos, LTDataType x);

2.2.9 修改pos位置数据

函数声明：

//修改pos位置数据
void LTModify(LTNode* pos, LTDataType x);

2.2.10 删除pos位置节点

函数声明：

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

删除pos位置节点的时候，链表也不能为空，这里因为参数没有phead，所以没有办法断言

d1的next指向d3
d3的prev指向d1

2.2.11 销毁

只要是向操作系统申请的节点，就要全部还给操作系统，即哨兵位节点也要释放掉，所以这里传二级指针

链表里面有多个节点，每个节点都是独立申请的，要一个一个释放，但是不能从哨兵位开始遍历，而是要从哨兵位的下一个节点开始遍历，一轮循环完后，当pcur指向哨兵位的时候跳出循环，让pcur指向头节点的话，会形成死循环

这里删之前先将要删除节点的下一个节点存起来，只要当前节点不为空，就把当前节点释放掉，否则当前节点删除后，找下一个节点不好找了

这里删除之后pcur走到next指针指向的节点，只要pcur不为空，next就把下一个待销毁的节点存起来，然后把pcur销毁掉，pcur继续向后走

以此类推

这里销毁写完之后其实还有一个小问题当使用双向链表的时候，初始化和销毁形参都是二级指针，其他操作的参数都是一级指针，在日常我们经常会使用标准库里实现好的一些方法，比如说abs（绝对值），qsort，这些方法的参数都是固定的，有的传值有的传地址。

今后这个双向链表的数据结构如果要给其他人去用，但是对于使用的人来说，哪些方法要传地址，哪些方法要传值，这无形之中增加了记忆的成本，这样一会用一级指针，一会用二级指针，这对于使用的用户来说并不友好

为了保证代码实现接口的一致性，这里再对初始化和销毁进行修改，在初始化这里，是直接给了一个指针进行初始化的，就比如说我现在去买一桶油，我提了一个空的油桶，对售货员说麻烦给我灌满，而下面的操作就是我去超市买一桶油，既买了油，又买了桶。

接下来就不要参数，操作结束后，直接给一个指向哨兵位节点的指针函数声明：

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

销毁：函数声明：

//销毁---为了保持接口一致性
//void LTDesTroy(LTNode** pphead);
void LTDesTroy(LTNode* phead);

plist虽然空间已经被释放，但是plist没有置为NULL，这里就需要手动操作了，这是为了保持接口的一致性所要付出的代价

三、双向链表完整源码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义双向链表结构
typedef int LTDataType;
typedef struct ListNode {
	LTDataType data;
	struct ListNode* next; //指向下一个节点的指针
	struct ListNode* prev; //指向前一个节点的指针
}LTNode;

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

//销毁---为了保持接口一致性
//void LTDesTroy(LTNode** pphead);
void LTDesTroy(LTNode* phead);


//在双向链表中，增删改查都不会改变哨兵位节点
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);

bool LTEmpty(LTNode* phead);
void LTPrint(LTNode* phead);


LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插⼊数据----在pos位置之前插入数据自行实现
void LTInsert(LTNode* pos, LTDataType x);

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

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->next = newnode->prev = newnode;

	return newnode;
}

//初始化
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}
//void LTInit(LTNode** pphead)
//{
//	//*pphead = (LTNode*)malloc(sizeof(LTNode));
//	//if (*pphead == NULL)
//	//{
//	//	perror("malloc fail!");
//	//	exit(1);
//	//}
//	//(*pphead)->data = -1;
//	//(*pphead)->next = (*pphead)->prev = *pphead;
//	*pphead = LTBuyNode(-1);
//}


//销毁
void LTDesTroy(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//销毁头结点
	free(phead);
	phead = NULL;
}

//void LTDesTroy(LTNode** pphead)
//{
//	LTNode* pcur = (*pphead)->next;
//	while (pcur != *pphead)
//	{
//		LTNode* next = pcur->next;
//		free(pcur);
//		pcur = next;
//	}
//	//销毁头结点
//	free(*pphead);
//	*pphead = NULL;
//}

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 newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next->prev = newnode;
	phead->next = newnode;
}
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty(phead));

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

	free(del);
	del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* del = phead->next;
	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;
}
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->prev = pos;
	newnode->next = pos->next;

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

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

	free(pos);
	pos = NULL;
}

test.c

#include"List.h"

void test01()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	//LTPushFront(plist, 1);
	//LTPushFront(plist, 2);
	//LTPushFront(plist, 3);
	//LTPushFront(plist, 4);
	//
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);

	LTNode* pos = LTFind(plist, 2);
	//if (pos)
	//{
	//	printf("找到了！\n");
	//}
	//else {
	//	printf("未找到！\n");
	//}
	//LTInsert(pos, 100);
	//LTErase(pos);
	LTPrint(plist);

	//销毁
	//LTDesTroy(&plist);
	LTDesTroy(plist);
	plist = NULL;
}

int main()
{
	test01();
	return 0;
}