算法快学笔记(二):数组与链表

栏目: 编程工具 · 发布时间: 6年前

内容简介:当程序需要将数据存储到内存时,计算机会给你一个存储地址。需要存储多项数据时,有两种基本方式——数组和链表。但它们并非都适用于所有的情形,因此知道它们的特性很重要。本文将对数组与链表的原理与优缺点进行总结。使用数组存储多个元素的时候,数组中元素的地址时刻都是挨在一起的,为了便于理解,以看电影为例进行说明。

1. 说明

当程序需要将数据存储到内存时,计算机会给你一个存储地址。需要存

储多项数据时,有两种基本方式——数组和链表。但它们并非都适用于所有的情形,因此知道它们的特性很重要。本文将对数组与链表的原理与优缺点进行总结。

2. 数组

使用数组存储多个元素的时候,数组中元素的地址时刻都是挨在一起的,为了便于理解,以看电影为例进行说明。

你和你小伙伴的关系都非常的好,如果一起看电影必须要座位要挨在一起,你先和两个小伙伴去看电影,到了电影院只坐有连续三个空位的地方( 数组初始化 )。找到地方就坐后又来了一位朋友,但原来坐的地方没有空位置,这时只能重新找一个可坐下所有人的地方( 数组插入新元素 )。如果又来了一位朋友,而当前坐的地方也没有空位,你们就得再次转移!好不容易安稳的看了会电影,有个小伙伴又要离开,为了让大家都紧挨着,有一部分小伙伴就需要挪动下座位( 数组删除元素 )。

真是太麻烦了。同样,在数组中添加/删除元素也很麻烦。因此数组添加/删除元素的速度都会很慢。

对于新增元素的一种解决之道是“预留座位”:即便你们现在只有3个小伙伴,也请计算机提供10个位置,以防临时有朋友来的情况。这样,只要小伙伴不超过10个,就无需转移。

该方案存在两个缺点。

  • 你额外请求的位置可能根本用不上,这将浪费内存。你没有使用,别人也用不了。
  • 待办事项超过10个后,你还得转移。

3. 链表

链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起,因此链表中的元素可存储在内存的任何地方,当添加/删除元素时其他的元素都不需要移动。同样以看电影为例对链表进行说明。

假设你与10位朋友去看一部很火的电影。你们11人想坐在一起,但看电影的人较多,没有11个在一起的座位,如果是数组的解决方式,这个电影就看不了了,因为实在没有这么多空的位置是在一起的。链表的解决方式是“既然这样,我们分开来坐,但是为大家之间还可能会联系,因此每个人都依次记得下一个人的座位号,例如A记得B的座位号是008,B记得C的座位号是102…”,因此,只要有足够的内存空间,就能为链表分配内存

4. 数组与链表的查询

从看电影的例子可以看出,使用链表的方式,解决入场观看(初始化),以及中途人员变动(新增/删除)是一个比较好的方案,但是如果用来找你的小伙伴了?考虑以下两种操作

4.1 全部查找

  1. 数组方式:由于所有小伙伴都做在一起,只要找到第一个,其他的就都能找到。
  2. 链表方式:虽然小伙伴都是分散做的,但是由于每个小伙伴都知道下一个小伙伴的座位号,因此要找全部小伙伴也比较方便

4.2 随机查找

假设10个小伙伴的入场看电影的时候,是按照年龄从小到大的顺序入场的,你突然要找年龄最大的那个小伙伴。

  1. 数组方式:由于所有小伙伴都做在一起,找到第一个人后,他的座位号+10就是年龄最大的那个小伙伴。
  2. 链表方式:由于小伙伴都是分散坐的,所以你只能从第一个人问第二个人的座位号,到第二个人那边后,问他第三个人的座位号,以此类推。

通过上面的例子可以看出,在随机读取的场景:

  1. 需要随机地读取元素时,数组的效率很高,因为可迅速找到数组的任何元素。
  2. 在链表中元素并非靠在一起的,你无法迅速计算出第i个元素的内存地址,而必须先访问第一个元素以获取第二个元素的地址,再访问第二个元素以获取第三个元素的地址,以此类推,直到访问第i个元素。

5. 总结

  • 需要存储多个元素时,可使用数组或链表。
  • 数组的元素都在一起。
  • 链表的元素是分开的,其中每个元素都存储了下一个元素的地址。
  • 数组的随机读取速度很快。
  • 链表的插入和删除速度很快。
  • 在同一个数组中,所有元素的类型都必须相同(都为int、 double等)。

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

搜

(美)约翰·巴特利 / 张岩、魏平 / 中信出版社 / 2006-1 / 35.00元

这个世界需要什么?如何任何一家公司能回答好这个问题,它就掌握了控制商业社会,乃至整个人类文明的万能钥匙。在过去的几年中,Google正在为获得这把钥匙而努力。虽然Google并非搜索业务的最早开发者,但它凭借着简明、便利、实用的搜索技术和理念,逐渐击败雅虎、Alta Vista等搜索领域的先锋,成为搜索行业名副其实的王者。 本书描述了Google如何从斯坦福一个不起眼的公司迅速崛起为“......一起来看看 《搜》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具