一只胡说八道的猴子

一只胡说八道的猴子

数据结构与算法系列3

写在前面

前面两章讲了链表和动态数组,我们这章来从内存的角度的来讲讲二者的区别

什么是内存

写在前面:

由于本章是从内存的角度来讲述数组与链表,所以我们先来讲讲内存

内存概述

内存是计算机的重要部件之一。它是外存CPU进行沟通的桥梁,计算机中所有程序的运行都在内存中进行。内存性能的强弱影响计算机整体发挥的水平。内存(Memory)也称内存储器主存储器,它用于暂时存放CPU中的运算数据,与硬盘外部存储器交换的数据。只要计算机开始运行,操作系统就会把需要运算的数据从内存调到CPU中进行运算。当运算完成,CPU将结果传送出来。内存的运行也决定计算机整体运行快慢的程度。内存条由内存芯片电路板金手指等部分组成。

数据结构与算法系列3-LMLPHP

内存工作原理

比如我们去考驾照,考驾照的地方有一个寄存柜,你需要将你的东西寄存到寄存柜里

数据结构与算法系列3-LMLPHP

假设每个柜子只可以放一样东西,你有两样东西需要寄存,因此需要两个寄存柜

数据结构与算法系列3-LMLPHP

然后你就可以将你的两样东西寄存到箱子里

数据结构与算法系列3-LMLPHP

然后你就可以放心的去考驾照了,等考好了再到对应的箱子里取出自己的物品即可,这大致就是计算机内存的工作原理,计算机像是很多抽屉的集合,每个抽屉都有地址,就像下面一样划分成一个个区块,一个个地址
数据结构与算法系列3-LMLPHP

需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存储多项数据。有两种基本方式---数组和链表。他们并非都适用与所有场景。

数组在内存中的分布

数组再内存中是连续分布的,什么是连续分布呢,就拿上面的寄存柜来说,比如寄存柜有100个柜子,你有四个东西要寄存,一个柜子只能放一个东西,所以你要四个柜子,连续分布就是只这四个柜子要一个柜子挨着一个柜子连在一起,需要连号,比如1234,5678等等

数字代表寄存的物品标号
数据结构与算法系列3-LMLPHP

这种方式的优缺点是什么呢?

我们再来举一个例子

比如我们去组团看电影,看电影的时候一共有十个人,为了保证10个人能坐在一起,必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。但是这样的缺点是,如果来的人不够10个,那么剩下的位置就浪费了。如果临时有多来了个人,那么10个就不够用了,这时可能需要将第11个位置上的人挪走,或者是他们11个人重新去找一个11连坐的位置,效率都很低。如果没有找到符合要求的作为,那么就没法坐了。

缺点

人来在计算机中就是插入数据,人走在计算机中就是删除数据。而数组方式存放数据,插入数据和删除数据效率低,插入数据时,这个位置后面的数据在内存中都要向后移。删除数据时,这个数据后面的数据都要往前移动。 比如原来去了5个人,然后后来又去了一个人要坐在第三个位置上,那么第三个到第五个都要往后移动一个位子,将第三个位置留给新来的人。 当这个人走了的时候,因为他们要连在一起的,所以他后面几个人要往前移动一个位置,把这个空位补上。

预留座位

对于这种位置不够的缺点我们可以通过"预留座位的方式"来解决,即即使你们只有十个人去看电影,为了防止有人突然拖家带口,导致位置不够的情况,为了以防万一你就事先买了十五张电影票。一旦有人来了就有位置做了。在计算机中我们为了防止数组溢出,也可以使用这种方式,即申请一个比预期大的数组,来防止数组不够大,存储不了数据的情况。但这种"预留座位"的方式也会导致内存空间的浪费

优点

随机读取效率很高。因为数组是连续的,知道每一个数据的内存地址,可以直接找到给地址的数据。

并且不利于扩展,数组定义的空间不够时要重新定义数组。(刚刚讲的十个座位,多来了一个人,你就只能重新申请空间定义一个大于11的数组)

链表在内存中的分布

数组再内存中是非连续分布的,什么是非连续分布呢,就拿上面的寄存柜来说,比如寄存柜有100个柜子,你有四个东西要寄存,一个柜子只能放一个东西,所以你要四个柜子,非连续分布就是随便在寄存柜中找四个柜子就可以了,不需要连号,比如1589,2489等等都可以

数字代表寄存的物品标号
数据结构与算法系列3-LMLPHP

优缺点

在内存中可以存在任何地方,不要求连续。 在电影院几个人可以随便坐。比如十个人去看电影,这十个人可以在电影院随便找十个位置坐下。不需要十个人坐在一起,这十个人每个人都记住下一个人的位置号,这样到时候找人也就不会找不到了

在计算机中也一样的道理,每一个数据都保存了下一个数据的内存地址,通过这个地址找到下一个数据。 第一个人知道第二个人的座位号,第二个人知道第三个人的座位号……

优点

增加数据和删除数据很容易。 再来个人可以随便坐,比如来了个人要做到第三个位置,那他只需要把自己的位置告诉第二个人,然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。

不指定大小,扩展方便。链表大小不用定义,数据随意增删。

缺点

查找数据时效率低,因为不具有随机访问性,所以访问某个位置的数据都要从第一个数据开始访问,然后根据第一个数据保存的下一个数据的地址找到第二个数据,以此类推。 要找到第三个人,必须从第一个人开始问起。

小总结

数组的优点

  • 随机访问性强
  • 查找速度快

数组的缺点

  • 插入和删除效率低
  • 可能浪费内存
  • 内存空间要求高,必须有足够的连续内存空间。
  • 数组大小固定,不能动态拓展

链表的优点

  • 插入删除速度快
  • 内存利用率高,不会浪费内存
  • 大小没有固定,拓展很灵活。

链表的缺点

  • 不能随机查找,必须从第一个开始遍历,查找效率低

应用场景

数组应用场景:

数据比较少;经常做的运算是按序号访问数据元素;数组更容易实现,任何高级语言都支持;构建的线性表较稳定

链表应用场景:

对线性表的长度或者规模难以估计;频繁做插入删除操作;构建动态性比较强的线性表

02-11 05:37