ArrayList和LinkedList、及Vector对比分析

ArrayList和LinkedList

底层结构

两者的差别主要来自于底层的数据结构不同，ArrayList是基于数组实现的，LinkedList是基于双链表实现的。

接口实现

LinkedList类不仅是List接口的实现类，可以根据索引来随机访问集合中的元素，除此之外，LinkedList还实现了Deque接口，Deque接口是Queue接口的子接口，它代表一个双向队列，因此LinkedList可以作为双向队列，栈（可以参见Deque提供的接口方法）和List集合使用，功能强大。

效率性能

因为ArrayList是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的，可以直接返回数组中index位置的元素，因此在随机访问集合元素上有较好的性能。Array获取数据的时间复杂度是O(1)，但是要插入、删除数据却是开销很大的，因为这需要移动数组中插入位置之后的的所有元素。

相对于ArrayList，LinkedList的随机访问集合元素时性能较差，因为需要在双向列表中找到要index的位置，再返回；但在插入，删除操作是更快的。因为LinkedList不像ArrayList一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是ArrayList最坏的一种情况，时间复杂度是O(n)，而LinkedList中插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据时还需要更新索引（除了插入数组的尾部）。

资源消耗

除了时间上的消耗不同，LinkedList需要更多的内存，因为LinkedList中的每个节点中存储的是实际的数据和前后节点的位置，而ArrayList的每个索引的位置是实际的数据。

非线程安全

ArrayList 和 LinkedList 都是非线程安全的。如果要求线程安全，那么得考虑使用它两的兄弟Vector，Vector是同步的，当然，也可以通过一些办法包装ArrayList,LinkedList，使他们也达到同步，但效率可能会有所降低。

使用场景

可以根据数据总量大小解和常用的操作场景需要来选择。

如果需要对数据有较多的随机访问，ArrayList对象要优于LinkedList对象；
如果应用程序有更多的插入或者删除操作，较少的随机访问，LinkedList对象要优于ArrayList对象；
不过ArrayList的插入，删除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移动较少的数据，而LinkedList则需要一直查找到列表尾部，反而耗费较多时间，这时ArrayList就比LinkedList要快。

关于Vector

底层实现

Vector与ArrayList一样，也是通过数组实现的

线程安全

支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。

扩容机制

如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长度的100%，而arraylist增长率为目前数组长度的50%。

效率性能

如果查找一个指定位置的数据，vector和arraylist使用的时间是相同的，都是O(1)；

如果数量比较大，用vector有一定的优势，因为每次扩容的量更大。

巴特西

ArrayList和LinkedList、及Vector对比分析