List
List是Java中的一个接口，常用的实现类有ArrayList和LinkedList
ArrayList
ArrayList的底层结构是数组
- Java本身就有数组了，为什么要用ArrayList？
Java原生的数组在使用的时候必须要为它创建大小，而ArrayList不用。在日常开发中，通常我们是不知道要给数组分配多大的容量，如果数组的大小指定多了，浪费内存；如果数组的大小指定少了，装不下。而ArrayList底层是实现了动态扩容的。
- ArrayList怎么扩容？一次扩容多少？
当我们new一个ArrayList的时候，默认会创建一个空的Object数组，大小为0。当我们第一次add()添加数据的时候，会给这个数组初始化一个大小，这个大小默认值为10。使用ArrayList在每一次add添加数据的时候，它都会先去计算这个数组空间是否足够，如果空间足够那就会直接追加上去；如果空间不够就会扩容。在源码中有一个grow方法，每一次扩容是扩为原来的1.5倍。空间扩容完成后，会调用System.arraycopy来对数组进行拷贝。
- 为什么日常开发中ArrayList用得最多？
这是由底层的数据结构来决定的，在日常开发中，遍历的需求比增删要多，即便是增删往往也是在List的尾部添加数据，在尾部添加数据ArrayList的时间复杂度和LinkedList一样也是O(1)
- 线程安全的List有哪些？
有Vector；还可以用Collections.synchronizedList来包装ArrayList；还有java.util.concurrent包下的CopyOnWriteArrayList。
LinkedList
LinkedList的底层结构是链表，增删快（不用复制数组），查询慢（）
Vector
- Vector和ArrayList的区别？
Vector的底层结构也是数组，相对于ArrayList，Vector是线程安全的（所以Vector效率更低，类似StringBuffer和StringBuilder的区别）。Vector在扩容的时候直接扩容为原来的两倍（占空间多）。
CopyOnWriteArrayList
copy-on-write（cow）：读时共享，写时复制策略。
Linux在最早的时候父进程fork出子进程是子进程复制父进程的整个PCB（除了PID，PID都是从操作系统中获取），fork完成后父进程和子进程有相同的数据段和代码段（但实际数据不一样，因为数据是由虚拟地址指向真实的物理地址，子进程只复制了虚拟地址，进程间的虚拟地址是独立的，所以指向的物理地址肯定不相同）。
当使用了cow策略，fork后不再整个复制父进程的PCB给子进程，而是内核把父进程和子进程对父进程PCB的访问权限设置为只读，如果父子进程中的任何一个试图修改这些区域，内核只为修改的那片区域制作一个副本给子进程。
这样做的好处就是，等到真正发盛修改的时候，再去分配资源，可以减少分配或者复制大量资源时带来的瞬时开销。简单来说，可以理解为懒加载或者单例模式的懒汉式，等真正用到的时候再分配。
在文件系统中也有cow机制，在修改数据的时候，不会直接在原来的数据位置上进程操作，而是重新找个位置修改。比如说：要修改数据块A的内容，先把A读出来，写到B块里面去，如果这时候断电了，原来A的内容还在。这样做的好处就是可以保证数据的完整性，瞬间挂掉了容易恢复。
回到CopyOnWriteArrayList：是一个线程安全的List，底层是通过赋值数组的方式来实现的，在它的add()方法的实现里，首先它会加lock锁，锁住，然后会复制出一个新的数组，往新的数组里边add真正的元素，最后把array的指向改变为新的数组，和文件的cow机制很像（注意：每次add后容量只会+1，不做扩容）。缺点是：1、CopyOnWriteArrayList很耗费内存，每次add都会复制一整个数组；2、CopyOnWriteArrayList只能保证数据的最终一致性，不能保证数据的实时一致性，比如有两个线程，线程A去读取CopyOnWriteArrayList的数据还没读完，线程B进行了add()操作，但是还没将array指向改变后的新数组时，线程A此时还是可以把剩余的数据给读出来。
相对与Vector的优点：读不加锁。
