List家族简介

背景

List是Collection framework中重要的一员,在平时的编程中,我也会经常用到,它可以简单的理解成一个变长的数组,数组中的每个元素的类型必须一致。在数据结构的概念里面,链表是可以动态添加删除的,由节点与指针组成的一组数据集合,包括了单向链表、双向链表、循环链表、带头节点的链表、十字链表等。在Java中,并没有实现那么多复杂的结构,它的实现类包括了ArrayList、LinkedList、Vector三大类,下面详细介绍各个实现类。

ArrayList

ArrayList是List家族最常用的一个类了,它是一个变长的数组,实际上它的内部实现也是通过一个对象数组实现的。它实现了List、RandomAccess、Cloneable、Serializable接口,这四个接口的含义是:

  • List代表的是一个有序的数组,顺序为插入时候的先后顺序,成员可以是基本数据类型和类,用户可以通过下标访问成员,也可以查询成员是否存在
  • RandomAccess接口比较有意思,它用来修饰实现了List接口的类,也就是说实现该接口必须先实现List接口。它表示该类可以进行快速的随机访问。具体的含义可以理解为代码段
1
2
for (int i=0, n=list.size(); i < n; i++)
list.get(i);

的运行速度比下面的代码段快

1
2
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
  • Cloneable接口代表的是该类可以进行复制,并保留原有的属性值,实现该接口的类必须有一个public的clone方法
  • Serializable接口是序列化中的关键,只有实现了该接口的类才可以正常的进行序列化和反序列化

上面说到ArrayList内部实现是一个数组,那么它的长度是多少呢,它又是怎么实现变长的呢,数组的元素类型又是什么呢?

1
2
3
4
5
6
7
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access

上面的成员变量就是ArrayList中实际存元素的数组,通过注释我们也可以看出,ArrayList有一个默认的长度,在JDK8中为10,也可以通过构造函数传入默认的长度。ArrayList在添加元素的时候,会保证当前的数组有剩余空间,通过ensureCapacityInternal(size + 1); // Increments modCount!!来实现,调用该方法保证当前数组长度大于等于size+1,方法内部调用
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); calculateCapacity方法返回的是默认容量和传入的minCapacity间的最大值,ensureExplicitCapacity方法会判断minCapacity是否大于elementData的长度,如果小于,调用grow方法,对elementData扩容。grow方法默认扩充原elementData的一半长度(int newCapacity = oldCapacity + (oldCapacity >> 1);),如果newCapacity仍然小于minCapacity的话,则newCapacity = minCapacity;

在ensureExplicitCapacity方法的调用第一句有一句有趣的代码为modCount++,这个属性我最开始以为是类似于魔数的含义,但最后发现并不是,它的定义语句位于AbstractList中,通过注释可以看到,它的存在是为了解决并发访问的问题,由于ArrayList没有加锁,因此当我们返回它的Iterator之后,一旦对该List进行元素的增删改,就会发生并发错误,ArrayList通过modCount来避免该现象,当ArrayList发生了结构变化时(增删改、自排序),modCount会自增,这就会于返回Iterator时的值不同,因此直接抛出ConcurrentModificationException异常,这是Java实现的一个fail-fast机制,此时我们可以重新返回新的Iterator元素,重新进行数据的遍历。在ArrayList的序列化和反序列化中,modCount也扮演了重要的角色,在调用writeObject方法时,写完对象之后,会判断modCount和写之前的值是否一致,若不一致,也会抛出ConcurrentModificationException异常。如果我们在使用ArrayList时候,需要考虑并发访问,可以考虑使用List list = Collections.synchronizedList(new ArrayList(...));返回一个同步对象了,然后对该同步对象进行并发操作。

ArrayList常用的方法介绍如下:

  • add方法向数组最后添加一个元素,该方法也可以将元素添加到指定的位置
  • remove方法可以删除指定位置的元素,也可以删除与指定元素相同的元素,也可以传入一个下标区间,删除该区间内的元素
  • get方法返回指定位置的元素,set方法修改指定位置的元素
  • isEmpty方法判断是否为空
  • iterator方法返回一个遍历对象,该对象可以通过next方法遍历数组
  • sort方法可以传入一个comparator对象实现数组的自排序,comparator可以定义排序规则
  • subList可以返回指定区间的子数组,listIterator可以返回指定位置开始的子Iterator

ArrayList中通过iterator方法返回一个遍历对象,该对象的类原型是一个ArrayList中的内部类Itr,该类实现了Iterator接口,可以通过next方法遍历数组,并可以通过remove删除当前位置的元素,forEachRemaining方法传入一个Consumer,可以对当前位置之后的所有元素执行Consumer的动作,在特定的场景下可以应用。通过Itr对象进行的元素更改,对原ArrayList会产生影响。上面说到的modCount在Itr中重要的应用,用以防止在Itr对象的生命周期中,原始ArrayList没有发生结构上的变化,若发生了变化,则抛出异常,但通过Itr的remove方法进行的修改不会抛出异常。Itr的remove方法源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

