数据结构双向链表

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

数据结构双向链表,数据结构,链表,网络

Hello,好久不见,今天我们讲链表的双向链表,这是一个很厉害的链表,带头双向且循环,学了这个链表,你会发现顺序表的头插头删不再是一个麻烦问题,单链表的尾插尾删也变得简单起来了,那废话不多说,让我们开始我们的学习吧!

首先我们要了解它的物理和逻辑结构,那他们的样子是怎样的呢,首先是一个带头的,那这个难道是我们的哨兵位吗,又是双向,且循环,那让我们来画图了解它吧。

数据结构双向链表,数据结构,链表,网络

大致就是这样的一个形状,那我们现在需要这样的一个结构体来实现这样的功能,首先应该有一个存储数据的,就是data,然后就是得有两个指针,一个指向前面的节点,一个就是指向后面的节点,那我们就叫它们一个pre指向前面,一个next指向后面,我们来实现一下吧。

typedef int DListType;
typedef struct DList
{
	struct DList* pre;
	struct DList* next;
	DListType data;
	
}DLNode;

为了方便我们写后面的时候结构体方便一点,我们先定义结构体为DLNode,这样更加方便使用。

现在我们要实现下面的各种接口来完成双链表

首先最重要的就是怎么初始化
初始化的话我们先要想想这个接口函数改的参数和返回值
因为是双向链表,所以得有一个head的头节点,这样才能链接后面的内容

初始化双链表

DLNode* DListInit();

接口函数的名字
这里我们分析首先我们得返回值为什么不是void,而是DLNode*
因为我们要在这里面创建一个头节点,这个节点我们后面都得使用,其次还有一个原因就是这样头节点就不会被销毁,当然我们也可以在外面创建一个节点,然后我们在传它的指针进去,对结构体的内容进行修改,都可以达到相同的作用,废话不多说,我们来实现吧!

DLNode* DListInit()
{
	DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));
	assert(pHead);
	pHead->next = pHead;
	pHead->pre = pHead;
}

其实很简单,这里必须指针指向自己才可以,如果不这样的话,那我们的循环就不能实现了。
接下来就是怎么打印,打印很简单,我们将它这个指针传过去就行了。

打印双链表

