1. 数组（array）
数组在内存中的储存方式是连在一起的。
优点
由于数组中的所有元素是连在一起的，所以查找任何元素都很方便。需要注意是第一个元素是从0开始数，也就是如果你想读取第10个元素，只需要输入索引9就可以了。
缺点
数组在内存中是必须连在一起的，这就造成了一个问题。如果在内存给一个数组分配除了一个可以储存5个元素的数组，那么给这个数组增加下一个元素的时候，就必须重新开辟一片空间来储存这6个元素。这就好像5个好友去看电影，又来了一个朋友，但是原来的位置地方不够了，他们必须去重新找一个有6个位置的地方，甚至换一个影厅。
一个折中的解决方案是：每次给一个数组分配空间的时候，都多分配点。比如只需要一个可以储存5个元素的数组，也让计算机会给你分配10个 。但这也不是最完美的，因为这个方案有两个缺点：
-
多申请时候的空间如果不用的话，就会造成浪费。因为你不用，别人也不能用。
-
当增加的元素超过了10个了，还得重新找地方。
2. 链表（Linked lists）
链表的元素可以在内存中的任何地方。每一个元素都储存着下一个元素的地址，从而使一系列随机的元素串在一起。这就好像6个人去看电影，他们不要求非得坐在一起，分开也没事。
优点
添加元素容易，可以将其放在内存中的任何位置，并将其地址储存到前一个元素中。
缺点
链表在查找元素的时候会很慢，比如你要查找最后一个元素，你不能直接读取最后一个元素，你必须从第2个开始，从中获取第2个元素的地址，然后从第2个元素中获取第3个元素的地址，以此类推。如果你需要读取所有数据时，链表的效率高很。如果你需要跳跃，链表的效率很低。
3. 在中间插入元素
在中间插入元素使用链表，这样只用修改它前面元素指向的地址。而使用数组的话，就必须将后面的元素都往后移，如果没有足够空间，就会把所有数组都复制到其他地方！
4. 删除元素
删除元素也用链表好，同理，你只需要修改前一个元素的指向就可以了。而数组删除元素后，必须将后面的值向前移。
注意：只有可以访问要删除的元素时，删除操作的运行时间才为O(1)。通常我们都记录了链表的第一个元素和最后一个元素，因此删除这些元素时运行时间为O (1)”
5. 总结
| 数组 | 链表 | |
|---|---|---|
| READING | O(1) | O(n) |
| INSERTION | O(n) | O(1) |
| DELETION | O(n) | O(1) |
数组的使用场景要比链表多，因为数组支持随机访问，而链表是顺序访问。顺序访问意味着必须从第一个开始一个一个读取，想读取第10个元素需要把前9个都读取完了才行，而随机访问可以直接读取第10个元素。