ArrayList、LinkedList、Vector区别

以下资料整理自互联网，仅用于个人学习。

---

继承结构：

Collection

├------List

├----LinkedList

├----ArrayList

├----Vector

一、ArrayList

类定义：public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable

特性：

1、可变大小的数组

2、非线程安全

3、初始容量为10，容量不足时，缺省情况下自动增长原来的50%

4、允许null元素

二、LinkedList

类定义：public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>,  Deque<E>,  Cloneable,  Serializable

特性：

1、双链表

2、非线程安全

3、在添加和删除元素元素时具有比ArrayList更好的性能

4、LinkedList还实现了Queue接口（非直接实现，是通过实现Queue的子接口Deque间接实现Queue），该接口比List提供了更多方法。包括从尾部添加元素：offer(E)、返回第一个元素但不出队:peek()、返回第一个元素并出队：poll()等

5、允许null元素

可通过如下方式转换为同步的List：

List list= Collections.synchronizedList(newLinkedList()); 

三、Vector

类定义：public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess,  Cloneable,  Serializable

特性：

1、与ArrayList类似，但属于同步类型，多了线程安全

2、初始容量为10，容量不足时，缺省情况下自动增长原来一倍

3、允许null元素

ArrayList、LinkedList、Vector的底层实现和区别

从同步性来看，ArrayList和LinkedList是不同步的，而Vector是同步的。当然，也可以通过一些办法包装ArrayList和LinkedList，使之达到同步，但效率可能会有所降低。

从内部实现机制来讲ArrayList和Vector都是使用Object的数组形式来存储的。

ArrayList和Vector中，从指定位置检索一个对象，或者在末尾插入、删除一个对象的时间都是O(1)，但是在集合其他位置增加或者删除元素花费的时间会呈线性增长O(n-i)，n代表集合中元素个数，i代表元素增加或移除元素的索引位置，因为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行(n-i)个对象的位移操作。LinkedList底层是由双向循环链表实现的，LinkedList在插入、删除集合中任何位置的元素所花费的时间都是一样的O(1)，但它在索引一个元素的时候比较慢，为O(i)，其中i是索引的位置。