void DListPrint(DLNode* pHead)
{
	assert(pHead);
	DLNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

打印函数的想法就是我们找head后面的那个节点,然后打印,因为头节点我们不打印,所以取cur开始,因为是循环,所以cur最后会等于pHead,这样的话就是一个循环,所以我们找下一个就行了,然后打印后更新cur。
接下来我们要创建一个节点,这样才能链接起来我们的节点。

DLNode* CreatNewNode(DListType x)
DLNode* CreatNewNode(DListType x)
{
	DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	newnode->pre = NULL;
	return newnode;
}

创造节点好了,接下来就是尾插一个节点进去,我们前面单链表尾插首先要找到尾的位置,然后再去尾插,同时要先找到尾的前一个位置,然后free尾,这样时间复杂度就是O(N),所以效率不是特别高,那我们现在因为head的位置里存放的就是尾的位置,所以不用进行查找了。我们现在来实现一下吧

双链表尾插

void DListPushBACK(DLNode* pHead, DListType x)
{
	assert(pHead);
	DLNode* newnode = CreatNewNode(x);
	DLNode* pre = pHead->pre;
	pHead->pre = newnode;
	newnode->next = pHead;
	pre->next = newnode;
	newnode->pre = pre;
}

其实尾插也很简单,我们这里先用一个指针保存位置,这样的话下一次插入就可以找到尾的位置,而且还不用注重顺序,这样大大的提升效率

有了尾插那就肯定有头插,一样的办法我们来实现一下

双链表的头插


void DListPushFront(DLNode* pHead, DListType x)
{
	assert(pHead);
	DLNode* newnode = CreatNewNode(x);
	DLNode* next = pHead->next;
	pHead->next = newnode;
	newnode->pre = pHead;
	newnode->next = next;
	next->pre = newnode;
}

有了头插这些,那肯定还有头删和尾删
那我们也来实现一下吧

尾删

void DListPopBack(DLNode* pHead)
{
	assert(pHead);
	if (pHead->next != pHead)
	{
		DLNode* del = pHead->pre;
		del->pre->next = pHead;
		pHead->pre = del->pre;
		free(del);
	}
}

前面写的代码都需要测试一下,我们先来测试三个

#include"DList.h"
void test()
{
	DLNode* head = DListInit();
	DListPushBack(head, 1);
	DListPushBack(head, 2);
	DListPushBack(head, 3);
	DListPushBack(head, 4);
	DListPrint(head);
	DListPushFront(head, 111);
	DListPushFront(head, 111);
	DListPushFront(head, 111);
	DListPrint(head);
	DListPopBack(head);
	DListPopBack(head);
	DListPopBack(head);
	DListPrint(head);
}
int main()
{
	test();
	return 0;
}

发现我们的程序没有问题,我们再来实现一下头删

void DListPopFront(DLNode* pHead)
{
	assert(pHead);
	if (pHead->next != pHead)
	{
		DLNode* del = pHead->next;
		pHead->next = del->next;
		del->next->pre = pHead;
		free(del);
	}
}

接下来就是双链表的查找,有了查找我们才能和在任意位置的删除和插入连用,那我们现在来实现一下吧


DLNode* DListFind(DLNode* pHead, DListType x)
{
	assert(pHead);
	DLNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

随机插入

void DListInsert(DLNode* pos, DListType x)
{
	assrt(pos);
	DLNode* newnode = CreatNewNode(x);
	DLNode* pospre = pos->pre;
	pospre->next = newnode;
	newnode->pre = pospre;
	newnode->next = pos;
	pos->pre = newnode;

}

也不是随机插入,是在pos位置之前插入,我们直接传pos和x就行,然后在根据之前的想法一步一步的进行插入链接就行

这里可以更新一下头插和尾插,这里就不演示了
那我们在写一个删除pos位置的函数

删除pos位置

void DListPop(DLNode* pos)
{
	assert(pos);
	DLNode* pospre = pos->pre;
	DLNode* posnext = pos->next;
	pospre->next = posnext;
	posnext->pre = pospre;
	free(pos);
}

还有一个destory我们开辟的空间,这个遍历一遍数组, 然后一个一个释放就行,但是会有问题,我们释放的时候必须看要机记住位置,可以从尾巴开始释放,用一个指针记住前面一个的位置,然后释放掉尾巴,然后更新前一个位置,用while控制一下就行了

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DListType;
typedef struct DList
{
	struct DList* pre;
	struct DList* next;
	DListType data;
	
}DLNode;

DLNode* DListInit();

void DListPrint(DLNode* pHead);

DLNode* CreatNewNode(DListType x);

void DListPushBack(DLNode* pHead, DListType x);

void DListPushFront(DLNode* pHead, DListType x);


void DListPopBack(DLNode* pHead);

void DListPopFront(DLNode* pHead);

DLNode* DListFind(DLNode* pHead, DListType x);

void DListInsert(DLNode* pos, DListType x);

void DListPop(DLNode* pos);
#include"DList.h"

DLNode* DListInit()
{
	DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));
	pHead->next = pHead;
	pHead->pre = pHead;
}

