数组的特点
在内存中，数组是一块连续的区域，拿看电影的来说，几个人在电影院必须坐一起。
数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间，比如看电影时，为了保证10个人坐一起，必须提前订好10个连续的位置，这样的好处就是能保证10个人可以在一起，但是这样的缺点是，如果来的人不够10个，那么剩下的位置就浪费了，如果临时有多来了个人，那么10个就不够用了，这时可能需要将第11个位置上的人挪走，或者是11个人重新去找一个11连坐的位置，效率都很低，如果没有找到符合要求的座位，那么就没法坐了。
插入数据和删除数据效率很低，插入数据时，这个位置后面的数据在内存中都要向后移动，删除数据时，这个数据后面的数据都要向前移动，比如原来去了5个人，后来又去了一个人要坐在第三个位置上，那么第三个到第五个都要向后移动一个位子，将第三个位置留给新来的人，当这个人走了的时候，因为他们要连在一起的。所以后面几个人要向前移动一个位置，把这个空位补上。
随机读取效率很高，因为数组是连续的。知道每一个数据的内存地址，可以直接找到该地址的数据。
不利于拓展。数组定义的空间不够要重新定义数组。
链表的特点
在内存中可以存在任何地方，不要求连续，在电影院几个人可以随便坐。
每一个数据都保存了下一个数据的内存地址。通过这个地址找到下一个数据，第一个人知道第二个人的座位号，第二个人知道第三个人的座位号。
增加数据和删除数据很容易。再来个人可以随便坐，比如来个人要坐到第三个位置。那他只需要把自己的位置告诉第二人。问第二个人就能知道第三个人的位置，其他人都不用动。
查找数据时效率低，因为不具备随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推，要找到第三个人，必须从第一个人开始问起。
不指定大小，拓展方便，链表不用定义大小，数据随意增删。
各自的优缺点
数组的有点
随机访问性强
查找速度快
数组的缺点
插入和删除效率低
可能浪费内存
内存空间要求高，必须有足够的连续内存空间
数组大小固定，不能动态拓展
链表的优点
插入删除速度快
内存利用率高,不会浪费内存
大小没有固定，拓展很灵活
链表的缺点
不能随机查找，必须从第一个开始遍历，查找效率低
| name | 数组 | 链表 |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
