什么是链表? | 算法必看系列二-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

什么是链表? | 算法必看系列二

简介: 如果说数据结构是算法的基础,那么数组和链表就是数据结构的基础。因为像堆,栈,树,图等比较复杂的数组结基本上都可以由数组和链表来表示,所以掌握数组和链表的基本操作十分重要。
+关注继续查看

原文链接

什么是链表

前言

如果说数据结构是算法的基础,那么数组和链表就是数据结构的基础。因为像堆,栈,树,图等比较复杂的数组结基本上都可以由数组和链表来表示,所以掌握数组和链表的基本操作十分重要。

今天就来看看链表的基本操作及其在面试中的常见解题思路,本文将从以下几个点来讲解链表的核心知识

1.什么是链表,链表的优缺点
2.链表的表示及基本操作
3.面试中链表的常见解题思路—翻转

什么是链表

相信大家已经开始迫不及待地想用链表解题了,不过在开始之前我们还是要先来温习下链表的定义,以及它的优势与劣势,磨刀不误砍柴功!

链表的定义

链表是物理存储单元上非连续的、非顺序的存储结构,它是由一个个结点,通过指针来联系起来的,其中每个结点包括数据和指针。
image.png
链表的非连续,非顺序,对应数组的连续,顺序,我们来看看整型数组 1,2,3,4 在内存中是如何表示的
image.png
可以看到数组的每个元素都是连续紧邻分配的,这叫连续性,同时由于数组的元素占用的大小是一样的,在 Java 中 int 型大小固定为 4 个字节,所以如果数组的起始地址是 100, 由于这些元素在内存中都是连续紧邻分配的,大小也一样,可以很容易地找出数组中任意一个元素的位置,比如数组中的第三个元素起始地址为 100 + 2 * 4 = 108,这就叫顺序性。查找的时间复杂度是O(1),效率很高!

那链表在内存中是怎么表示的呢
image.png
可以看到每个结点都分配在非连续的位置,结点与结点之间通过指针连在了一起,所以如果我们要找比如值为 3 的结点时,只能通过结点 1 从头到尾遍历寻找,如果元素少还好,如果元素太多(比如超过一万个),每个元素的查找都要从头开始查找,时间复杂度是O(n),比起数组的 O(1),差距不小。

除了查找性能链表不如数组外,还有一个优势让数组的性能高于链表,这里引入程序局部性原理,啥叫程序局部性原理。

我们知道 CPU 运行速度是非常快的,如果 CPU 每次运算都要到内存里去取数据无疑是很耗时的,所以在 CPU 与内存之间往往集成了挺多层级的缓存,这些缓存越接近CPU,速度越快,所以如果能提前把内存中的数据加载到如下图中的 L1, L2, L3 缓存中,那么下一次 CPU 取数的话直接从这些缓存里取即可,能让CPU执行速度加快,那什么情况下内存中的数据会被提前加载到 L1,L2,L3 缓存中呢,答案是当某个元素被用到的时候,那么这个元素地址附近的的元素会被提前加载到缓存中
image.png
以上文整型数组 1,2,3,4为例,当程序用到了数组中的第一个元素(即 1)时,由于 CPU 认为既然 1 被用到了,那么紧邻它的元素 2,3,4 被用到的概率会很大,所以会提前把 2,3,4 加到 L1,L2,L3 缓存中去,这样 CPU 再次执行的时候如果用到 2,3,4,直接从 L1,L2,L3 缓存里取就行了,能提升不少性能

画外音:如果把 CPU 的一个时种看成一秒,则从 L1 读取数据需要 3 秒,从 L2 读取需要 11 秒,L3读取需要 25秒,而从内存读取呢,需要 1 分 40 秒,所以程序局部性原理能对 CPU 执行性能有很大的提升

而链表呢,由于链表的每个结点在内存里都是随机分布的,只是通过指针联系在一起,所以这些结点的地址并不相邻,自然无法利用 程序局部性原理 来提前加载到 L1,L2,L3 缓存中来提升程序性能。

画外音:程序局部性原理是计算机中非常重要的原理,这里不做展开,建议大家查阅相关资料详细了解一下

如上所述,相比数组,链表的非连续,非顺序确实让它在性能上处于劣势,那什么情况下该使用链表呢?考虑以下情况

  • 大内存空间分配

由于数组空间的连续性,如果要为数组分配 500M 的空间,这 500M 的空间必须是连续的,未使用的,所以在内存空间的分配上数组的要求会比较严格,如果内存碎片太多,分配连续的大空间很可能导致失败。而链表由于是非连续的,所以这种情况下选择链表更合适。

  • 元素频繁删除和插入

如果涉及到元素的频繁删除和插入,用链表就会高效很多,对于数组来说,如果要在元素间插入一个元素,需要把其余元素一个个往后移(如图示),以为新元素腾空间(同理,如果是删除则需要把被删除元素之后的元素一个个往前移),效率上无疑是比较低的。
(在 1,2 间插入 5,需要把2,3,4 同时往后移一位)
image.png
后移:
image.png
插入5:
image.png
完成!
而链表的插入删除相对来说就比较简单了,修改指针位置即可,其他元素无需做任何移动操作(如图示:以插入为例)
image.png
插入5:
image.png
完成:
image.png
综上所述:如果数据以查为主,很少涉及到增和删,选择数组,如果数据涉及到频繁的插入和删除,或元素所需分配空间过大,倾向于选择链表。

说了这么多理论,相信读者对数组和链表的区别应该有了更深刻地认识了,尤其是程序局部性原理,是不是开了不少眼界^_^,如果面试中问到数组和链表的区别能回答到程序局部性原理,会是一个非常大的亮点!

了解更多算法内容,请持续关注:阿里云开发者社区算法编程官方技术圈 !

下一节:链表的表示

来源 | 五分钟学算法
作者 | 程序员小吴

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
什么是算法及其特征
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。
677 0
五分钟了解一下什么是「贪心算法 」 | 算法必看系列二十一
贪心算法在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
600 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4479 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
5727 0
动画:七分钟理解什么是KMP算法 | 算法必看系列十五
Knuth-Morris-Pratt 字符串查找算法,简称为 KMP算法,常用于在一个文本串 S 内查找一个模式串 P 的出现位置。
731 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
10767 0
阿里云服务器远程登录用户名和密码的查询方法
阿里云服务器远程连接登录用户名和密码在哪查看?阿里云服务器默认密码是什么?云服务器系统不同默认用户名不同
443 0
什么是链表? | 算法必看系列二
如果说数据结构是算法的基础,那么数组和链表就是数据结构的基础。因为像堆,栈,树,图等比较复杂的数组结基本上都可以由数组和链表来表示,所以掌握数组和链表的基本操作十分重要。
429 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
3227 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载