1. Toy模板网首页
  2. >Toy博客

【数据结构与算法】之双向链表及其实现！

1年前作者：秋风起，再归来～分类：Toy博客阅读(14)违法举报

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

【数据结构与算法】之双向链表及其实现！,数据结构与算法,链表,数据结构​

                                                                                个人主页：秋风起，再归来~

                                                                                            数据结构与算法                             

                                                                       个人格言：悟已往之不谏，知来者犹可追

                                                                                        克心守己，律己则安！

目录

1、双向链表的结构及概念

2、双向链表的实现

2.1 要实现的接口（List.h）

2.2 链表的初始化

2.3 链表的销毁

2.4 链表的打印

2.5 链表的尾插

2.6 链表的尾删

2.7 链表的头插

2.8 链表的头删

2.8 链表的查找

2.9 pos位置插入数据

2.10 pos位置删除数据

3、完整代码

List.h

List.c

Test.c（本人在实现双向链表时的测试代码） 

4、 完结散花

1、双向链表的结构及概念

我们这里要实现的数据结构是带头双向循环的链表（简称双向链表）

下面就是该链表的物理模型啦~

【数据结构与算法】之双向链表及其实现！,数据结构与算法,链表,数据结构​

2、双向链表的实现

2.1 要实现的接口（List.h）

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

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;//前驱指针
	LTDataType data;
	struct ListNode* next;//后驱指针
}LTNode;

//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
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);

//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x);

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

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

2.2 链表的初始化

注意：在初始化的时候一定要让头结点的prev指针和next指针都指向自己！

//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
LTNode* LTInit()
{
	//初始化时创建一个带哨兵卫的头结点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		perror("malloc fail!\n");
		return NULL;
	}
	phead->next = phead->prev = phead;
	phead->data = -1;
	return phead;
}

2.3 链表的销毁

注意：我们一定是从链表的头结点（头结点中并没有有效数据的存储）的下一个位置开始销毁链表的！

//链表销毁
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur=phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur!=phead)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
}

并且我们在调用链表的销毁函数后依然要手动释放动态内存开辟的phead头结点 ！

为尽量确保接口传递参数的一致性我们并没有传递头结点的地址，所以我们并不能在链表的销毁函数中free我们的头结点！

LTDestroy(plist);
//动态开辟的头结点需要手动释放
free(plist);
plist = NULL;

2.4 链表的打印

遍历链表打印头结点，循环结束的条件是pcur=phead，继续的条件是pcur！=phead

//链表的打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur != phead)
	{
		next = pcur->next;
		printf("%d->", pcur->data);
		pcur = next;
	}
	printf("\n");
}

2.5 链表的尾插

新节点的创建（单独封装成为一个函数）

//新节点的创建
LTNode* ListCreatNode(LTDataType x)
{
	LTNode* NewNode = (LTNode*)malloc(sizeof(LTNode));//开辟空间
	if (NewNode == NULL)//判断空间是否开辟成功
	{
		perror("malloc fail");
		return NULL;
	}
	NewNode->data = x;//赋值
	NewNode->next = NULL;//置空
	NewNode->prev = NULL;
	return NewNode;
}

链表的尾插 （在为尾插接口中直接调用创建节点的函数）

//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	LTNode* tail = phead->prev;
	newNode->prev = tail;
	newNode->next = phead;
	tail->next = newNode;
	phead->prev = newNode;
}

2.6 链表的尾删

注意各个节点的指向！

//链表的尾删
void LTPopBack(LTNode* phead)
{
	//尾删的前提是双向链表不为空
	assert(phead && phead->next != phead);
	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next=phead;
	free(tail);
	tail = NULL;
}

2.7 链表的头插

//链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	newNode->next = phead->next;
	newNode->prev = phead;
	phead->next->prev = newNode;
	phead->next = newNode;
}

2.8 链表的头删

