【Java 集合】List接口 —— ArrayList 与 LinkedList 详解

List接口继承自Collection接口，是单列集合的一个重要分支。

在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，在程序中可以通过索引（类似于数组中的元素角标）来访问集合中的指定元素。另外，List集合还有一个特点就是元素有序，即元素的存入顺序和取出顺序一致。

表1 List集合常用方法

方法声明	功能描述
void add(int index,Object element)	将元素element插入在List集合的指定索引位置
boolean addAll(int index,Collection c)	将集合c包含的所有元素插入到List集合的指定索引位置
Object get(int index)	返回集合索引index处的元素
Object remove(int index)	删除index索引处的元素
Object set(int index, Object element)	将索引index处元素替换成element元素，并将替换后的元素返回
int indexOf(Object o)	返回对象o在List集合中首次出现的位置索引
int lastIndexOf(Object o)	返回对象o在List集合中最后一次出现的位置索引
List subList(int fromIndex, int toIndex)	返回从索引fromIndex（包括）到 toIndex（不包括）处所有元素集合组成的子集合
Object[] toArray()	将集合元素转换为数组
default void sort(Comparator<? super E> c)	根据指定的比较器规则对集合元素排序（JDK 8新方法）

其中sort(Comparator<? super E> c)方法是JDK 8新增的，用于对集合元素进行排序操作，该方法的参数是一个接口类型的比较器Comparator，可以通过前面讲解的Lambda表达式传入一个函数式接口作为参数，来指定集合元素的排序规则。

ArrayList集合

ArrayList是List接口的一个实现类，它是程序中最常见的一种集合。ArrayList会在内存中分配一个更大的数组来存储这些元素，因此可以将ArrayList集合看作一个长度可变的数组。

正是由于ArrayList内部的数据存储结构是数组形式，在增加或删除指定位置的元素时，会创建新的数组，效率比较低，因此不适合做大量的增删操作。但是，这种数组结构允许程序通过索引的方式来访问元素，因此使用ArrayList集合在遍历和查找元素时显得非常高效。

LinkedList集合

LinkedList集合内部包含有两个Node类型的first和last属性维护一个双向循环链表，在链表中的每一个元素都使用引用的方式来记住它的前一个元素和后一个元素，从而可以将所有的元素彼此连接起来。

正因为这样的存储结构，所以LinkedList集合对于元素的增删操作表现出很高的效率，LinkedList集合添加元素和删除元素的过程如图1所示。

表1 LinkedList中的特有方法

方法声明	功能描述
void add(int index, E element)	在此列表中指定的位置插入指定的元素。
void addFirst(Object o)	将指定元素插入集合的开头
void addLast(Object o)	将指定元素添加到集合的结尾
Object getFirst()	返回集合的第一个元素
Object getLast()	返回集合的最后一个元素
Object removeFirst()	移除并返回集合的第一个元素
Object removeLast()	移除并返回集合的最后一个元素
boolean offer(Object o)	将指定元素添加到集合的结尾
boolean offerFirst(Object o)	将指定元素添加到集合的开头
boolean offerLast(Object o)	将指定元素添加到集合的结尾
Object peek()	获取集合的第一个元素
Object peekFirst()	获取集合的第一个元素
Object peekLast()	获取集合的最后一个元素
Object poll()	移除并返回集合的第一个元素
Object pollFirst()	移除并返回集合的第一个元素
Object pollLast()	移除并返回集合的最后一个元素
void push(Object o)	将指定元素添加到集合的开头
Object pop()	移除并返回集合的第一个元素