ArrayList、LinkedList、Vector是集合中经常拿来比较和面试的一个问题，我这里简要概括一下他们的区别和实现原理。

存储结构

ArrayList和Vector是按照顺序将元素存储（从下表为0开始），删除元素时，删除操作完成后，需要使部分元素移位，默认的初始容量都是10.

ArrayList和Vector是基于数组实现的，LinkedList是基于双向链表实现的（含有头结点）。

线程安全性

ArrayList不具有有线程安全性，在单线程的环境中，LinkedList也是线程不安全的，如果在并发环境下使用它们，可以用Collections类中的静态方法synchronizedList(）对ArrayList和LinkedList进行调用即可。

Vector实现线程安全的，即它大部分的方法都包含关键字synchronized,但是Vector的效率没有ArraykList和LinkedList高。

扩容机制

从内部实现机制来讲，ArrayList和Vector都是使用Object的数组形式来存储的，当向这两种类型中增加元素的时候，若容量不够，需要进行扩容。ArrayList扩容后的容量是之前的1.5倍，然后把之前的数据拷贝到新建的数组中去。而Vector默认情况下扩容后的容量是之前的2倍。

Vector可以设置容量增量，而ArrayList不可以。在Vector中，有capacityIncrement：当大小大于其容量时，容量自动增加的量。如果在创建Vector时，指定了capacityIncrement的大小，则Vector中动态数组容量需要增加时，如果容量的增量大于0，则增加的是大小是capacityIncrement，如果增量小于0，则增大为之前的2倍。

在这里需要说一下可变长度数组的原理：当元素个数超过数组的长度时，会产生一个新的数组，将原数组的数据复制到新数组，再将新的元素添加到新数组中。

增删改查的效率

ArrayList和Vector中，从指定的位置检索一个对象，或在集合的末尾插入、删除一个元素的时间是一样的，时间复杂度都是O（1）。但是如果在其他位置增加或者删除元素花费的时间是O（n）,LinkedList中，在插入、删除任何位置的元素所花费的时间都是一样的，时间复杂度都为O（1），但是他在检索一个元素的时间复杂度为O（n）.

所以如果只是查找特定位置的元素或只在集合的末端增加移动元素，那么使用ArrayList或Vector都是一样的。如果是在指定位置的插入、删除元素，最好选择LinkedList

一.ArrayList

特性：

1.基于动态数组的数据结构，初始容量为10，容量不足时，在缺省的情况下自动增长原来的50%。

2.非线程安全。

3.允许Null元素。

二.LinkedList

特性：

1.底层的数据结构是双链表。

2.非线程安全。

3.允许Null元素。

三.Vector

特性：

1.基于动态数组的数据结构，初始容量为10，容量不足时，在缺省的情况下自动增长原来的一倍。

2.同步线程安全。

3.允许Null元素。

四.总结：

1.如果是非线程安全的话，可以使用ArrayList或LinkedList。这样可以节省同步耗费的开销。

2.如果只是查找特定位置的元素或者在集合的末尾插入、删除对象，可以使用ArrayList或Vector，他们开销的时间是一样的，可以用O(1)表示。如果在集合的其他位置插入、删除对象，他们开销的时间会呈线性的增长,可以用O(n-i)表示。因为ArrayList和Vector都是数组实现，所以在集合中间插入和删除需要移动后面所有的元素。LinkedList在插入、删除集合任何位置的元素所开销的时间都是一样的，可以用O(1)表示。因为LinkedList是用链表实现，在内存里是离散的(不连续)，里面的每一个元素都有下一个元素引用，所以不支持高效的随机元素访问，查询的时候比ArrayList和Vector慢，开销时间为O(i)，ArrayList和Vector查询开销的时间为O(1)。

备注：n表示集合元素的个数；i表示元素插入、删除和查询的索引位置。

https://blog.csdn.net/stemq/article/details/66476265?biz_id=102&utm_term=ArrayListLinkedListVector区别&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-2-66476265&spm=1018.2118.3001.4187

ArrayList,LinkedList和Vector都继承自List接口。ArrayList和Vector的底层是动态数组，LinkedList的底层是双向链表.

ArrayList和Vector的区别就是ArrayList是线程不安全的，Vector是线程安全的，Vector中的方法都是同步方法(synchronized),所以ArrayList的执行效率要高于Vector,它也是用的最广泛的一种集合。

1.从存储数据结构分析

ArrayList：数组

Vector：数组

LinkedList：双向链表

数组：可以根据下标快速查找，所以大部分情况下，查询快。但是如果要进行增删操作的时候，会需要移动修改元素后面的所有元素，所以增删的开销比较大，数组的对增删操作的执行效率低。而采用数组作为数据存储结构的ArrayList、Vector也存在这些特性，查询速度快（可以根据下标直接取，比迭代查找更快），增删慢。

链表：增加和删除元素方便，增加或删除一个元素，仅需处理结点间的引用即可。就像人手拉手连成一排，要增加或删除某个人只要附近的两个人换一个人牵手，对已经牵好手的人没影响。无论在哪里换人耗费的资源和时间都是一样的。但是查询不方便，需要一个个对比，无法根据下标直接查找。而采用链表结构存储的LinkedList也有这些特性，增删方便，查询慢(指的是随机查询，不是顺序查询)。

2.从继承上分析

 都实现了List接口，也就是说都实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”。数组结构根据下标取值很容易，LinkedList双向列表的实现也比较简单，通过计数索引值实现，从链表长度的1/2开始查找，下标大了就从表头开始找，小了就从表尾开始找。

3.从并发安全上分析

Vector：线程安全

ArrayList：非线程安全

LinkedList:非线程安全

4.数据增长分析

Vector：缺省的情况下，增长为原数组长度的一倍。说到缺省，说明他其实是可以自主设置初始化大小的。

ArrayList：自动增长原数组的50%。