数据结构——链表详解

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

链表

前言

new一个奶黄包:没关系,这条路我陪你走到底

数据结构——链表详解,数据结构,链表,数据结构,c++,算法

认识链表

单链表结构图

数据结构——链表详解,数据结构,链表,数据结构,c++,算法

带头单循环链表结构图

数据结构——链表详解,数据结构,链表,数据结构,c++,算法

双向循环链表结构图

数据结构——链表详解,数据结构,链表,数据结构,c++,算法

带头双向循环链表结构图

数据结构——链表详解,数据结构,链表,数据结构,c++,算法

链表特点

  • 单链表在内存中,并不是连续存储的(逻辑上连续)。

  • 不支持随机访问

  • 插入时只需要改变指针指向

  • 没有容量的概念

  • 可以高效的在任意位置插入&&删除

  • 缓存利用率低

链表实现(带头双向循环链表实现)

链表结构体
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
(1) 新建头节点
LTNode* ListInit()//建立头节点
{
	LTNode* phead = buyListNode(-1); //建立一个带头节点
	phead->next = phead;      
	phead->prev = phead;

	return phead;
}
(2) 建立新节点
LTNode* buyListNode(LTDataType x)//创建内存初始化数据  
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	// 初始化:注意所对的结构来初始化
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}

(3)尾部插入节点
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyListNode(x);
	LTNode* tail = phead->prev;
  
	tail->next = newnode;
	newnode->prev = tail;

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

数据结构——链表详解,数据结构,链表,数据结构,c++,算法

(4)删除节点
void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;  //记录上一个节点
	LTNode* tailmove =tail->prev;  //记录上一个节点的上一个节点
  
	tailmove->next = phead;    
	phead->prev = tailmove;
  
	free(tail);
}

数据结构——链表详解,数据结构,链表,数据结构,c++,算法

(5)头部插入节点
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyListNode(x); 
	LTNode* first = phead->next;

	newnode->next = first;
	first->prev = newnode;

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

数据结构——链表详解,数据结构,链表,数据结构,c++,算法

(6) 头删节点
void LTPopFront(LTNode* phead)
{
	assert(phead);  //判断是否有头节点
	assert(phead->next != NULL);  //判断第一个节点是否存在
	LTNode* tail = phead->next;
	LTNode* tailmove = tail->next;

	tailmove->prev = phead;
	phead->next = tailmove;

	tailmove->next = phead;
	phead->prev = tailmove;
	free(tail);
}

数据结构——链表详解,数据结构,链表,数据结构,c++,算法

(7) 寻找节点
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			//printf("找到了");
			return cur;//返回指针
		}
      cur=cur->next; //每次都走到下一个节点直到phead
	}
	//printf("找不到");
	return NULL;
}
(8) pos位置插入节点
void LTInsert(LTNode* pos, LTDataType x)//头插尾插都可以调用这个函数 
{
	assert(pos);
	LTNode* newnode = buyListNode(x); //新建一个节点
	LTNode* prev = pos->prev;   //记录pos位置的前一个节点

	newnode->next = pos;   //新节点的下一个节点就是pos
	pos->prev = newnode;   //pos位置节点prve就链接后面

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

数据结构——链表详解,数据结构,链表,数据结构,c++,算法

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

	prve->next = next;
	next->prev = prve;

	free(pos);
}

数据结构——链表详解,数据结构,链表,数据结构,c++,算法文章来源地址https://www.toymoban.com/news/detail-655496.html

(10) 打印链表
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
  
	while (cur!= phead)
	{
		printf("-> %d ",cur->data );
		cur = cur->next;
	}
  
}
测试用例
void test1()
{
	LTNode* ptail = ListInit();
	LTPushBack(ptail, 1);
	LTPushBack(ptail, 3);
	LTPushBack(ptail, 2);
	LTPushBack(ptail, 4);
	LTPushBack(ptail, 5);
	LTPopBack(ptail);
	LTPrint(ptail);
}

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

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

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

相关文章

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

    链表是由一串节点串联在一起的,链表的每个节点存储两个信息:数据+下一个节点的地址 分清楚两个概念:什么是内存内部,什么是程序内部 内存内部: 信息存储在内存空间里的 程序内部: 通过什么信息,去操作结构 如果想操作链表的话,我们依靠的是程序内部的信息,

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

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 在前面我们已经学习过了有关顺序表的知识,但是我们知道顺序表是存在着一些问题的 问题: 中间/头部的插入删除,时间复杂度

    2024年02月03日
    浏览(41)
  • 数据结构——链表详解

    new一个奶黄包:没关系,这条路我陪你走到底 单链表结构图 带头单循环链表结构图 双向循环链表结构图 带头双向循环链表结构图 链表特点 单链表在内存中,并不是连续存储的(逻辑上连续)。 不支持随机访问 插入时只需要改变指针指向 没有容量的概念 可以高效的在任意

    2024年02月12日
    浏览(36)
  • [数据结构]——链表详解

    1.什么是链表?链表的概念及结构 链表是一种 物理存储结构上非连续、非顺序 的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的。 注意: 1.链式结构在逻辑上是连续的,但在物理上不一定连续 2.现实中的结点一般都是从堆上申请出来的 3.从堆上申请的

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

    我们不废话,直入正题。 什么是链表? 来看看百度怎么说: 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包

    2023年04月19日
    浏览(42)
  • 02-链表 (数据结构和算法)

    3.1 链表的基本概念 前面我们在学习顺序表时,线性表的顺序存储结构的特点是逻辑关系上相邻的两个数据元素在物理位置上也是相邻的。我们会发现虽然顺序表的查询很快,时间复杂度为O(1),但是增删的效率是比较低的,因为每一次增删操作都伴随着大量的数据元素移动。为

    2024年02月16日
    浏览(46)
  • Python数据结构与算法-数据结构(列表、栈、队列、链表)

    数据结构是指相互之间存在这一种或者多种关系的数据元素的集合和该集合中元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。 N.Wirth:“程序=数据结构+算法” 数据结构按照其 逻辑结

    2024年02月08日
    浏览(58)
  • 数据结构入门 — 链表详解_双向链表

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

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

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

    2024年03月26日
    浏览(65)
  • 【数据结构和算法】奇偶链表

    Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1 方法一:分离节点后合并 三、代码 3.1 方法一:分离节点后合并 四、复杂度分析 4.1 方法一:分离节点后合并 这是力扣的 328 题,难

    2024年01月20日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包