Java List

———— JDK 1.8
words: 3k    views:    time: 12min
Java SE
List

根据实现的接口可以将java容器分为Collection和Map两部分，其中还可以按照是否线程安全来继续划分，大部分线程安全的实现在JDK1.5之后新增的concurrent包中。

本文先讨论Collection中比较基础的两个List实现ArrayList和LinkedList，前者通过数组，后者通过链表。数组的好处在于有位置索引，可以按下标任意访问，并且由于数组在内存上的连续性，因此访问会更快，但前提是元素必须排列紧凑， 这样在进行插入删除时就免不了要进行移动，而且由于数组长度不可变，在添加元素时可能需要扩容和复制处理。链表可以弥补数组在插入删除上的缺陷，但代价是牺牲查询的效率，尤其是按位置索引访问时，它只能选择从头或者从尾开始依次遍历。

在讨论之前先整体看下Collection的体系结构，可以看到其实有很多的实现类，它们分别用来应付各种不同的场景


另外，在看容器类的实现之前，最好先对[java 泛型]有个比较好的理解，因为容器类是促成java泛型最主要的原因之一

1. ArrayList

ArrayList相当于对数组做了一层代理，它在插入删除时做了两件事：
1、负责对数组进行扩容处理，在插入元素时可能造成数组越界，而ArrayList会提前检查并进行扩容；
2、负责对数组元素进行移动，以保证元素在位置上的连续性，在指定位置插入或删除元素时可能要对前后的元素进行移动；

1.1. 属性

java.util.ArrayList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    // 数组默认长度，如果初始化长度小于10，则第一次扩容时直接置为10
    private static final int DEFAULT_CAPACITY = 10;

    // 有的VM可能在数组中保存一些头信息，如果想数组中放入Integer.MAX_VALUE个元素，可能导致越界；
    // 所以扩容时先尽量扩为Integer.MAX_VALUE - 8，如果确实需要，再扩为Integer.MAX_VALUE
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    // 空数组，默认构造器即初始化一个空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 数组
    transient Object[] elementData;

    // 元素个数
    private int size;

    ...
}

1.2. 接口实现

主要看一下add和remove以及迭代器的实现，其他操作基本都可以在此基础上实现

1.2.1. add
java.util.ArrayList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) { 
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0) 
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); 
	
    if (newCapacity - minCapacity < 0) 
        newCapacity = minCapacity;
		
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
		
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) { 
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
		
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

看add实现主要就是看下ArrayList是如何对数组进行扩容的，这里真正体现了什么是简单即复杂（要想写出更简单的代码则要付出更多的思考与努力），上面的代码逻辑很少，却涵盖了所有的场景，可以梳理一下作者的思路：

记原数组长度为oldCapacity，记其1.5倍为newCapacity，并记增加元素最低所需长度为minCapacity

  1. 首先比较minCapacity与defaultCapacity，取较大者并记为minCapacity（确保首次扩容后至少为defaultCapacity）

  2. 再比较newCapacity与minCapacity，取较大者并记为newCapacity（如果newCapacity < minCapacity，则有三种可能情形：1.5倍之后长度小于10；1.5倍之后溢出；addAll接口，1.5倍之后不足以放下新做的元素；）

  3. 最后，如果newCapacity <= MAX_ARRAY_SIZE，则扩容完成，否则newCapacity超过了MAX_ARRAY_SIZE（包括溢出），那么再看minCapacity：
    如果 minCapacity 没有达到 MAX_ARRAY_SIZE，那么先扩为 MAX_ARRAY_SIZE；
    如果 minCapacity 超过了 MAX_ARRAY_SIZE，但是没溢出（小于 Integer.MAX_VALUE）则扩为 Integer.MAX_VALUE；
    如果 minCapacity 溢出，那么异常退出；

其实扩容实现能这么简洁干净，有两个判断比较关键：
newCapacity - MAX_ARRAY_SIZE > 0：表示 newCapacity 超过了 MAX_ARRAY_SIZE，包括溢出的可能
minCapacity > MAX_ARRAY_SIZE：表示 minCapacity 超过了 MAX_ARRAY_SIZE，但是没有溢出

可以通过画图来描述得更清晰些（假设这里 minCapacity 每次只比需比 oldCapacity 大 1）：

如果 oldCapacity 在 A-B 之间，则 newCapacity 扩到 B 点；
如果 oldCapacity 在 B-C 之间，则 newCapacity 扩为 1.5 倍，要是 1.5 倍之后落在 D-E 之间，那么先改成扩到 D 点；
如果 oldCapacity 在 C-D 之间，则 newCapacity 扩到 D 点；
如果 oldCapacity 在 D-E 之间，则 newCapacity 扩到 E 点；

1.2.2. remove
java.util.ArrayList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) { // 删除第一个equals成立的元素
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1; // 计算index之后实际有多少元素
    if (numMoved > 0) // 将index之后的元素整体向前移到一位，然后删除末尾元素
        System.arraycopy(elementData, index+1, elementData, index, numMoved);

    elementData[--size] = null; 
}

remove的思路很简单，就是将目标元素之后的元素整体前移一位，然后再删除末尾的元素，不过要注意remove(Object o)的含义只是删除第一个equals成立的元素。