void DListPrint(DLNode* pHead)
{
	assert(pHead);
	DLNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

DLNode* CreatNewNode(DListType x)
{
	DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	newnode->pre = NULL;
	return newnode;
}


void DListPushBack(DLNode* pHead, DListType x)
{
	DLNode* newnode = CreatNewNode(x);
	DLNode* pre = pHead->pre;
	pHead->pre = newnode;
	newnode->next = pHead;
	pre->next = newnode;
	newnode->pre = pre;
}

void DListPushFront(DLNode* pHead, DListType x)
{
	DLNode* newnode = CreatNewNode(x);
	DLNode* next = pHead->next;
	pHead->next = newnode;
	newnode->pre = pHead;
	newnode->next = next;
	next->pre = newnode;
}

void DListPopBack(DLNode* pHead)
{
	assert(pHead);
	if (pHead->next != pHead)
	{
		DLNode* del = pHead->pre;
		del->pre->next = pHead;
		pHead->pre = del->pre;
		free(del);
	}
}

void DListPopFront(DLNode* pHead)
{
	assert(pHead);
	if (pHead->next != pHead)
	{
		DLNode* del = pHead->next;
		pHead->next = del->next;
		del->next->pre = pHead;
		free(del);
	}
}

DLNode* DListFind(DLNode* pHead, DListType x)
{
	assert(pHead);
	DLNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void DListInsert(DLNode* pos, DListType x)
{
	assrt(pos);
	DLNode* newnode = CreatNewNode(x);
	DLNode* pospre = pos->pre;
	pospre->next = newnode;
	newnode->pre = pospre;
	newnode->next = pos;
	pos->pre = newnode;

}


void DListPop(DLNode* pos)
{
	assert(pos);
	DLNode* pospre = pos->pre;
	DLNode* posnext = pos->next;
	pospre->next = posnext;
	posnext->pre = pospre;
	free(pos);
}

谢谢大家,我们下期再见文章来源地址https://www.toymoban.com/news/detail-675057.html

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

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

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构---双向链表

    单向链表:一块内存指向下一个内存。 单链表存在一些缺陷: 1.查找速度慢。 2.不能从后往前找。 3.找不到前驱。 链表的结构分为8种: 1.单向和双向 2.带头和不带头 带头的链表有一个带哨兵位的头结点,这个节点不存储有效数据。 好处 :尾插更方便,不需要二级指针了,

    2024年02月02日
    浏览(46)
  • 数据结构-双向链表

    在单链表那一篇博客中介绍了单链表和双向链表的优缺点,所以此篇博客直接分享怎样实现一个带头双向循环链表。 单链表博客: 首先我们需要写一个结构体,双向带头链表的话需要一个前驱指针prev和一个后驱指针next,前驱指针的作用是方便找尾节点,因为头节点的prev指

    2024年02月05日
    浏览(52)
  • 数据结构 - 双向链表

    文章目录 目录 文章目录 前言 一、什么是双向链表? 双向链表有什么优势? 二、双向链表的设计和实现 1.设计思想 尾增 : 在链表的末尾添加新的元素  头插 : 在链表头部插入节点  删除 : 根据val的值删除节点  查找 : 根据索引的值查找并返回节点 总结 大家好,今天给大家讲解

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

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

    2024年02月07日
    浏览(55)
  • 【数据结构】链表的分类和双向链表

    本篇是基于上篇单链表所作,推荐与上篇配合阅读,效果更加 http://t.csdnimg.cn/UhXEj 链表的结构非常多样,以下情况组合起来就有8种(2 x 2 x 2)链表结构: 我们一般叫这个头为哨兵位 我们上回讲的单链表就是不带头单项不循环链表。 今天我们要讲带头双向循环的链表。 不过

    2024年01月25日
    浏览(38)
  • 数据结构入门 — 链表详解_双向链表

    数据结构入门 — 双向链表详解 博客主页链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 文章末尾有源码 *****感谢观看,希望对你有所帮助***** 第一篇:数据结构入门 — 链表详解_单链表 第二篇:数据结构入门 — 链表详解_双向链表 第三篇:数据结构入门

    2024年02月11日
    浏览(47)
  • 数据结构:详解【链表】的实现(单向链表+双向链表)

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

    2024年03月26日
    浏览(65)
  • 【数据结构与算法】双向链表

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

    2024年02月11日
    浏览(56)
  • 【数据结构】‘双向链表’冲冲冲

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 我们的节点是双向循

    2024年02月13日
    浏览(41)
  • 数据结构与算法:双向链表

    朋友们大家好啊,在上节完成单链表的讲解后,我们本篇文章来对 带头循环双向链表进行讲解 单链表中,一个节点存储数据和指向下一个节点的指针,而双向链表除了上述两个内容,还包括了 指向上一个节点的指针 带头的双向链表,是指在双向链表的最前端添加了一个 额

    2024年02月20日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包