//链表的头删
void LTPopFront(LTNode* phead)
{
	//头删的前提是双向链表不为空
	assert(phead && phead->next != phead);
	LTNode* start = phead->next;
	phead->next = start->next;
	start->next->prev = phead;
	free(start);
	start= NULL;
}

2.8 链表的查找

返回值是该指向该数据节点的结构体指针，如没有找到，直接返回空！

//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		next = pcur->next;
		pcur = next;
	}
	return NULL;
}

2.9 pos位置插入数据

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	newNode->next = pos->next;
	newNode->prev = pos;
	pos->next->prev = newNode;
	pos->next = newNode;
}

2.10 pos位置删除数据

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

3、完整代码

List.h

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

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;//前驱指针
	LTDataType data;
	struct ListNode* next;//后驱指针
}LTNode;

//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
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);

//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x);

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

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

List.c

#include"List.h"

//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
LTNode* LTInit()
{
	//初始化时创建一个带哨兵卫的头结点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		perror("malloc fail!\n");
		return NULL;
	}
	phead->next = phead->prev = phead;
	phead->data = -1;
	return phead;
}

//链表销毁
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur=phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur!=phead)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
}

//链表的打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur != phead)
	{
		next = pcur->next;
		printf("%d->", pcur->data);
		pcur = next;
	}
	printf("\n");
}

//新节点的创建
LTNode* ListCreatNode(LTDataType x)
{
	LTNode* NewNode = (LTNode*)malloc(sizeof(LTNode));//开辟空间
	if (NewNode == NULL)//判断空间是否开辟成功
	{
		perror("malloc fail");
		return NULL;
	}
	NewNode->data = x;//赋值
	NewNode->next = NULL;//置空
	NewNode->prev = NULL;
	return NewNode;
}

//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	LTNode* tail = phead->prev;
	newNode->prev = tail;
	newNode->next = phead;
	tail->next = newNode;
	phead->prev = newNode;
}

//链表的尾删
void LTPopBack(LTNode* phead)
{
	//尾删的前提是双向链表不为空
	assert(phead && phead->next != phead);
	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next=phead;
	free(tail);
	tail = NULL;
}

//链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newNode = ListCreatNode(x);//先创建一个新节点
	newNode->next = phead->next;
	newNode->prev = phead;
	phead->next->prev = newNode;
	phead->next = newNode;
}

//链表的头删
void LTPopFront(LTNode* phead)
{
	//头删的前提是双向链表不为空
	assert(phead && phead->next != phead);
	LTNode* start = phead->next;
	phead->next = start->next;
	start->next->prev = phead;
	free(start);
	start= NULL;
}

//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode* next = NULL;
	//结束条件是当pcur不等于篇phead
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		next = pcur->next;
		pcur = next;
	}
	return NULL;
}

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

Test.c（本人在实现双向链表时的测试代码） 

#define _CRT_SECURE_NO_WARNINGS

#include"LIst.h"

void TestList1()
{
	LTNode* plist;
	plist = LTInit();//初始化链表
	LTPushBack(plist,1);
	LTPushBack(plist,2);
	LTPushBack(plist,3);
	LTPushFront(plist, 4);
	LTPushFront(plist, 4);
	/*LTPopFront(plist);
	LTPopFront(plist);*/
	LTNode* pos=LTFind(plist, 2);
	printf("删除pos位置之前\n");
	LTPrint(plist);
	LTErase(pos);
	printf("删除pos位置之后\n");
	LTPrint(plist);
	//LTInsert(pos, 5);
	//LTPopBack(plist);
	//LTPopBack(plist);
	//LTPopBack(plist);
	LTDestroy(plist);
	//动态开辟的头结点需要手动释放
	free(plist);
	plist = NULL;
}

int main()
{
	TestList1();

	return 0;
}

4、 完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~

【数据结构与算法】之双向链表及其实现！,数据结构与算法,链表,数据结构​【数据结构与算法】之双向链表及其实现！,数据结构与算法,链表,数据结构​文章来源地址https://www.toymoban.com/news/detail-855915.html

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包赞助服务器费用

