JDK List源码分析

List接口定义了有序集合(序列)。在Collection的基础上，增加了可以通过下标索引访问，以及线性查找等功能。

整体类结构

JDK Collection 源码分析（2）—— List

1.AbstractList

该类作为List的通用骨架实现，和AbstractCollection一样，也是为了减少实现该接口的工作量。为了实现一个只读的List，仅仅只需要实现get和size方法即可。而对于读写的List，则需要额外覆写set，add和remove。

该类基于get(int)，set(int, Object)等方法实现了Iterator方法，基于随机访问的，所以如果如果是链表，还是得重新实现该方法。

该类有一个重要的属性：protected transient int modCount = 0;，这个属性用于检测多线程并发的，每次对集合的结构发生了变化（如添加或者删除等，由子类实现控制），modCount就会自增。当创建迭代器的时候，迭代器内部就会用一个属性(expectedModCount)来保存当前modCount的值，用于表示当前的状态。在遍历的过程中，如果另一个线程修改了集合(modCount发生变化),在该线程就会检测到expectedModCount和modCount 不一样，从而抛出并发异常(fast-fail)。(并不严格保证并发控制)

私有内部类：Itr和ListItr

Itr为最基本的迭代器，基于外部类的get等方法来构建。该类有三个属性：cursor用于记录当前的访问位置，expectedModCount保存当前容器状态，lastRet则保存上次访问的结果。而ListItr继承了Itr，添加了双向遍历的功能

对于迭代器的实现，和Lua等动态语言的闭包类似。

例如next操作：

public E next() {

	// 先检查是否被另一个线程修改过

    checkForComodification();

    try {

        int i = cursor;

        E next = get(i);

        // 保存这次访问的下标

        lastRet = i;

        // 移动到下一个元素

        cursor = i + 1;

        return next;

    } catch (IndexOutOfBoundsException e) {

        checkForComodification();

        throw new NoSuchElementException();

    }

}

public void remove() {

	// lastRet<0表示已经删除过一次，不允许连续删除（可以控制越界删除）

    if (lastRet < 0)

        throw new IllegalStateException();

    checkForComodification();

    try {

	    // 调用外部类的删除方法，modCount发生变化

        AbstractList.this.remove(lastRet);

        if (lastRet < cursor)

            cursor--;

        // 防止连续删除

        lastRet = -1;

        // 记录下modCount当前的值

        expectedModCount = modCount;

    } catch (IndexOutOfBoundsException e) {

        throw new ConcurrentModificationException();

    }

}

final void checkForComodification() {

    if (modCount != expectedModCount)

        throw new ConcurrentModificationException();

}

2.ArrayList

List接口的动态数组实现，和Vector最大不同之处在于，它是非同步的。如果需要同步，可以使用Collections.synchronizedList或者加锁同步。

添加元素的时候，如果当前数组已满，则会先执行扩容，再添加。每次扩展增加为原来容量的1/2，如：newCapacity = oldCapacity + (oldCapacity >> 1)，如果新计算出来的容量比所需要的小或者溢出，则只扩展至所需的大小:

private void grow(int minCapacity) {

    // overflow-conscious code

    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);

}

在删除元素的时候，经过移动后，需要把数组最后一个元素的引用置空，否则会存在强引用，GC无法收集而导致内存泄漏。如：

private void fastRemove(int index) {

    modCount++;

    int numMoved = size - index - 1;

    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    elementData[--size] = null; // Let gc do its work

}

3.AbstractSequentialList/LinkedList

AbstractSequentialList抽象类是为了减少实现序列访问存储的工作量，如链表等，该类通过使用ListIterator迭代器来实现父类的get，set等方法，如果要实现链表，仅仅只需要实现该方法的迭代器即可。

LinkedList继承了该抽象类，并实现了Deque双端队列的接口，底层采用双向链表的方式实现，其并没有沿用父类的一些实现，如对add的实现，父类通过迭代器从头遍历到尾部，后再添加，这里直接通过尾指针在表尾部添加，以实现O(1)的操作。在使用下标遍历访问时，做了点小优化，如果靠近头部，就从头部开始遍历，靠近尾部，则从尾部开始遍历。如下：

Node<E> node(int 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;

    }

}

秒客网