Java 容器之 List
Java 容器之 List
List
是Collection
的子接口,其中可以保存各个重复的内容。
List 简介
List
是一个接口,它继承于 Collection
的接口。它代表着有序的队列。
AbstractList
是一个抽象类,它继承于 AbstractCollection
。AbstractList
实现了 List
接口中除 size()
、get(int location)
之外的函数。
AbstractSequentialList
是一个抽象类,它继承于 AbstractList
。AbstractSequentialList
实现了“链表中,根据 index 索引值操作链表的全部函数”。
ArrayList 和 LinkedList
ArrayList
、LinkedList
是 List
最常用的实现。
ArrayList
基于动态数组实现,存在容量限制,当元素数超过最大容量时,会自动扩容;LinkedList
基于双向链表实现,不存在容量限制。ArrayList
随机访问速度较快,随机插入、删除速度较慢;LinkedList
随机插入、删除速度较快,随机访问速度较慢。ArrayList
和LinkedList
都不是线程安全的。
Vector 和 Stack
Vector
和 Stack
的设计目标是作为线程安全的 List
实现,替代 ArrayList
。
Vector
-Vector
和ArrayList
类似,也实现了List
接口。但是,Vector
中的主要方法都是synchronized
方法,即通过互斥同步方式保证操作的线程安全。Stack
-Stack
也是一个同步容器,它的方法也用synchronized
进行了同步,它实际上是继承于Vector
类。
ArrayList
ArrayList 从数据结构角度来看,可以视为支持动态扩容的线性表。
ArrayList 要点
ArrayList
是一个数组队列,相当于动态数组。**ArrayList
默认初始容量大小为 10
,添加元素时,如果发现容量已满,会自动扩容为原始大小的 1.5 倍**。因此,应该尽量在初始化 ArrayList
时,为其指定合适的初始化容量大小,减少扩容操作产生的性能开销。
ArrayList
定义:
1 | public class ArrayList<E> extends AbstractList<E> |
从 ArrayList 的定义,不难看出 ArrayList 的一些基本特性:
ArrayList
实现了List
接口,并继承了AbstractList
,它支持所有List
的操作。ArrayList
实现了RandomAccess
接口,支持随机访问。RandomAccess
是一个标志接口,它意味着“只要实现该接口的List
类,都支持快速随机访问”。在ArrayList
中,我们即可以通过元素的序号快速获取元素对象;这就是快速随机访问。ArrayList
实现了Cloneable
接口,默认为浅拷贝。ArrayList
实现了Serializable
接口,支持序列化,能通过序列化方式传输。ArrayList
是非线程安全的。
ArrayList 原理
ArrayList 的数据结构
ArrayList 包含了两个重要的元素:elementData
和 size
。
1 | // 默认初始化容量 |
size
- 是动态数组的实际大小。elementData
- 是一个Object
数组,用于保存添加到ArrayList
中的元素。
ArrayList 的序列化
ArrayList
具有动态扩容特性,因此保存元素的数组不一定都会被使用,那么就没必要全部进行序列化。为此,ArrayList
定制了其序列化方式。具体做法是:
- 存储元素的
Object
数组(即elementData
)使用transient
修饰,使得它可以被 Java 序列化所忽略。 ArrayList
重写了writeObject()
和readObject()
来控制序列化数组中有元素填充那部分内容。
:bulb: 不了解 Java 序列化方式,可以参考:Java 序列化
ArrayList 构造方法
ArrayList 类实现了三个构造函数:
- 第一个是默认构造方法,ArrayList 会创建一个空数组;
- 第二个是创建 ArrayList 对象时,传入一个初始化值;
- 第三个是传入一个集合类型进行初始化。
当 ArrayList 新增元素时,如果所存储的元素已经超过其当前容量,它会计算容量后再进行动态扩容。数组的动态扩容会导致整个数组进行一次内存复制。因此,初始化 ArrayList 时,指定数组初始大小,有助于减少数组的扩容次数,从而提高系统性能。
1 | public ArrayList() { |
ArrayList 访问元素
ArrayList
访问元素的实现主要基于以下关键性源码:
1 | // 获取第 index 个元素 |
实现非常简单,其实就是**通过数组下标访问数组元素,其时间复杂度为 O(1)**,所以很快。
ArrayList 添加元素
ArrayList
添加元素有两种方法:一种是添加元素到数组末尾,另外一种是添加元素到任意位置。
1 | // 添加元素到数组末尾 |
两种添加元素方法的不同点是:
- 添加元素到任意位置,会导致在该位置后的所有元素都需要重新排列;
- 而添加元素到数组末尾,在没有发生扩容的前提下,是不会有元素复制排序过程的。
两种添加元素方法的共同点是:添加元素时,会先检查容量大小,如果发现容量不足,会自动扩容为原始大小的 1.5 倍。
ArrayList
添加元素的实现主要基于以下关键性源码:
1 | private void ensureCapacityInternal(int minCapacity) { |
ArrayList
执行添加元素动作(add
方法)时,调用 ensureCapacityInternal
方法来保证容量足够。
- 如果容量足够时,将数据作为数组中
size+1
位置上的元素写入,并将size
自增 1。 - 如果容量不够时,需要使用
grow
方法进行扩容数组,新容量的大小为oldCapacity + (oldCapacity >> 1)
,也就是旧容量的 1.5 倍。扩容操作实际上是调用Arrays.copyOf()
把原数组拷贝为一个新数组,因此最好在创建ArrayList
对象时就指定大概的容量大小,减少扩容操作的次数。
ArrayList 删除元素
ArrayList
的删除方法和添加元素到任意位置方法有些相似。
ArrayList
在每一次有效的删除操作后,都要进行数组的重组,并且删除的元素位置越靠前,数组重组的开销就越大。具体来说,ArrayList
会**调用 System.arraycopy()
将 index+1
后面的元素都复制到 index
位置上。
1 | public E remove(int index) { |
ArrayList 的 Fail-Fast
ArrayList
使用 modCount
来记录结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作,或者是调整内部数组的大小,仅仅只是设置元素的值不算结构发生变化。
在进行序列化或者迭代等操作时,需要比较操作前后 modCount
是否改变,如果发生改变,ArrayList
会抛出 ConcurrentModificationException
。
1 | private void writeObject(java.io.ObjectOutputStream s) |
LinkedList
LinkedList 从数据结构角度来看,可以视为双链表。
LinkedList 要点
LinkedList
基于双链表结构实现。由于是双链表,所以顺序访问会非常高效,而随机访问效率比较低。
LinkedList
定义:
1 | public class LinkedList<E> |
从 LinkedList
的定义,可以得出 LinkedList
的一些基本特性:
LinkedList
实现了List
接口,并继承了AbstractSequentialList
,它支持所有List
的操作。LinkedList
实现了Deque
接口,也可以被当作队列(Queue
)或双端队列(Deque
)进行操作,此外,也可以用来实现栈。LinkedList
实现了Cloneable
接口,默认为浅拷贝。LinkedList
实现了Serializable
接口,支持序列化。LinkedList
是非线程安全的。
LinkedList 原理
LinkedList 的数据结构
LinkedList
内部维护了一个双链表。
LinkedList
通过 Node
类型的头尾指针(first
和 last
)来访问数据。
1 | // 链表长度 |
size
- 表示双链表中节点的个数,初始为 0。first
和last
- 分别是双链表的头节点和尾节点。
Node
是 LinkedList
的内部类,它表示链表中的元素实例。Node 中包含三个元素:
prev
是该节点的上一个节点;next
是该节点的下一个节点;item
是该节点所包含的值。
1 | private static class Node<E> { |
LinkedList 的序列化
LinkedList
与 ArrayList
一样也定制了自身的序列化方式。具体做法是:
- 将
size
(双链表容量大小)、first
和last
(双链表的头尾节点)修饰为transient
,使得它们可以被 Java 序列化所忽略。 - 重写了
writeObject()
和readObject()
来控制序列化时,只处理双链表中能被头节点链式引用的节点元素。
LinkedList 访问元素
LinkedList
访问元素的实现主要基于以下关键性源码:
1 | public E get(int index) { |
获取 LinkedList
第 index 个元素的算法是:
- 判断 index 在链表前半部分,还是后半部分。
- 如果是前半部分,从头节点开始查找;如果是后半部分,从尾结点开始查找。
LinkedList
这种访问元素的性能是 O(N)
级别的(极端情况下,扫描 N/2 个元素);相比于 ArrayList
的 O(1)
,显然要慢不少。
推荐使用迭代器遍历 LinkedList
,不要使用传统的 for
循环。注:foreach 语法会被编译器转换成迭代器遍历,但是它的遍历过程中不允许修改 List
长度,即不能进行增删操作。
LinkedList 添加元素
LinkedList
有多种添加元素方法:
add(E e)
:默认添加元素方法(插入尾部)add(int index, E element)
:添加元素到任意位置addFirst(E e)
:在头部添加元素addLast(E e)
:在尾部添加元素
1 | public boolean add(E e) { |
LinkedList
添加元素的实现主要基于以下关键性源码:
1 | private void linkFirst(E e) { |
算法如下:
- 将新添加的数据包装为
Node
; - 如果往头部添加元素,将头指针
first
指向新的Node
,之前的first
对象的prev
指向新的Node
。 - 如果是向尾部添加元素,则将尾指针
last
指向新的Node
,之前的last
对象的next
指向新的Node
。
LinkedList 删除元素
LinkedList
删除元素的实现主要基于以下关键性源码:
1 | public boolean remove(Object o) { |
算法说明:
- 遍历找到要删除的元素节点,然后调用
unlink
方法删除节点; unlink
删除节点的方法:- 如果当前节点有前驱节点,则让前驱节点指向当前节点的下一个节点;否则,让双链表头指针指向下一个节点。
- 如果当前节点有后继节点,则让后继节点指向当前节点的前一个节点;否则,让双链表尾指针指向上一个节点。
List 常见问题
Arrays.asList 问题点
在业务开发中,我们常常会把原始的数组转换为 List
类数据结构,来继续展开各种 Stream
操作。通常,我们会使用 Arrays.asList
方法可以把数组一键转换为 List
。
【示例】Arrays.asList 转换基本类型数组
1 | int[] arr = { 1, 2, 3 }; |
【输出】
1 | 11:26:33.214 [main] INFO io.github.dunwu.javacore.container.list.AsList示例 - list:[[I@ae45eb6] size:1 class:class [I |
数组元素个数为 3,但转换后的列表个数为 1。
由此可知, Arrays.asList
第一个问题点:不能直接使用 Arrays.asList
来转换基本类型数组。
其原因是:Arrays.asList
方法传入的是一个泛型 T 类型可变参数,最终 int
数组整体作为了一个对象成为了泛型类型 T:
1 | public static <T> List<T> asList(T... a) { |
直接遍历这样的 List
必然会出现 Bug,修复方式有两种,如果使用 Java8 以上版本可以使用 Arrays.stream
方法来转换,否则可以把 int
数组声明为包装类型 Integer
数组:
【示例】转换整型数组为 List 的正确方式
1 | int[] arr1 = { 1, 2, 3 }; |
【示例】Arrays.asList 转换引用类型数组
1 | String[] arr = { "1", "2", "3" }; |
抛出 java.lang.UnsupportedOperationException
。
抛出异常的原因在于 Arrays.asList
第二个问题点:**Arrays.asList
返回的 List
不支持增删操作**。Arrays.asList
返回的 List 并不是我们期望的 java.util.ArrayList
,而是 Arrays
的内部类 ArrayList
。
查看源码,我们可以发现 Arrays.asList
返回的 ArrayList
继承了 AbstractList
,但是并没有覆写 add
和 remove
方法。
1 | private static class ArrayList<E> extends AbstractList<E> |
Arrays.asList
第三个问题点:**对原始数组的修改会影响到我们获得的那个 List
**。ArrayList
其实是直接使用了原始的数组。
解决方法很简单,重新 new
一个 ArrayList
初始化 Arrays.asList
返回的 List
即可:
1 | String[] arr = { "1", "2", "3" }; |
List.subList 问题点
List.subList 直接引用了原始的 List,也可以认为是共享“存储”,而且对原始 List 直接进行结构性修改会导致 SubList 出现异常。
1 | private static List<List<Integer>> data = new ArrayList<>(); |
出现 OOM 的原因是,循环中的 1000 个具有 10 万个元素的 List 始终得不到回收,因为它始终被 subList 方法返回的 List 强引用。
解决方法是:
1 | private static void oomfix() { |
【示例】子 List 强引用原始的 List
1 | private static void wrong() { |
抛出 java.util.ConcurrentModificationException
。
解决方法:
一种是,不直接使用 subList 方法返回的 SubList,而是重新使用 new ArrayList,在构造方法传入 SubList,来构建一个独立的 ArrayList;
另一种是,对于 Java 8 使用 Stream 的 skip 和 limit API 来跳过流中的元素,以及限制流中元素的个数,同样可以达到 SubList 切片的目的。
1 | //方式一: |