expectedModCount是一个Itr对象的属性,在该对象创建的时候赋值为modCount,checkForComodification方法判断两值是否相等,若不相等,则抛出异常。remove方法调用的ArrayList的remove方法删除指定位置(lastRet)的元素,删除该元素后,cursor指向了lastRet位置,由于该位置元素已经被删除,因此指向了原位置的下一元素,lastRet指向-1,因此,Itr的remove方法不可以连续执行。

LinkedList

LinkedList是一个第一眼看上去很熟悉,但用的时候却总是想不起来的一个角色,对于我来说,它的使用频率甚至少于Stack(Vector的子类),但因为它的名字里面带了List,因此我在第二位分析它。

LinkedList是一个双向链表,它实现了List、Deque、Cloneable、Serializable接口,其他三个都在ArrayList中进行了分析,这里重点介绍Deque接口。Deque光看名字好像跟Queue有点关系,但又不完全相同,实际上它是Queue的子接口,它是一个支持从头、尾两端进行添加元素和删除元素的队列,也就是“double ended queue”。它的添加、删除两头元素的方法都有两种形式,一种是遇到错误的时候抛出异常、一种是遇到错误返回特定的值(null或false),下表是这些方法的详细说明。

/ 抛出异常 返回特定值 抛出异常 返回特定值
添加 addFirst(e) offerFirst(e) addLast(e) offerLast(e)
删除 removeFirst() pullFirst() removeLast() pullLast()
获取值 getFirst() peekFirst() getLast() peekLast()

由于Deque可以在两端增删元素,因此也可以用作栈来使用,实际上,它也提供了相应的方法,push、pop、peek、它们与上面的方法的对应关系为

Stack方法 Deque对应的方法
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()

由此可见,当被用作栈的时候,栈顶为Deque的第一个元素。

LinkedList是双向链表,与ArrayList相比,它或许更有资格称为“List”,因为,它的内部实现就是通过一组节点和节点的引用来构成的,节点类是一个内部类Node,定义如下:

1
2
3
4
5
6
7
8
9
10
11
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;
}
}

它通过一个next指向下一个节点,通过prev指向前一个节点。LinkedList通过保存两个节点first、last来记录链表的头部和尾部,通过size属性来记录当前链表的长度。当需要添加一个元素的时候,LinkedList将该节点添加到last之后,当需要删除一个节点的时候,LinkedList从first节点向后遍历,逐一比对,删除第一个相同的节点(equals返回true)。

当调用set、get(index) 方法的时候,LinkedList会根据index来选择比较近的路径找到对应节点(从头向尾或者从尾向头),通过调用node(index)返回对应的节点。该方法的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
}

可以看到,当index小于size的一半时,从first节点向后,大于时,从last节点从后向前。

LinkedList中有个内部类ListItr,它是ListIterator的一个实现类,ListIterator提供了双向遍历数组的能力,这也是LinkedLIst的能力,该Iterator返回node节点,next方法也是通过Node的next“指针”来进行的,它和ArrayList中的Itr一样,并不会返回一个全新的对象,对它的元素的删除、添加是直接对原LinkedList中的节点的操作,因此也需要防止并发错误,也是通过了modCount来实现的,具体原理与ArrayList中相同。DescendingIterator是一个从后向前遍历的单向Iterator,内部实现使用了ListIterator。

Vector

Vector也是一个第一眼看来很眼熟,但不怎么常用的类(在C++中可能更常用些),这主要源于它很大程度上与ArrayList的功能相同,内部也是通过对象数组来进行元素的存储。它与ArrayList的主要不同有两点:

  • 提供了capacityIncrement来控制当数组空间不足时,新增的容量,这在需要严格控制内存的使用的应用上有时可以派上用场,但鉴于Java应用大多数跑在服务器上,所以似乎用处不大
  • 它是线程安全的。这在多线程编程时,自己不想实现类似结构的时候,可以临时使用Vector来代替。但由于其内部实现是通过在方法上直接修饰synchronized来形成同步方法,因此并发度并不高,因此使用场景也比较有限。

Vector也提供了Itr和ListItr两种遍历对象来进行数组的遍历,其内部实现逻辑与ArrayList相同,也是通过一个cursor记录当前的遍历位置,在涉及到元素修改的代码中,添加了synchronized (Vector.this)来确保元素的操作是线程安全的。

Stack

Stack跟List家族的关系并不大,在这里介绍主要是因为它是Vector的子类,但它却不是数组,而是栈(LIFO)。栈顶位于Vector的最后一个位置,添加和删除都是从该位置进行的。Stack提供了栈的几个基本的操作,包括push、pop、peek、empty查看是否为空,search返回元素距栈顶的距离。

Stack只是栈的一个最基本的实现,更加具体的实现由Deque和它的实现类提供,在实际使用中应该倾向于使用该类,如:

1
Deque<Integer> stack = new ArrayDeque<Integer>();

总结

List家族的几员大将已经分析完毕,还剩一个CopyOnWriteArrayList由于涉及更多关于线程的知识,暂时不在这里讨论,通过总结List中的几个常用类,对它们的使用场景有了更深的认识,并了解了modCount机制,这是一个简单避免线程不安全的方法,在编程中是一个不错的小技巧。List中动态分配内存空间的思想也对于高效编程有很大的帮助,理解它们有助于编写出GC友好的代码。