毫无疑问，List是一种非常基础的数据结构，翻译过来就是列表。正如它的名字所示，List表示的是一个有序(插入顺序)的元素序列。在Java的集合框架中，List是作为顶级接口Collection的直接子类接口存在，因此，List分支是集合框架中最简单、最常用的分支。

List概述

List分支作为集合框架中最简单、最常用的分支，其在集合框架中的位置可以直接参看下图：

仔细观察和分析此图，你会发现JDK中对于List接口的实现由三种类型：ArrayList、Vector 和 LinkedList。当我们谈论List的时候，我们可以用它与Set来做比较，集合框架中的Set代表一群无序和唯一的元素集合。 仔细观察上图可知，集合框架中的List接口具有多达三个实现类。由继承机制可知，它们在很多方面都是非常相似的，比如有序、用法等。它们之间最大的区别是它们的内部实现方式和细节，不同的实现方式和细节造就了它们之间巨大的性能差异和用法差异。

1. ArrayList 是Java语言对于动态数组的一个实现。当不断地添加新的元素到ArrayList集合中时，该集合的底层数组的长度就会动态的增长，以便能容纳新添加的元素。至于ArrayList的底层数组长度的动态增长策略，在不同的JDK实现和版本中是不同的，最常见的策略是新增 %50，具体请参看源码。正因为ArrayList的底层实现是数组，其带来的一个特性是：它的元素可以通过 getter(index) 和 setter(index) 方法直接访问，而且性能特别好。
2. LinkedList 的底层实现是基于 双向队列(double linked list)。熟悉数据结构的读者应该可以猜到：LinkedList 对于新增和删除元素的操作在性能上远远优于 ArrayList。但是，它的缺点在于：其 getter(index) 方法和 setter(index) 方法的性能很差，时间复杂度是 O(n)。
3. Vector 与 ArrayList 唯一的区别是：它是同步的(synchronized)，线程安全。

性能对比

1. 对于ArrayList，add/remove的时间复杂度是 O(n)；但在尾部操作是 O(1) 。
2. 对于LinkedList，add/remove的时间复杂度是 O(n)；但在尾部和头部操作的是 O(1) 。

性能测试

为了实际测验三种List的add、get和remove的性能，我们可以使用如下的代码片段：

1
2
3
4
5
6
7
8

ArrayList arrayList = new ArrayList();
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("duration : " + duration);

此处只给出测验ArrayList的add操作的代码，但是测验LinkedList和其他操作的代码是类似，读者可自行修改代码进行测验。测验的结果表明： 在add和remove操作时，LinkedList的性能远优于ArrayList。在get操作时，ArrayList的性能优于LinkedList。经过性能对比和性能的测试，我们可以总结出如何在它们之间做出选择。通常使用ArrayList，但是LinkedList在如下场景时更合适：

1. 随机访问集合元素的次数不是很频繁。
2. 对集合有大量的add/remove操作需求。

总结

对比Vector和ArrayList，如果程序本身就是线程安全的，为了更好的性能，应该选择ArrayList。当添加新的元素到集合时，Vector和ArrayList都需要更多的空间来存储新元素，但是它们的增长策略是不一样的：Vector的增长幅度是 100%；ArrayList的增长幅度是 50%。对于LinkdedList而言，其不仅实现了List接口，还实现了Queue接口，这个Queue接口给LinkdedList带来了更多的访问和操作元素的方法，比如 offer(), peek(), poll() 等。 对于ArrayList而言，如果使用不含参数的构造函数新建一个ArrayList对象，该对象的起始大小是比较小的，只有10。我们都知道对象的动态增长导致的底层数组重写分配和复制是一个非常耗时的操作。所以，对于可以预估ArrayList大小的应用场景，应该指定ArrayList对象的初始大小，从而提供性能。

原文地址

Java中ArrayList、LinkedList和Vector的联系与区别