【ZT】ArrayList、Vector、LinkedList之间的区别

这个最原始，面试最具讨论性的问题，下面说说我个人的理解，如有不对还请大家指正！

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set

如图所示，Vector,ArrayList,LinkedList都实现了List类，

Vector类和ArrayList类的主要不同之处在于同步。除了两个只用于串行化的方法，没有一个ArrayList的方法具有同步执行的能力；相反，Vector的大多数方法具有同步能力，或直接或间接。因此，Vector是线程安全的，ArrayList不是。这使得ArrayList要比Vector快速。对于一些最新的JVM，两个类在速度上的差异可以忽略不计：严格地说，对于这些JVM，这两个类在速度上的差异小于比较这些类性能的测试所显示的时间差异。

通过索引访问和更新元素时，Vector和ArrayList的实现有着卓越的性能，因为不存在除范围检查之外的其他开销。除非内部数组空间耗尽必须进行扩展，否则，向列表的末尾添加元素或者从列表的末尾删除元素时，都同样有着优秀的性能。插入元素和删除元素总是要进行数组复制（当数组先必须进行扩展时，需要两次复制）。被复制元素的数量和[size-index]成比例，即和插入/删除点到集合中最后索引位置之间的距离成比例。对于插入操作，把元素插入到集合最前面（索引0）时性能最差，插入到集合最后面时（最后一个现有元素之后）时性能最好。随着集合规模的增大，数组复制的开销也迅速增加，因为每次插入操作必须复制的元素数量增加了。

从内部实现机制来讲ArrayList和Vector都是使用Objec的数组形式来存储的。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。

在ArrayList的前面或中间插入数据时，必须将其后的所有数据相应的后移，这样必然要花费较多时间，所以，当你的操作是在一列数据的后面添加数据而不是在前面或中间，并且需要随机地访问其中的元素时，使用ArrayList会提供比较好的性能；

而访问链表中的某个元素时，就必须从链表的一端开始沿着连接方向一个一个元素地去查找，直到找到所需的元素为止，所以，当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用LinkedList了。

ArrayList的查询效率比较高，增删动作的效率比较差，适用于查询比较频繁，增删动作较少的元素管理的集合。LinkedList的查询效率低，但是增删效率很高。适用于增删动作的比较频繁，查询次数较少的元素管理集合。