毫无疑问，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 的联系与区别