双向链表的实现

时间：2024-10-01 19:24:56

前言

上节谈到单链表的实现，双向链表看似复杂，实际上只需套用单链表的实现，再让各个节点互相连

接即可，以下是具体实现与讲解。

相关接口如下：

#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 Print(LTNode*);
//初始化
void LTInit(LTNode**);


//插入数据
void LTPushBack(LTNode*,LTDataType);
void LTPushFront(LTNode*,LTDataType);


//删除
//判空
bool LTEmpty(LTNode*);

void LTPopBack(LTNode*);
void LTPopFront(LTNode*);


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

//在指定位置之前或之后插入节点
void LTInsert(LTNode* pos, LTDataType x);
void LTInsertBefore(LTNode* pos, LTDataType x);


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

//销毁
void LTDestroy(LTNode**);

//为了保持接口的一致性,优化代码
//将初始化和销毁函数传递的参数统一为一级指针
void LTDestroy2(LTNode*);
LTNode* LTInit2();

分析：

1. 首先定义链表结构，与单链表的单向连接不同，双链表需要两个指针来分别存储前后节点的地址。

2.我们把数据类型重定义为LTDataType，便于后续数据类型的修改。

例如，如果要把int类型的双链表改为char类型的双链表，只需要在重定义处将int改为char即可。

3.每一个接口在实现完成之后都要逐个测试！避免后续可能出现的大量报错！

test.c测试代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void ListTest01()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);//初始化,只有一个哨兵位,为空链表
	 
	
	//保持接口一致性使用一级指针
	LTNode* plist = LTInit2();


	//测验尾插
	LTPushBack(plist, 4);
	//LTPushBack(plist, 3);
	//LTPushBack(plist, 4);
	//LTPushBack(plist, 5);

	//测验头插
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	//LTNode* pos=LTFind(plist, 2);
	//if (pos == NULL)
//	printf("没有找到\n");
//else
//	printf("找到了\n");


	//在指定位置之后插入数据;
	//LTInsert(pos, 6);
	//在指定位置之前插入数据
	//LTInsertBefore(pos, 7);

	//删除指定位置数据
	//LTErase(pos);
	

	//测验尾删
	//LTPopBack(plist);
	//LTPopBack(plist);
	//LTPopBack(plist);
	//LTPopBack(plist);
	// 测验头删
	//LTPopFront(plist);
	//LTPopFront(plist);
	//LTPopFront(plist);
	//LTPopFront(plist);
	//LTPopFront(plist);
	 
	//LTDestroy(&plist);

	//保持接口一致性使用一级指针
	LTDestroy2(plist);//记得把plist置为NULL
	plist = NULL;
	Print(plist);
}
int main()
{
	ListTest01();
	return 0;
}

一. 双向链表的初始化与销毁

在进入正题之前，我们首先介绍一下上节提到的哨兵位。

哨兵位

我们在创建链表的时候首先需要做的自然是链表的初始化，可是空链表这种情况该怎么办呢？如果

通过开辟节点的方式再置为空，似乎又与“空”一字相悖。

定义

哨兵位就是针对这种情况而诞生，我们开辟一个节点，但是他并不参与数据的存储，而是像哨兵一

样，充当链表的先驱节点，极大方便了后续的种种操作。

创建节点

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;
}

分析：

1.与单链表的实现类似，我们定义一个专门用来创建节点的函数来进行每一次的动态开辟操作。

2.在该函数中，我们创建的节点，其next与prev指针均指向本身。

初始化

void LTInit(LTNode** pphead)
{
	//创建头结点(哨兵位)
	*pphead = LTBuyNode(-1);
}

分析：

1. 双向链表的头结点只是拿来保存第一个节点的地址的，不用来存储有效数据，双向链表为空的时候就是只有头结点，所以双向链表初始化就是申请一个头结点，并让plist指向头结点即可。

2.为了保持接口的一致性，我们最好采用一级指针的方式进行，通过函数的返回值即可访问到新节点。

LTNode* LTInit2()
{
	return LTBuyNode(-1);
}

打印

void Print(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d ", pcur->data);
		pcur = pcur->next;
	}//形成闭环
}

分析：

1.与单链表的直接遍历至尾节点不同，双向链表具有循环特性，各个节点依次连接形成闭环。

2.当节点向后遍历至最初的初始位置时，即代表刚好完整遍历一遍。

销毁

//销毁链表
void LTDestroy(LTNode** pphead)
{
	assert(pphead&&*pphead);
	LTNode* pcur, * next;
	pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//销毁头结点
	free(*pphead);
	*pphead = NULL;
	pcur = NULL;
}

分析：

1.与单链表类似，需要逐个释放

2.注意最后销毁哨兵位！否则会造成内存泄漏！

3.与初始化类似，为了保持接口一致性，我们采用一级指针进行销毁。

void LTDestroy2(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead=pcur = NULL;
}

注意：在主函数中调用该函数时，需要再手动把哨兵位置为空！

二. 双向链表的插入

核心：

1.创建新节点存储数据

2.修改创建位置处前后节点的next和prev指针

头插

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

尾插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

在指定位置之前插入数据

//在指定位置之前插入数据
void LTInsertBefore(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos;
	newnode->prev = pos->prev;
	pos->prev = newnode;
	newnode->prev->next = newnode;
}

在指定位置之后插入数据

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

三. 双向链表的删除

判空

删除的前提是链表内还有数据可以存储，因此如果链表内仅有一个哨兵位，即为空链表，此时不可

再进行删除。

//判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

头删

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

分析：

1. 在判空完成之后，首先定义一个指针del来指向将要删除的节点

2. 再修改删除节点下一个节点的前驱指针

3. 修改头节点的后驱指针

尾删

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	phead->prev = del->prev;
	del->prev->next = phead;
	free(del);
	del = NULL;

}

与头删同理。

在指定位置删除数据

//删除指定位置节点
void LTErase(LTNode* pos)
{
	LTNode* del = pos;
	del->prev->next = pos->next;
	del->next->prev = del->prev;
	free(pos);
	pos = 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;
}

分析：

1.直接遍历查找即可，注意循环条件

2.找到则返回节点地址，未找到则返回空

五. 顺序表与链表的比较

六. 完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
//打印链表
void Print(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d ", pcur->data);
		pcur = pcur->next;
	}
}

//申请新节点
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;
}


//初始化链表
void LTInit(LTNode** pphead)
{
	//创建头结点(哨兵位)
	*pphead = LTBuyNode(-1);
}


//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

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

//判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}


//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	phead->prev = del->prev;
	del->prev->next = phead;
	free(del);
	del = NULL;

}


//头删
void LTPopFront(LTNode* phead)
{
	assert(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;
}



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


//在指定位置之前插入数据
void LTInsertBefore(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos;
	newnode->prev = pos->prev;
	pos->prev = newnode;
	newnode->prev->next = newnode;
}

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


//销毁链表
void LTDestroy(LTNode** pphead)
{
	assert(pphead&&*pphead);
	LTNode* pcur, * next;
	pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//销毁头结点
	free(*pphead);
	*pphead = NULL;
	pcur = NULL;
}


void LTDestroy2(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead=pcur = NULL;
}


LTNode* LTInit2()
{
	return LTBuyNode(-1);
}

小结：本文主要介绍了双向链表的结构，概念，相关接口的具体实现方法和链表与顺序表的区别，

并简要介绍了哨兵位的含义与作用，欢迎各位大佬前来斧正支持！！！

相关文章