深入浅出分析 Collection 中的 List 接口

在前面的文章集合系列中，我相信大部分朋友对 Java 容器整体架构都有了初步的了解，那么本文主要是想详细的介绍以下 List 接口实现类之间的区别！

01、List 简介

“

List 的数据结构就是一个序列，存储内容时直接在内存中开辟一块连续的空间，然后将空间地址与索引对应。

以下是 List 集合简易架构图

由图中的继承关系，可以知道，ArrayList、LinkedList、Vector、Stack 都是List 的四个实现类。

AbstractCollection 是一个抽象类，它唯一实现 Collection 接口的类。AbstractCollection 主要实现了 toArray()、toArray(T[] a)、remove() 等方法。

AbstractList 也是一个抽象类，它继承于 AbstractCollection。AbstractList 实现 List 接口中除 size()、get(int location) 之外的函数，比如特定迭代器 ListIterator。

AbstractSequentialList 是一个抽象类，它继承于 AbstractList。AbstractSequentialList 实现了“链表中，根据 index 索引值操作链表的全部函数”。

ArrayList 是一个动态数组，它由数组实现。随机访问效率高，随机插入、随机删除效率低。

LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList 随机访问效率低，但随机插入、随机删除效率高。

Vector 也是一个动态数组，和 ArrayList 一样，也是由数组实现。但是ArrayList 是非线程安全的，而 Vector 是线程安全的。

Stack 是栈，它继承于 Vector。它的特性是：先进后出(FILO, First In Last Out)。

下面对各个实现类进行方法剖析！

02、ArrayList

“

ArrayList 实现了 List 接口，也是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入 null 元素，底层通过数组实现。除该类未实现同步外，其余跟 Vector 大致相同。

在 Java1.5 之后，集合还提供了泛型，泛型只是编译器提供的语法糖，方便编程，对程序不会有实质的影响。因为所有的类都默认继承至 Object，所以这里的数组是一个 Object 数组，以便能够容纳任何类型的对象。

2.1、get 方法

get() 方法同样很简单，先判断传入的下标是否越界，再获取指定元素。

2.2、set 方法

set() 方法也非常简单，直接对数组的指定位置赋值即可。

2.3、add 方法

ArrayList 添加元素有两个方法，一个是 add(E e)，另一个是 add(int index, E e)。这两个方法都是向容器中添加新元素，可能会出现容量（capacity）不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过 grow() 方法完成的。

grow方法实现

添加元素还有另外一个 addAll() 方法，addAll() 方法能够一次添加多个元素，根据位置不同也有两个方法，一个是在末尾添加的 addAll(Collection c)方法，一个是从指定位置开始插入的 addAll(int index, Collection c)方法。

不同点：addAll() 的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关，时间复杂度是线性增长！

2.4、remove 方法

remove() 方法也有两个版本，一个是 remove(int index) 删除指定位置的元素；另一个是 remove(Object o)，通过 o.equals(elementData[index]) 来删除第一个满足的元素。

需要将删除点之后的元素向前移动一个位置。需要注意的是为了让 GC 起作用，必须显式的为最后一个位置赋 null 值。

remove(int index) 方法

remove(Object o) 方法

03、LinkedList

“

在上篇文章中，我们知道 LinkedList 同时实现了 List 接口和 Deque 接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。

LinkedList 底层通过双向链表实现，通过 和 引用分别指向链表的第一个和最后一个元素，注意这里没有所谓的哑元（某个参数如果在子程序或函数中没有用到，那就被称为哑元），当链表为空的时候 和 都指向 null。

3.1、get 方法

get() 方法同样很简单，先判断传入的下标是否越界，再获取指定元素。

3.2、set 方法

set(int index, E element) 方法将指定下标处的元素修改成指定值，也是先通过 node(int index) 找到对应下表元素的引用，然后修改 Node 中 item 的值。

3.3、add 方法

同样的，add() 方法有两方法，一个是 add(E e)，另一个是 add(int index, E element)。

add(E e) 方法

该方法在 LinkedList 的末尾插入元素，因为有 last 指向链表末尾，在末尾插入元素的花费是常数时间，只需要简单修改几个相关引用即可。

add(int index, E element)方法

该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。

具体分成两步，1.先根据 index 找到要插入的位置；2.修改引用，完成插入操作。

同样的，添加元素还有另外一个 addAll() 方法，addAll() 方法能够一次添加多个元素，根据位置不同也有两个方法，一个是在末尾添加的 addAll(Collection c) 方法，另一个是从指定位置开始插入的 addAll(int index, Collection c) 方法。

里面也 for 循环添加元素，addAll() 的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关，时间复杂度是线性增长！

3.4、remove 方法

同样的，remove() 方法也有两个方法，一个是删除指定下标处的元素 remove(int index)，另一个是删除跟指定元素相等的第一个元素 remove(Object o)。

两个删除操作都是，1.先找到要删除元素的引用；2.修改相关引用，完成删除操作。

remove(int index) 方法

通过下表，找到对应的节点，然后将其删除

remove(Object o) 方法

通过 equals 判断找到对应的节点，然后将其删除

删除操作都是通过 方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

04、Vector

Vector 类属于一个挽救的子类，早在 jdk1.0 的时候，就已经存在此类，但是到了 jdk1.2 之后重点强调了集合的概念，所以，先后定义了很多新的接口，比如 ArrayList、LinkedList，但考虑到早期大部分已经习惯使用 Vector 类，所以，为了兼容性， java 的设计者，就让 Vector 多实现了一个 List 接口，这才将其保留下来。

在使用方面，Vector 的 、、、 方法实现，与ArrayList 基本相同，不同的是 Vector 在方法上加了线程同步锁 ，所以，执行效率方面，会比较慢！

4.1、get 方法

4.2、set 方法

4.3、add 方法

4.4、remove 方法

05、Stack

在 Java 中 Stack 类表示后进先出（LIFO）的对象堆栈。栈是一种非常常见的数据结构，它采用典型的先进后出的操作方式完成的；在现实生活中，手枪弹夹的子弹就是一个典型的后进先出的结构。

在使用方面，主要方法有 、、。

5.1、push 方法

push 方法表示，向栈中添加元素

5.2、peek 方法

peek 方法表示，查看栈顶部的对象，但不从栈中移除它

5.3、pop 方法

pop 方法表示，移除元素，并将要移除的元素方法

关于 Java 中 Stack 类，有很多的质疑声，栈更适合用队列结构来实现，这使得 Stack 在设计上不严谨，因此，官方推荐使用 Deque 下的类来实现栈！

06、总结

ArrayList (动态数组结构)，查询快（随意访问或顺序访问），增删慢，但在末尾插入，速度与 LinkedList 相差无几！

LinkedList（双向链表结构），查询慢，增删快！

Vector（动态数组结构），相比 ArrayList 都慢，被 ArrayList 替代，基本不在使用。优势是线程安全（函数都是 synchronized），如果需要在多线程下使用，推荐使用并发容器中的工具类来操作，效率高！

Stack（栈结构）继承于 Vector，数据是先进后出，基本不在使用，如果要实现栈，推荐使用 Deque 下的 ArrayDeque，效率比 Stack 高！

07、参考

1、JDK1.7 & JDK1.8 源码

2、CarpenterLee - Java集合分析

3、博客园 - 朽木 - ArrayList、LinkedList、Vector、Stack的比较