Collection子接口之List

本文主要介绍List接口下的ArrayList和LinkedList两个类。至于Vector类，其实现和ArrayList十分相似，底层都是Object[]，主要区别在于Vector是线程安全的，里面所有方法都被synchronized修饰。

尽量减少使用Vector，尽管它是线程安全的，但是和ArrayList相比，效率大大降低。

ArrayList

ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。其特点如下：

1. 底层通过数组实现，允许放入null元素；

   

2. 数组容量不够时可以动态扩容（调用grow()方法约为原大小1.5倍，代价较大，应尽量避免）；

3. 实现了RandomAccess接口，支持随机访问；

4. size()，isEmpty()，get()，set()方法都在常数时间内完成；

5. 为追求效率，ArrayList没有实现同步(synchronized) ，如需用到多线程，可用Vector代替。

注： 以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。

LinkedList

LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类(它是个接口名字)。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)有着更好的性能。其特点如下：

1. 底层通过双向链表实现

   

2. 所有和下标相关的操作都是线性时间

3. 为追求效率LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。

参考资料

1. https://pdai.tech/md/java/collection/java-collection-ArrayList.html

2. https://pdai.tech/md/java/collection/java-collection-LinkedList.html

3. https://javaguide.cn/java/collection/arraylist-source-code/