数组和链表的区别?「建议收藏」

数组和链表的区别?「建议收藏」今天来说下两种最基本的数据结构——数组和链表,它们无处不在!下面我们来一一介绍下他们,首先了解下内存分配的!内存的工作原理假设你去看演出,需要将东西寄存。寄存处有一个柜子,柜子有很多抽屉。每个抽屉可放一样东西,你有两样东西要寄存,因此要了两个抽屉。现在你可以去看演出了!这大致就是计算机内存的工作原理。计算机就像是很多抽屉的集合体,每个抽屉都有地址。fe0ffeeb是一个内存单元的地址。需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存储多项数据时,有两种基本方式

大家好,又见面了,我是你们的朋友全栈君。

今天来说下两种最基本的数据结构——数组和链表,它们无处不在!下面我们来一一介绍下他们,首先了解下内存分配的!

内存的工作原理

假设你去看演出,需要将东西寄存。寄存处有一个柜子,柜子有很多抽屉。
在这里插入图片描述
每个抽屉可放一样东西,你有两样东西要寄存,因此要了两个抽屉。
在这里插入图片描述
现在你可以去看演出了!这大致就是计算机内存的工作原理。计算机就像是很多抽屉的集合体,每个抽屉都有地址。
在这里插入图片描述
fe0ffeeb是一个内存单元的地址。需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存储多项数据时,有两种基本方式——数组和链表。但它们并非都适用于所有的情形,因此知道它们的差别很重要。接下来介绍数组和链表以及它们的优缺点。

数组

数组怎么在储存在内存中呢?举个例子,我们将待办事项存储在数组中。使用数组意味着所有待办事项在内存中都是相连的(紧靠在一起的)。
在这里插入图片描述
现在假设你要添加第四个待办事项,但后面的那个抽屉放着别人的东西!
在这里插入图片描述

这就像你与朋友(假如3人)去看电影,找到地方就坐后又来了一位朋友,但原来坐的地方没有空位置(你们4人想坐一起),只得再找一个可坐下所有人的地方。在这种情况下,你需要请求计算机重新分配一块可容纳4个位置的内存。如果又来了一位朋友,而当前坐的地方也没有空位,你们就得再次转移!真是太麻烦了。同样,在数组中添加新元素也可能很麻烦。如果没有了空间,就得移到内存的其他地方,因此添加新元素的速度会很慢。假如在数组中间插入一个待办事项(买茶叶)
在这里插入图片描述
如果没有足够的空间,可能还得将整个数组复制到其他地方!同理!要删除待办事项(吃午饭),删除后,必须将后面的元素都向前移,也是很费时间的!那么数组有没有优势的地方,优势在哪里呢?看下图5个元素的数组:
在这里插入图片描述

只需执行简单的数学运算就知道,需要随机地读取元素时,数组的效率很高,因为可迅速找到数组的任何元素。

链表

链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。
在这里插入图片描述
这犹如寻宝游戏。你前往第一个地址,那里有一张纸条写着“下一个元素的地址为123”。因此,你前往地址123,那里又有一张纸条,写着“下一个元素的地址为847”,以此类推。在链表中添加元素很容易:只需将其放入内存,并将其地址存储到前一个元素中。使用链表时,根本就不需要移动元素。这还可避免另一个问题。假设你与五位朋友去看一部很火的电影。你们六人想坐在一起,但看电影的人较多,没有六个在一起的座位。使用数组时有时就会遇到这样的情况。假设你要为数组分配10 000个位置,内存中有10 000个位置,但不都靠在一起。在这种情况下,你将无法为该数组分配内存!链表相当于说“我们分开来坐”,因此,只要有足够的内存空间,就能为链表分配内存。

那么链表有没有缺点?

当读取链的最后一个元素时,你不能直接读取,因为你不知道它所处的地址,必须先访问元素#1,从中获取元素#2的地址,再访问元素#2并从中获取元素#3的地址,以此类推,直到访问最后一个元素。需要同时读取所有元素时,链表的效率很高:你读取第一个元素,根据其中的地址再读取第二个元素,以此类推。但如果你需要跳跃,链表的效率真的很低。
在这里插入图片描述
使用链表时,插入元素很简单,只需修改它前面的那个元素指向的地址。而使用数组时,则必须将后面的元素都向后移。因此,当需要在中间插入元素时,链表是更好的选择。假如在链表中删除某个元素,只需修改前一个元素指向的地址即可。而使用数组时,删除元素后,必须将后面的元素都向前移。

总结

下面是数组和链表操作的运行时间:
在这里插入图片描述
数组和链表哪个用得更多呢?显然要看情况。但数组用得很多,因为它支持随机访问。有两种访问方式:随机访问和顺序访问。顺序访问意味着从第一个元素开始逐个地读取元素。链表只能顺序访问:要读取链表的第十个元素,得先读取前九个元素,并沿链接找到第十个元素。随机访问意味着可直接跳到第十个元素。本书经常说数组的读取速度更快,这是因为它们支持随机访问。很多情况都要求能够随机访问,因此数组用得很多!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/148625.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • sql:常用:group by 多个字段「建议收藏」

    sql:常用:group by 多个字段「建议收藏」首先groupby的简单说明:  groupby一般和聚合函数一起使用才有意义,比如countsumavg等,使用groupby的两个要素:  (1)出现在select后面的字段要么是是聚合函数中的,要么就是groupby中的.  (2)要筛选结果可以先使用where再用groupby或者先用groupby再用having下面看下groupb…

  • 测试deeplink「建议收藏」

    测试deeplink「建议收藏」deeplink测试

  • 运维标准化工作流程

    运维标准化工作流程运维标准化工作流程:http://wenku.baidu.com/link?url=bt1ZVijjS35mSSMoDbs4rgWtrG0zBY8a-zuIKPfi5TGehD6XHD8RzscniHsOtODaKkqCG7ba5DeUHLS6sqes03JdEdOYEK1OPviwsl9wv0_ 转载于:https://blog.51cto.com/jackysz…

  • MapReduce编程案例系列篇(01-15)

    MapReduce编程案例系列篇(01-15)由于本人最开始接触大数据工作,主要以写MapReduce程序为主,虽然现在有流行的言论称MapReduce这种运行很慢的分布式计算编程框架将要被各种内存计算框架取代。但是MapRedcue也会吸收很多流行的内存计算的各种优点,我相信,将来,MapReduce绝对不会沦落到要淘汰的地步。甚至会后来居上。在此,本人总结一篇关于MapReduce编程的各种典型应用场景编程案例,便于大家查阅学习…

  • win10下pytorch-gpu安装以及CUDA详细安装过程

    win10下pytorch-gpu安装以及CUDA详细安装过程win10下pytorch-gpu安装以及CUDA详细安装过程1.Cuda的下载安装及配置首先我们要确定本机是否有独立显卡。在计算机-管理-设备管理器-显示适配器中,查看是否有独立显卡。可以看到本机有一个集成显卡和独立显卡NVIDIAGetForceGTX1050。接下来,测试本机独立显…

  • Linux文件系统类型[通俗易懂]

    文件系统是操作系统用于明确磁盘或分区上的文件的方法和数据结构; 即在磁盘上组织文件的方法。也指用于存储文件的磁盘或分区一个分区或磁盘能作为文件系统使用前,需要初始化,并将记录数据结构写到磁盘上。这个过程就叫建立文件系统 种类:1 ext2与ext3是linux专门设计的硬盘文件系统一般称为扩展文件系统。Ext3增加了日志记录功能。fdisk 分区在终端会显示打印信息   mkfs.ext4 /de…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号