双向链表（带头双向循环链表）的实现

发布于：2024-04-26 ⋅ 阅读:(20) ⋅ 点赞:(0)

前言：前面实现的单向链表，全称是不带头单向不循环链表。这里实现带头双向不循环链表，比单向链表好实现一点。

目录

链表的分类

单向链表与双向链表的比较：

 双向链表的节点的定义：

多文件实现：

List.h来看一下需要实现的函数接口：

List.c的各个函数的实现：

创建节点的函数：

链表的初始化：

尾插：

头插：

打印链表：

尾删： 

头删：

查找

插入（在指定位置之后插入）：

删除指定位置的数据：

销毁链表：

实现双链表的全部源码：

List.h：

List.c：

test.c的主要功能是测试个接口，所以这里的代码仅供参考哦！

结语：

链表的分类

将是否带头，单向还是双向，是否循环，随机组合一共有八种类型，只要会写不带头单向不循环链表和带头双向循环链表这两个链表，其他的链表实现起来就简单多了。

单向链表与双向链表的比较：

单向链表 双向链表
是否带头 不带头 带头（有哨兵位）
单向还是双向 单向 双向
是否循环 不循环 循环

逻辑图解比较：

 双向链表的节点的定义：

typedef int LTTypeData;
typedef struct ListNode
{
	LTTypeData data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

prev指向前一个节点

next指向下一个节点

data存储数据

为什么tydef一个新的数据类型是为了方便以后修改存储的数据类型。

多文件实现：

文件名称 负责的功能
List.h 链表的定义，需要用到库里的头文件的包含，链表需要实现函数的声明。
List.c 链表函数的实现
test.c 测试接口（这里大家可以自己测，自己写）

这里的建议是每写一个接口就测试一个接口，省得全写完在测试，有一堆麻烦，还没开始解决麻烦，就先把自己的心态搞崩了。

List.h来看一下需要实现的函数接口：

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

typedef int LTTypeData;
typedef struct ListNode
{
	LTTypeData data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//初始化链表
void LTInite(LTNode** pphead);
//尾插
void LTPushBack(LTNode* phead, LTTypeData x);
//头插
void LTPushFront(LTNode* phead, LTTypeData x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//打印链表中的数据
void LTPrint(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTTypeData x);
//在指定位置之后插入
void LTInsert(LTNode* pos, LTTypeData x);
//删除指定位置的数据
void LTErase(LTNode* pos);
//销毁链表
void LTDestroy(LTNode* phead);

List.c的各个函数的实现：

因为会频繁的创建新的节点，这里直接将创建新的节点分装成一个函数。

创建节点的函数：

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

注意这里创建出的节点的next和prev指针都指向自己。

图解：

链表的初始化：

void LTInite(LTNode** pphead)
{
	assert(pphead);//链表不能无效
	*pphead = LTBuyNode(-1);
}

这里*pphead指向的节点为头结点（哨兵位），哨兵位的数据为无用的数据。

尾插：

void LTPushBack(LTNode* phead, LTTypeData 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的prev和next，再改原链表的尾节点的next（指向新的节点）和头节点的prev（指向新的节点）

 图解：

注意这里2和3不能调换顺序，如果调换顺序，那么prev->next就找不到原来链表的尾节点了。

头插：

void LTPushFront(LTNode* phead, LTTypeData x)
{
	assert(phead);//防止链表无效
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

 注意：还是顺序问题：最后两句不能调换顺序，否则，phead->next就指向的不是原链表的第一个节点，就找不到原链表的第一个节点了。

打印链表：

void LTPrint(LTNode* phead)
{
	assert(phead);//防止链表无效
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

这里注意循环结束的标志：

当pcur指向哨兵位时，循环结束。

看一下打印效果：

#include "List.h"
void test1()
{
	LTNode* plist = NULL;
	LTInite(&plist);
	LTPushBack(plist, 1);
	LTPrint(plist);
	LTPushBack(plist, 2);
	LTPrint(plist);
	LTPushBack(plist, 3);
	LTPrint(plist);
	LTPushFront(plist, 4);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
}
int main()
{
	test1();
}

效果展示： 

尾删： 

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

这里需要修改的链表的地方：尾节点的前一个节点的next和头节点的prev

步骤图解：

注意：这里需要保存下尾节点的地址，防止到最后释放的时候找不到。

头删：

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

 跟尾删一样，需要注意的一点就是，需要创建一个新的变量（del）存储需要删除的节点的地址。

查找：

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

注意下循环结束的条件：跟上面的打印函数一样，需要遍历一遍链表。

返回值：如果没找到返回NULL，找到了就返回那个节点的地址。

插入（在指定位置之后插入）：

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

注意：最后两句的顺序不能交换。这里的原因上面的头插尾插的原因一样，若交换就找不到pos指向的节点的下一个节点。

删除指定位置的数据：

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

这里没啥好注意的 。

销毁链表：

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

注意：这里用到前后指针：防止释放完一个节点找不到之后的节点。

最后哨兵位释放，因为这里传的是一级指针不会修改test.c 文件中的phead的值，所以调用完该函数后，需要手动的将test.c中的phNULL.

那么,这里为什么不传二级指针呢？

保证接口的一致性，所以传的二级指针。

实现双链表的全部源码：

List.h：

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

typedef int LTTypeData;
typedef struct ListNode
{
	LTTypeData data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//初始化链表
void LTInite(LTNode** pphead);
//尾插
void LTPushBack(LTNode* phead, LTTypeData x);
//头插
void LTPushFront(LTNode* phead, LTTypeData x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//打印链表中的数据
void LTPrint(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTTypeData x);
//在指定位置之后插入
void LTInsert(LTNode* pos, LTTypeData x);
//删除指定位置的数据
void LTErase(LTNode* pos);
//销毁链表
void LTDestroy(LTNode* phead);

List.c：

#include "List.h"


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

void LTPushBack(LTNode* phead, LTTypeData x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->prev = phead->prev;
	newnode->next = phead;

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

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


void LTPushFront(LTNode* phead, LTTypeData x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}



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


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


LTNode* LTFind(LTNode* phead, LTTypeData 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, LTTypeData x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	
	pos->next->prev = newnode;
	pos->next = newnode;
}


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


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

test.c的主要功能是测试个接口，所以这里的代码仅供参考哦！

#include "List.h"
void test1()
{
	LTNode* plist = NULL;
	LTInite(&plist);
	LTPushBack(plist, 1);
	LTPrint(plist);
	LTPushBack(plist, 2);
	LTPrint(plist);
	LTPushBack(plist, 3);
	LTPrint(plist);
	LTPushFront(plist, 4);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTNode* find = LTFind(plist, 4);
	//if (find == NULL)
	//	printf("没找到\n");
	//else
	//	printf("找到了\n");
	//LTInsert(find, 5);
	//LTPrint(plist);
	//LTErase(find);
	//LTPrint(plist);
	//LTDestroy(plist);
	//plist = NULL;
}
int main()
{
	test1();
	return 0;
}

结语：

继单链表后的又一个数据结构的实现。

cheers！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布