数组与链表

线索：

1. 对比数组和链表各自的特点；

2. 对比 Vector、ArrayList、LinkedList

3. 数组如何实现根据下标随机访问？

1. 数组与链表的特点。

数组：①根据下标随机访问；②插入和删除低效，这是因为为了保证数组的连续性，需要移动后续元素，平均时间复杂度是 O(N)；③一段连续的内存空间；④CPU 缓存机制友好；⑤扩容时的拷贝；

链表：①插入删除的时间复杂度是 O(1)；②不需要连续的内存空间，且天然支持动态扩容，但对 CPU 缓存机制不友好；

基于数组与链表的特点，在应用开发中，如果事先可以估计到，应用操作是偏向于插入、删除，还是随机访问较多，就可以针对性的进行选择。

2. Vector、ArrayList 与 LinkedList

Vector 和 ArrayList 底层都是基于数组，都支持动态扩容，区别在于 Vector 扩大 2 倍，ArrayList 扩大 1.5 倍。此外，前者是线程安全，后者是线程不安全的。

另外需要注意的是，虽然它们支持动态扩容，但最好不要那么做。因为数组拷贝是一个非常耗时的操作。举个极端例子，假设 ArrayList 已经存了 1G 的数据，需要扩容到 1.5G，此时需要重新申请一个 1.5G 的空间，再将原来的 1G 拷贝到新的数组空间上。因此，如果事先能确定需要存储的数据大小，就最好在构造器事先指定。

LinkedList 底层是基于双向链表。是线程不安全的。

3. 数组如何实现根据下标随机访问？

a[i]_address = base_address + i * data_type_size（元素大小，比如 int 占 4 字节。）

比如，int[] a = new int[10]，假设基地址是 1000，那么 a[0]存储在 1000~1003，a[1]存储在 1004~1007……，假设要得到 a[5]，那么就 1000+5*4=1020