数据结构和算法-单链表的基本介绍|学习笔记

简介: 快速学习数据结构和算法-单链表的基本介绍

开发者学堂课程【Go 语言核心编程 - 数据结构和算法:数据结构和算法-单链表的基本介绍】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/627/detail/9835


数据结构和算法-单链表的基本介绍


 容简介:

一、链表的介绍

二、单链表的介绍

三、小结


一、链表的介绍

(1)前言

上一节讲了用数组来模拟一个环形的队列,它的核心思想就是指针或者标识元素的下标,在到达队尾的时候,它可以通过取模的方式,又重新回到这个数组的前面,这是核心思想。下面来看另外一种数据结构,这个数据结构是非常有用的,为什么说这个数据结构更有用?或者更有意思?

因为这个链表,它可以实现前面的队列在前面讲 redit 的时候,曾经有一个数据结构叫 list ,那个 list 底层可以用数组实现,也可用链表实现,它这个就很灵活了。数据结构可以做很多好玩的东西出来

(2)链表的基本介绍及示意图

首先链表是什么,链表是有序的一个列表。它在内存中的存储是如下图所示:

image.png

有头指针,指向了后面的各个结点结点之间是可以这样互相指,对于我们来说,感觉并不是完全连续的,这个很正常,因为它下面地址的分布其实还是由系统来决定的,这个并不影响因为认为都是有序的就行,这是它一个基本的说明。


二、单链表的介绍

(1)单链表(带头结点)逻辑示意图

单链表(带头结点)逻辑示意图如下所示:

image.png

最左边是一个 head 结点先指向一个头结点头结点里面有一个字段这个字段又指向另外一个节点另外一个节点里面又有一个字段,它又向指向另外节点

(2)经典案例示意图介绍

一个示意图最经典的案例,如下:

image.png

有一个头结点 head 的节点它指向了一个头结点比如说这是第一个结点,那这个结点里面是什么内容?比如是一个人,Person ,假设它有个字段名字叫 tom ,另外它有一个叫 next 是一个什么类型?

姑且认为它是一个 next[ *Person] 的类型,假定左上角节点它的结构体是 type people struct ,它里面首先有它自己的信息,比如 name string ,另外一个最重要的信息就是 next 的指针,即 next[ *Person] ,假设还有一结点 jack假设还有一个结点 Scott ,再来一个头结点,头结点没有具体的数据,只专门用来做头结点,里面的内容可以不给任何东西,然后形成一个结构,可以看到它的头结点指向地方然后下边地方继续指向的下一个结点,以此类推,于是这样它就形成了一个链表的结构,那么链表它形成的意义有什么用?

可以想象在现实生活中就会存在这样类似的结构,比如小朋友围成一圈丢手帕,就可以形成一个环状的,怎么样一个环状呢?

既可以再重新回来不要再重新指向这个头结点这样就是一个环状,那如果不想做环状的列表,它本身其实看起来也像是一个队列也就可以当一个队列来使用它更有意思的是,它可以在内存里面形成一些非常有用的结构,

比如下图:

image.png

比如上图是有一组人,那么可以让多人形成一个哈希,到时候在帮某一组人的时候,通过一个里面有另外一个结构,可以很轻松的通过这个结点来找到主人所以说这个非常有用的,上图是它的一个示意图

(3)改进的链表示意图

那么我这个图,画的有一点点不准确,这个图如果在 Java 或者 C++ 里面,它是一个很精准的图,但是放在 Go 语言里面,有点不准确,哪一点不准确?

就是因为都非常清楚的知道,在 Go 语言里面这个结构体它本身是一个指针类型所以  next 这个指针准确的讲,并没有直接指向下一个结构体,它其实直接指向的是一个地址以前讲过,它是指针的话是先指向一个地址指向真正的结构体,也就是说标准的画法应该是如下图所示:

 image.png

有时候这样画的很麻烦,看起来不舒服,所以说在讲课的时候,可能把中间这个地址就不了,这个就是一个链表的一个最基本的结构。

(4)链表的增删改查

来完成对链表的增删改查通过练习,就能知道链表它是怎么用的,可以这样理解可以利用链表来做一个属于自己的内存数据库就是有些时候我们往往把数据直接放在数据库里面,但是是人家的东西有些时候想自己去存放一个数据量比较大的数据数量比较大而且还要让具有很好的扩展性,比如还在内存里面存放数据,有增删改查的功能,这个时候链表加上哈希,即链表配合哈希的算法,就是非常不错的一种机构

所以这就是为什么后边再讲的有一个闪列,闪列加上散列它本身就是一个哈希,然后配合链表,就相当于自己可以做一个小的内存的数据管理的一个机制,那是不是意味着将来自己想去搞一点数据,自己在里面把它维护起来,有增删改查功能就可以了,就这个意思必须学会链表,看起来它虽然不是很难,但是它很有用


三、小结

链表是一个有序的列表,它在内存中的存储可能不是连续的,但是在形式上体现出来肯定必须是一个有序的,在上文中画了一个图

单链表一般来讲会带一个表头,因为一般来说为了比较容易控制链表一般来讲,为了比较容易控制列表,一般都有表头,比较好的链表增删改查的操作都会给设置一个头结点,头结点主要是用来表示是链表的头它本身并不存放数据,头结点的价值或者作用主要是用来标识链表的头这个是不能动的,一旦头结点没有了,那就完全找不到了节点本身不存放数据

相关文章
|
16天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
27 1
|
19天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
63 4
|
17天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
17天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
17天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
38 5
|
16天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
42 1
|
11天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
17天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
5天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。
|
5天前
|
机器学习/深度学习 算法 信息无障碍
基于GoogleNet深度学习网络的手语识别算法matlab仿真
本项目展示了基于GoogleNet的深度学习手语识别算法,使用Matlab2022a实现。通过卷积神经网络(CNN)识别手语手势,如"How are you"、"I am fine"、"I love you"等。核心在于Inception模块,通过多尺度处理和1x1卷积减少计算量,提高效率。项目附带完整代码及操作视频。