数据结构【链表】看完还怕拿不下链表?

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

数据结构【链表】看完还怕拿不下链表?

✨Blog:🥰不会敲代码的小张:)🥰
🉑推荐专栏:C语言🤪、Cpp😶‍🌫️、数据结构初阶💀
💽座右铭:“記住,每一天都是一個新的開始😁😁😁

前言

上一章节:无头单向非循环链表

具体链表介绍内容请见上一章节
本章节主要介绍双向链表以及带头节点和循环的概念和实现,并且本章是在上一章节的基础上加以改造,虽然结构复杂了点,但是要比单链表更好实现🤪

双链表介绍

数据结构【链表】看完还怕拿不下链表?
从上面的图中我们可以看到,每一个节点都会有一个指针指向前一个和后一个,然后头节点指向最后一个节点,最后一个节点指向头节点,这就是带头双向循环链表。
那为什么会有单链表和双链表之分呢?
在单链表删除或者查询一个元素时,我们只能单向读取,然后如果删除的话,我们要保存前一个节点,为克服单链表的单向性,可以使用双链表更好的解决此问题。
头结点是为了操作的统一与方便而设立的,放在第一个元素结点之前,其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等等)

链表的创建

prev指针指向前一个,next指针指向后一个

typedef int LDataType;
typedef struct ListNode
{
	LDataType data;
	struct ListNode* prev;
	struct ListNode* next;

}ListNode;

创建新节点

//创建新的节点
ListNode* BuyListNode(LDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("BuyListNode");
		return NULL;
	}
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;

	return newnode;
}

初始化头节点

最开始的头节点前后指针都指向自己,如果有元素插入进来再更改指针指向的位置
数据结构【链表】看完还怕拿不下链表?

//初始化头节点
ListNode* LsitInit()
{
	ListNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

销毁链表结点

把头节点的后一个的节点给cur指针,也就是第一个节点的位置
cur指针指向头节点的时候,以及遍历完了链表,所以循环不再进去
然后保留cur的下一个节点,free掉cur,再把next给cur,继续向后走
数据结构【链表】看完还怕拿不下链表?

//销毁节点
void ListDestroy(ListNode* phead)
{
	assert(phead);//断言phead不能为空
	ListNode* cur = phead->next;//头节点的下一个才是第一个元素
	while (cur != phead)//cur的next不能等于头节点
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

打印链表

//打印节点数据
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;

	printf("head<=>");

	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

判断链表是否为空

如果头节点的next指针指向自己,说明链表为空

bool ListEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

尾插

只需要更改指针关系,找到最后一个节点的位置,在尾部链接要插入的节点,把新插入的节点前指针和后指针链接到对应的位置即可
数据结构【链表】看完还怕拿不下链表?

//尾插
void ListPushback(ListNode* phead, LDataType x)
{
	assert(phead);

	ListNode* newnode = BuyListNode(x);
	ListNode* tail = phead->prev;

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

尾删

找到最后一个节点tail,保留tail的前一个tailprev
把tailprev的next指向头节点,头节点的prev指向tailprev
数据结构【链表】看完还怕拿不下链表?

//尾删
void ListPopback(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	ListNode* tail = phead->prev;
	ListNode* tailprev = tail->prev;
	
	tailprev->next = phead;
	phead->prev = tailprev;
	free(tail);
	tail = NULL;
}

头插

更改指针关系的时候一定要注意先后顺序,不然一旦指针更改可能就会链接到错误的地方
数据结构【链表】看完还怕拿不下链表?

void ListPushFront(ListNode* phead, LDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	
	newnode->next = phead->next;
	phead->next->prev = newnode;
	newnode->prev = phead;
	phead->next = newnode;

	//ListInsert(phead->next, x);
}

头删

注意:只要是删除链表节点,就要判断链表是否为空,如果为空就直接报错
tail指针指向第一个节点,让头节点指针指向tail的next
tail的next的prev指向头节点
最后free掉tail指向的节点
数据结构【链表】看完还怕拿不下链表?

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	ListNode* tail = phead->next;
	phead->next = tail->next;
	tail->next->prev = phead;
	free(tail);
	tail = NULL;

	//ListErase(phead->next);

}

在pos的前一个位置插入

注:pos要配合着查找函数一起使用,比如查找6,找到之后返回6的地址给指针。
记录pos前一个的节点,然后再更改指针之间的关系
数据结构【链表】看完还怕拿不下链表?

//在pos的前一个位置插入
void ListInsert(ListNode* pos, LDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);
	ListNode* prev = pos->prev;

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

删除pos位置节点

数据结构【链表】看完还怕拿不下链表?

//删除pos位置节点
void ListErase(ListNode* pos)
{
	assert(pos);
	assert(!ListEmpty(pos));

	ListNode* prev = pos->prev;

	prev->next = pos->next;
	pos->next->prev = prev;
	free(pos);
	pos = NULL;
}

查找

定义一个cur指针指向第一个节点,如果cur的data和要查找的值一样就返回cur,如果不想等就让cur向后走,直到cur走到头节点循环结束。

//查找
ListNode* ListFind(ListNode* phead, LDataType x)
{
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data != x)
			cur = cur->next;
		else
			return cur;
	}
	return NULL;
}

