Java List 源码分析：ArrayList、LinkedList、Vector 与 CopyOnWriteArrayList
· 阅读需 9 分钟
了解基本数据结构在java中很是重要，今天在这里我们来常用的List接口，以及不同的实现。
ArrayList
LinkedList
Vector
CopyOnWriteArrayList
etc...
环境：JDK1.8
阅读 List 源码应围绕随机访问、插入删除、迭代和并发修改展开。不同实现没有绝对优劣，选择时需要结合访问模式、数据规模和线程安全要求。
接口定义
List接口定义分为：查询，修改，批量修改，比较和hash，位置访问，搜索，迭代，视图。
查询操作方法
int size(); // 返回此列表元素数量
boolean isEmpty(); // 返回此列表是否为空
boolean contains(Object o); // 返回此列表是否包含o元素
Iterator<E> iterator(); // 返回此列表迭代器
Object[] toArray(); // 返回此列表转换后的数组
<T> T[] toArray(T[] a); // 返回此列表转换后的数组范型
修改操作方法
boolean add(E e); // 添加元素到此列表中
boolean remove(Object o); // 从此列表中移除指定元素
批量修改操作方法
boolean containsAll(Collection<?> c); // 是否包含指定列表所有元素
boolean addAll(Collection<? extends E> c); // 添加指定集合所有元素到此列表中
boolean addAll(int index, Collection<? extends E> c); // 从此列表指定index插入指定集合所有元素
boolean removeAll(Collection<?> c); // 从此列表中删除指定集合中包含的所有元素
boolean retainAll(Collection<?> c); // 仅保留此列表中包含在指定集合中的元素，相当于两个集合的交集
default void replaceAll(UnaryOperator<E> operator){...} // 按照指定一元操作替换此列表中所有元素, jdk8
default void sort(Comparator<? super E> c) {...} // 按照指定比较器对此列表元素进行排序
void clear(); // 清除此列表所有元素
比较和hash
boolean equals(Object o); // 比较两个列表是否相等
int hashCode(); // 计算此列表的hash值
位置访问操作
E get(int index); // 从此列表中获取指定index元素
E set(int index, E element); // 从此列表指定index插入指定元素
E remove(int index); // 从此列表移除指定index元素
搜索操作
int indexOf(Object o); // 从前往后搜索指定元素的位置
int lastIndexOf(Object o); // 从后往前搜索指定元素位置
列表迭代器
ListIterator<E> listIterator(); // 返回此列表中元素的列表迭代器
ListIterator<E> listIterator(int index); // 从指定index返回此列表中元素的列表迭代器
视图
List<E> subList(int fromIndex, int toIndex); // 返回子列表视图
default Spliterator<E> spliterator() {...} // 返回可分割迭代器 splitable iterator
ArrayList实现
首先ArrayList的默认容量为10
private static final int DEFAULT_CAPACITY = 10;
其次定义了存储数据的数组以及数组中元素个数
transient Object[] elementData;
private int size;
从这里可以看出，我们的ArrayList底层是一个数组实现的。
我们再看看构造方法
public ArrayList(int initialCapacity) {...} // 指定容量大小的构造器
public ArrayList() {...} // 无参构造器
public ArrayList(Collection<? extends E> c) {...} // 指定集合构造器
构造器干了些啥呢？
其实很简单，就是一些数据初始化
- 初始化elementData
- 计算size大小，如果elementData为空，则size为默认值0
再来看看我们上面列的那些操作都干了啥？
主要看add，remove，set
boolean add(E e);
public boolean add(E e) {
// 容量检查
ensureCapacityInternal(size + 1); // Increments modCount!!
// 设置元素
elementData[size++] = e;
return true;
}
- 计算elementData与最小容量size+1的大小
- 判断size+1与elementData.length大小，如果size+1 - elementData.length < 0 则不扩容，否则扩容
- 存放对象到elementData数组中，size并增加
E remove(int index);
public E remove(int index) {
// index范围检查
rangeCheck(index);
modCount++;
// 获取index索引对应的元素
E oldValue = elementData(index);
// 计算元素位置是否移动了，并调整元素位置
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将最后一个元素设置为null
elementData[--size] = null; // clear to let GC do its work
// 返回index对应的元素
return oldValue;
}
- index范围检查
- 获取elementData中index位置的元素
- 计算index是否小于elementData.length-1，如果是则进行一次元素位置调整。并将最后一个元素设置为null.
E set(int index, E element);
public E set(int index, E element) {
// index范围检查
rangeCheck(index);
// 获取指定index的元素
E oldValue = elementData(index);
// 覆盖index的元素为新元素
elementData[index] = element;
// 返回旧值
return oldValue;
}
- index范围检查
- 获取指定index的元素，并覆盖旧元素为新元素
- 返回旧元素
LinkedList实现
我们看看LinkedList属性
transient int size = 0; // 元素个数
transient Node<E> first; // 头节点
transient Node<E> last; // 尾节点
我们再来看看Node是什么？
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
这里我们可以看到LinkedList是使用Node节点实现，Node类似铁链的环一样，一个接着一个
再来看看构造器
public LinkedList() {}
public LinkedList(Collection<? extends E> c) {...}
指定集合构造器实际上是调用了addAll方法，这里我们直接从addAll说起
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 检查index范围
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// 找出当前节点，与前一个节点
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
// 追加节点
for (Object o : a) {
E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
// 更新最后一个节点
last = pred;
} else {
// 中间插入时，更新index节点的prev
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
解释一下public boolean addAll(int index, Collection<? extends E> c) {...}
第一种情况：
当index == size大小时，从尾部添加。
第二种情况：
当index < size大小时， 从中间插入。
我们依旧看看add，remove，set
public boolean add(E e) {
linkLast(e);
return true;
}
// 在最后一个节点上追加节点
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
这里还有一个Node node(int index); 这个主要是用来查询指定index的元素，时间复杂度为O(logn)
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
从这里我们可以得出以下结论
- ArrayList访问指定index的元素要比LinkedList快，看下面代码
ArrayList访问指定index的元素
elementData[index]
LinkedList访问指定index的元素
node(index)
Vector实现
Vector则是在ArrayList的基础上所有方法增加了synchronized关键字，是线程安全的集合。
CopyOnWriteArrayList实现
从名字可以看出CopyOnWriteArrayList的底层实现采用的数组，因为也是ArrayList。这个集合类也是线程安全的，那么我们来看看它是如何实现线程安全的。
首先在该类中增加了可重入锁
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array; // 数据存储
依旧，我们看看构造器
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
if (c.getClass() == CopyOnWriteArrayList.class)
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
elements = c.toArray();
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
setArray(elements);
}
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
final void setArray(Object[] a) {
array = a;
}
上述构造器完成的就是array的初始化。
我们来看看是如何做到添加和获取做到线程安全的。
首先我们看看add方法
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
这里可以看到，在添加新元素的时候会采用lock锁住当前方法。然后进行copy元素到新的数组中。
包括set，remove都进行了lock操作。
我们再看看get方法
public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}
看到没有，这里可没有加锁哦。我们再Vector中可以使用了synchronized关键字的。我们看看Vector的get。
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
在CopyOnWriteArrayList的get没有加锁是因为set的原因，在set的时候。每次都会生成一个新的数组，所以get时不用加锁。
这里可以看出CopyOnWriteArrayList的写性能应该不会太高。因为每次都要生成新的数组。
最后看看有哪些List是线程安全的
1. 使用CopyOnWriteArrayList
2. Collections.synchronizedList(new ArrayList())
3. 使用Vector
好了，今天的分享就到这里啦。谢谢你的阅读，喜欢的话，可以打赏一下哦。