数据结构与算法系列3之从内存角度分析数组与链表的区别
数据结构与算法系列3之从内存角度分析数组与链表的区别
数据结构与算法系列3
写在前面
前面两章讲了链表和动态数组，我们这章来从内存的角度的来讲讲二者的区别
什么是内存
写在前面：
由于本章是从内存的角度来讲述数组与链表，所以我们先来讲讲内存
内存概述
内存是计算机的重要部件之一。它是外存与CPU进行沟通的桥梁，计算机中所有程序的运行都在内存中进行。内存性能的强弱影响计算机整体发挥的水平。内存(Memory)也称内存储器和主存储器，它用于暂时存放CPU中的运算数据，与硬盘等外部存储器交换的数据。只要计算机开始运行，操作系统就会把需要运算的数据从内存调到CPU中进行运算。当运算完成，CPU将结果传送出来。内存的运行也决定计算机整体运行快慢的程度。内存条由内存芯片、电路板、金手指等部分组成。
内存工作原理
比如我们去考驾照，考驾照的地方有一个寄存柜，你需要将你的东西寄存到寄存柜里
假设每个柜子只可以放一样东西，你有两样东西需要寄存，因此需要两个寄存柜
然后你就可以将你的两样东西寄存到箱子里
然后你就可以放心的去考驾照了，等考好了再到对应的箱子里取出自己的物品即可，这大致就是计算机内存的工作原理，计算机像是很多抽屉的集合，每个抽屉都有地址，就像下面一样划分成一个个区块，一个个地址
需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据。有两种基本方式---数组和链表。他们并非都适用与所有场景。
数组在内存中的分布
数组再内存中是连续分布的，什么是连续分布呢，就拿上面的寄存柜来说，比如寄存柜有100个柜子，你有四个东西要寄存，一个柜子只能放一个东西，所以你要四个柜子，连续分布就是只这四个柜子要一个柜子挨着一个柜子连在一起，需要连号，比如1234，5678等等
数字代表寄存的物品标号
这种方式的优缺点是什么呢？
我们再来举一个例子
比如我们去组团看电影，看电影的时候一共有十个人，为了保证10个人能坐在一起，必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。但是这样的缺点是，如果来的人不够10个，那么剩下的位置就浪费了。如果临时有多来了个人，那么10个就不够用了，这时可能需要将第11个位置上的人挪走，或者是他们11个人重新去找一个11连坐的位置，效率都很低。如果没有找到符合要求的作为，那么就没法坐了。
缺点
人来在计算机中就是插入数据，人走在计算机中就是删除数据。而数组方式存放数据，插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。 比如原来去了5个人，然后后来又去了一个人要坐在第三个位置上，那么第三个到第五个都要往后移动一个位子，将第三个位置留给新来的人。 当这个人走了的时候，因为他们要连在一起的，所以他后面几个人要往前移动一个位置，把这个空位补上。
预留座位
对于这种位置不够的缺点我们可以通过"预留座位的方式"来解决，即即使你们只有十个人去看电影，为了防止有人突然拖家带口，导致位置不够的情况，为了以防万一你就事先买了十五张电影票。一旦有人来了就有位置做了。在计算机中我们为了防止数组溢出，也可以使用这种方式，即申请一个比预期大的数组，来防止数组不够大，存储不了数据的情况。但这种"预留座位"的方式也会导致内存空间的浪费
优点
随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。
并且不利于扩展，数组定义的空间不够时要重新定义数组。（刚刚讲的十个座位，多来了一个人，你就只能重新申请空间定义一个大于11的数组）
链表在内存中的分布
数组再内存中是非连续分布的，什么是非连续分布呢，就拿上面的寄存柜来说，比如寄存柜有100个柜子，你有四个东西要寄存，一个柜子只能放一个东西，所以你要四个柜子，非连续分布就是随便在寄存柜中找四个柜子就可以了，不需要连号，比如1589，2489等等都可以
数字代表寄存的物品标号
优缺点
在内存中可以存在任何地方，不要求连续。 在电影院几个人可以随便坐。比如十个人去看电影，这十个人可以在电影院随便找十个位置坐下。不需要十个人坐在一起，这十个人每个人都记住下一个人的位置号，这样到时候找人也就不会找不到了
在计算机中也一样的道理，每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。 第一个人知道第二个人的座位号，第二个人知道第三个人的座位号……
优点
增加数据和删除数据很容易。 再来个人可以随便坐，比如来了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。
不指定大小，扩展方便。链表大小不用定义，数据随意增删。
缺点
查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。 要找到第三个人，必须从第一个人开始问起。
小总结
数组的优点
- 随机访问性强
- 查找速度快
数组的缺点
- 插入和删除效率低
- 可能浪费内存
- 内存空间要求高，必须有足够的连续内存空间。
- 数组大小固定，不能动态拓展
链表的优点
- 插入删除速度快
- 内存利用率高，不会浪费内存
- 大小没有固定，拓展很灵活。
链表的缺点
- 不能随机查找，必须从第一个开始遍历，查找效率低
- | 数组 | 链表 |
|---|---|---|
读取 | O(1) | O(n) |
插入 | O(n) | O(1) |
删除 | O(n) | O(1) |
应用场景
数组应用场景：
数据比较少；经常做的运算是按序号访问数据元素；数组更容易实现，任何高级语言都支持；构建的线性表较稳定。
链表应用场景：
对线性表的长度或者规模难以估计；频繁做插入删除操作；构建动态性比较强的线性表。