创作不易,记得三连!笔者水平有限,如有错误的地方,还望指出,谢谢大家😋😋😋文章来源地址https://www.toymoban.com/news/detail-460770.html

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

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

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

相关文章

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

    双向链表也叫双链表,与单向链表不同的是,每一个节点有三个区域组成:两个指针域,一个数据域 前一个指针域:存储前驱节点的内存地址 后一个指针域:存储后继节点的内存地址 数据域:存储节点数据 以下就是双向链表的最基本单位 节点的前指针域指向前驱,后指针

    2024年02月04日
    浏览(44)
  • <数据结构> 链表 - 链表的概念及结构

    概念: 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 1、链表由一系列结点(链表中每一个元素称为结点)组成。 2、结点可以在运行时动态(malloc)生成。 3、每个结点包括两个部分:一个是存储数据元素的

    2023年04月09日
    浏览(44)
  • 【数据结构-链表-01】反转链表

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月10日
    浏览(43)
  • 全面深入了解接口自动化,看完还不会我报地址

    (1)接口自动化 python/java+requests+unittest框架来实现 python/java+RF(RobotFramework)框架来实现——对于编程要求不高 (2)Web UI功能自动化 python/java+selenium+unittest+ddt+PO框架来实现 python/java+RFS(RobotFrameWork+Selenium)框架来实现——对于编程要求不高 (3)App自动化 python/java+appnium+u

    2023年04月14日
    浏览(36)
  • 数据结构——线性数据结构(数组,链表,栈,队列)

    数组(Array) 是一种很常见的数据结构。它由相同类型的元素(element)组成,并且是使用一块连续的内存来存储。 我们直接可以利用元素的索引(index)可以计算出该元素对应的存储地址。 数组的特点是: 提供随机访问 并且容量有限。 2.1. 链表简介 链表(LinkedList) 虽然是

    2024年02月11日
    浏览(41)
  • 【数据结构】链表的回文结构

    单链表的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _ 😀 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针

    2024年02月12日
    浏览(53)
  • 【数据结构】详解链表结构

    上篇博客已经介绍了顺序表的实现:【数据结构】详解顺序表。最后在里面也谈及了顺序表结构的缺陷,即 效率低,空间浪费 等等问题,那么为了解决这些问题,于是乎我们引入了链表的概念,下面将对链表结构进行讲解 首先肯定会问,到底什么是链表? 链表的概念 : 链

    2024年02月05日
    浏览(43)
  • 【数据结构】浅谈数据结构-链表【思路+例题学习】

    🏆今日学习目标: 🍀学习算法-数据结构-链表 ✅创作者:贤鱼 ⏰预计时间:30分钟 🎉个人主页:贤鱼的个人主页 🔥专栏系列:算法 🍁贤鱼的个人社区,欢迎你的加入 贤鱼摆烂团 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中

    2024年01月21日
    浏览(43)
  • 【数据结构】每天五分钟,快速入门数据结构(二)——链表

    目录 一 构建一个单向链表 二 特点 三 时间复杂度 四 相关算法 1.判断链表是否成环及成环位置 2.链表反转 五 Java中的LinkedList 类 1.使用 2.LinkedList 方法 长度无限 适合任意位置插入和删除频繁的场景 物理上可以不连续 访问、插入、删除 的时间复杂度均为O(n) 在头部插入元素

    2024年02月21日
    浏览(45)
  • 【后端那些事儿】Redis设计与实现(一) 数据结构,耐心看完你比Redis还懂Redis!

    本文章主要为了帮助读者认识Redis的数据结构,并深入了解Redis的数据结构,创作不易,希望得到大家的点赞、收藏、关注!谢谢! 1.1简单动态字符串(SDS)的定义 Redis的简单动态字符串(Simple Dynamic String,SDS)是Redis内部使用的字符串表示方式。SDS是一种可以自动扩展长度的字

    2024年01月22日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包