相关文章

  • 【数据结构与算法】双向链表

    【数据结构与算法】双向链表

    作者：旧梦拾遗186 专栏：数据结构成长日记   带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。 现在我们来通

    2024年02月11日
    浏览(14)
  • 数据结构与算法（四）：双向链表

    数据结构与算法（四）：双向链表

    双向链表概念和单向链表是一致的，区别在于双向链表在单向链表的基础上，指针区域多了一个指向上一个节点的指针。单向链表内容可以参考我的上一篇文章：http://t.csdn.cn/Iu56H。 基本的数据结构如图所示： 双向链表结构包含了节点的数据内容和两个指针：指向前一个节点

    2024年02月14日
    浏览(11)
  • 数据结构——实现双向链表

    数据结构——实现双向链表

    怎么说呢？光乍一听名字好像很难的样子是吧，那如果你这样认为的话，可就要让你大跌眼镜了哦，其实双向带头循环链表从操作和理解上来说都是要易于单项不带头不循环链表（俗称单链表）的。 咱们就来见识见识吧！希望真的能让你们“大跌眼镜”哈！ 双向带头循环链

    2024年02月07日
    浏览(10)
  • 数据结构：详解【链表】的实现（单向链表+双向链表）

    数据结构：详解【链表】的实现（单向链表+双向链表）

    1.顺序表的问题和思考 问题： 中间/头部的插入删除，时间复杂度为O(N)。 增容需要申请新空间，拷贝数据，释放旧空间,会有不小的消耗。 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据

    2024年03月26日
    浏览(10)
  • 【（数据结构）— 双向链表的实现】

    【（数据结构）— 双向链表的实现】

    注意： 这里的 “带头” 跟前面我们说的 “头节点” 是两个概念，实际前面的在单链表阶段称呼不严 谨，但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表里的头节点，实际为 “哨兵位” ，哨兵位节点不存储任何有效元素，只是站在这里“放哨 的” “哨

    2024年02月06日
    浏览(13)
  • 【数据结构】双向链表的实现

    【数据结构】双向链表的实现

    我要扼住命运的咽喉，他却不能使我完全屈服。                      --贝多芬 目录 一.带头循环的双向链表的特点 二.不带头不循环单向链表和带头循环的双向链表的对比 三.初始化链表，创建哨兵结点 四.双向链表的各种功能的实现 1.双向链表的尾插 2.双向链表的打印 

    2023年04月10日
    浏览(9)
  • 数据结构——双向链表的实现

    数据结构——双向链表的实现

    注意： 双向链表又称带头双向循环链表 这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严 谨，但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表⾥的头节点，实际为“ 哨兵位 ”，哨兵位节点不存储任何有效元素，只

    2024年02月06日
    浏览(13)
  • 双向链表--C语言实现数据结构

    双向链表--C语言实现数据结构

    本期带大家一起用C语言实现双向链表🌈🌈🌈 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；简单来说，线性表的链式存储结构生成的表，称作“链表”。 每个元素本身由两部分组成： 1、本身的信息，称

    2024年02月04日
    浏览(23)
  • 数据结构双向链表，实现增删改查

    数据结构双向链表，实现增删改查

            在单链表中，查找直接后继结点的执行时间为O(1)，而查找直接前驱的执行时间为O(n)。为克服单链表这种单向性的缺点，可以用 双向链表 。         在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱。 2.1 双向链表结点创建 2.2 双向链表

    2024年02月16日
    浏览(6)
  • 【数据结构】带头双向循环链表及其实现

    【数据结构】带头双向循环链表及其实现

    目录 1.带头双向循环链表 2.带头双向循环链表实现 2.1初始化 2.2销毁 2.3头插 2.4链表打印 2.5头删数据 2.6尾插数据 2.7尾删数据 2.8链表判空  2.9查找一个数据 2.10在pos位置前插入数据 2.11删除pos位置 2.12求链表的长度 2.顺序表和链表的比较 我们已经实现了无头单向循环链表 带头双

    2024年02月10日
    浏览(12)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包