内存的工作原理

        小时候特别喜欢去超市买东西，但是自己买的水和吃的不能带进超市，那时候最喜欢的一个环节就是把东西存到自动储物柜。只需要按一下“存”按钮，就会自动弹出来一个柜子，让你把你的东西放进去，并且它会给你打印一张印着条码的纸，当你买完东西回家时，你可以拿着这个条码去扫一下，取回属于自己的东西。
        这大致上就是计算机内存的工作原理。计算机就像是有很多柜子的集合体，每个柜子都有地址。需要将数据存储到内存时，请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据时，有两种基本的方式——数组和链表。

数组

比如我有一些待办事项，我要将他们通过我写的程序放到内存中，我们先用数组存储。使用数组意味着：所有的待办事项在内存中都是相连的。

现在假设要添加第4个待办事项，但是问题在于，后面的位置已经被他人占用了！
这时候如果非要放第4个待办事项，只能向计算机请求一块可以容纳4个待办事项的内存——也就是说要将原本的3个事项转移到新的内存位置，再添加第4个待办事项。但是假设它还会扩展，那么如果有第5个、第6个…没错，每次都要转移！有一种办法是，提前申请10个位置，只要不超过10个，就无需转移。

因此数组存在这么两个问题：

• 额外的位置可以根本用不上，这将会额外占用内存
• 超过申请的内存大小后，还需要转移。

链表

链表中的元素可以存储在内存的任何地方。

链表中的每个元素都存储了下一个元素的地址，使得一系列随机的内存地址串在一起。

因此，链表无需额外分配内存，也无需移动元素。
也就是说，链表在插入时有着强大的优势。
回过头看数组，它有什么优势呢？
对于链表，比如需要读取第5个位置的元素，需要从第1个开始读，才能找到第5个元素；而数组由于是连续的内存地址，直接可以获取到第5个位置的元素——可以迅速找到数组中的所有元素。

附录 数组和链表操作的运行时间