1.2.3. iterator
java.util.ArrayList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;       // 下一次返回元素的索引
	
    int lastRet = -1; // 当前返回的元素的索引
	
    int expectedModCount = modCount; // 开始迭代时，list的修改次数

    public boolean hasNext() {
        return cursor != size;
    }

    // 返回cursor所在位置的元素，并记lastRet = cursor，cursor = cursor + 1  
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
			
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
			
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    // 删除当前元素，然后修正cursor为当前位置（因为当前位置上实际上已经是原先的下一位元素）
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1; // 原先的元素已经不存在，置为-1从语义上也说得通，这样Iterator不允许重复删除
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
		
        // 若没有迭代到末尾，并且list没有修改，则一直迭代下去
        while (i != size && modCount == expectedModCount) { 
            consumer.accept((E) elementData[i++]);
        }
		
        // 记住迭代器当前的状态
        cursor = i;
        lastRet = i - 1;
		
        // 如果上面检测到修改，在这里异常退出（退出前记住当前的迭代位置）
        checkForComodification();
    }

    // 迭代过程中，检测到list发生修改则立即异常退出
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

ArrayList的iterator返回的是一个迭代器的私有实现，后面其它容器对于迭代也都是类似的处理，这种实现方式的好处是统一了容器对于迭代的实现。另外，将接口实现为内部类可以很容易的在实现中访问当前类的内部状态，而不受访问权限的限制，并且这样可以使代码更加简洁，不至于定义太多public类而显得过于臃肿。

2. LinkedList

LinkedList通过前后引用将元素串在一起形成一个链表，然后只需要记住两端的节点（称为哨兵节点），即first和last，便可以访问链表上任意位置的元素。

另外，LinkedList除了实现了List，还实现了双端队列Deque，因此在非线程安全环境下，它完全可以当作队列或者栈来使用，对应的java也提供了数组实现ArrayDeque，只是很少用到，因为一般用到队列的场景都涉及到线程安全的考虑。

2.1. 属性

java.util.LinkedList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
	
    transient int size = 0; // 元素总数

    transient Node<E> first; // 头节点

    transient Node<E> last; // 尾节点

    // 元素封装节点
    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;
        }
    }

    ...
}

2.2. 接口实现

还是看一下添加和删除的实现

2.2.1. add
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public void add(int index, E element) {
    checkPositionIndex(index); 
    if (index == size)
        linkLast(element); 
    else
        linkBefore(element, node(index)); 
}

void linkLast(E e) {
    final Node<E> l = last;
	
    final Node<E> newNode = new Node<>(l, e, null); // 创建newNode，并将其prev记为原先的last
	
    last = newNode; //将newNode记为新的last
	
    if (l == null) 
        first = newNode; // 如果原先是空链表，那么将first也记为newNode
    else
        l.next = newNode; // 将原先last的next记为newNode
		
    size++;
    modCount++;
}

Node<E> node(int index) {
    if (index < (size >> 1)) { // 确定是从first还是从last遍历位置
        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;
    }
}

void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev; // 记原index位置的节点为succ，它的前一个节点记为pred
	
    final Node<E> newNode = new Node<>(pred, e, succ); // 创建newNode，并将其prev记为pred，next记为succ
	
    succ.prev = newNode; // 将succ的prev记为newNode
	
    if (pred == null) 
        first = newNode; // 如果原先succ就是头节点first，那么直接将newNode记为first
    else
        pred.next = newNode; // 将pred的next指向newNode
    size++;
    modCount++;
}

LinkedList的插入就是一个修改链接的过程，不过应该尽量避免指定插入位置，那样会多一个寻址过程。

2.2.2. remove
java.util.LinkedList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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) {
    final E element = x.item; // 记要删除的节点为element，前后节点分别为prev和next
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next; // 如果本身为头节点，则直接将next记为新的first
    } else {
        prev.next = next; // 将prev的next跳过自己
        x.prev = null;
    }

    if (next == null) { // 如果本身为尾节点，则直接将prev记为新的last
        last = prev;
    } else {
        next.prev = prev; // 将next的prev跳过自己
        x.next = null;
    }

    x.item = null; // 与上面一样手动赋null，其实x已经是一个不被引用的对象，也许是为了能让其更快被回收
    size--;
    modCount++;
    return element;
}

remove(Object o)的语义与ArrayList一样，删除第一个equals成立的元素，都有一个遍历比较的过程，不过即便删除指定索引的元素，LinkedList依然免不了遍历，所以考虑在LinkedList上插入删除操作的代价时，除了操作本身之外可能还有一个遍历操作。

3. 线程安全

上面的代码中都有一个modCount计数，它被用来记录当前容器的修改次数，比如新增或删除。与其它非线程安全容器一样，它们对于并发修改都会表现出及时失败，并反馈一个ConcurrentModificationException，即当检测到modCount不是期望值时就立即异常退出，比如上面的迭代实现。

虽然modCount的设计初衷是为了防止并发修改，不过即便在单线程环境下也很容易触发这个异常，比如在迭代过程中通过迭代器自身之外的方法修改容器，导致expectedModCount = modCount不成立便会异常，因此需要注意。