java集合类深入分析之List篇

简介

    在List中最常用的两个类就数ArrayList和LinkedList。他们两个的实现代表着数据结构中的两种种典型：线性表和链表。在这里，这个线性表是可以根据需要自动增长的。Java的库里面默认没有实现单链表，LinkedList实际上是一个双链表。这些具体的细节我们会在后续的代码里分析。

    实际上，ArrayList和LinkedList他们之间的整体类关系图如下：

    有了这个图作为参照，我们在后面就可以很容易的来分析他们的具体实现。前面的图片省略了部分实现接口的细节。

ArrayList

    如果我们看过前面一篇文章关于stack和vector的分析的话，这里对ArrayList的分析就显得比较简单。从某种角度来说，ArrayList和Vector实在是太相似了。他们都是基于数组的线性表实现。在它的内部，都是使用一个private transient Object[] elementData;这样的数组来保存元素。在ArrayList中间还采用了一个private int size;这样的变量来保存当前list的长度。

构造

    ArrayList有两个构造函数，分别如下：

  public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    this.elementData = new Object[initialCapacity];
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this(10);
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

    这两个构造函数的实现比较简单。第一个指定一个无参数的构造函数，设置里面数组的默认长度为10. 第二个函数通过将一个Collection类型的参数传递进来转换为内部保存元素的数组。 

增加元素

    增加元素的方法有若干个，包括有add(E e) , add(int index, E element), addAll()的两个重载的方法。在讨论这几个方法的具体实现之前，我们先考虑一下他们实现的基础。考虑一个比较典型的情况，我们在很多情况下如果增加元素到数组里会导致里面保存元素的数组长度不够了，那么就需要调整数组的长度，保证它能够包含新增加进来的元素。同时，考虑到我们具体的限制，如果要增加的元素太多了，导致数组不可能增长到它极限长度Integer.MAX_VALUE。这个时候我们要考虑进行异常处理。下面是扩展底层数组长度相关的源代码：

public void ensureCapacity(int minCapacity) {
    if (minCapacity > 0)
        ensureCapacityInternal(minCapacity);
}

private void ensureCapacityInternal(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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

    在我们原来的数组长度不能满足要求的时候，我们首先考虑将数组增加到原来的1.5倍，如 int newCapacity = oldCapacity + (oldCapacity >> 1);这句所描述。当然，如果增加到原来1.5倍发现长度还是不能满足需要的时候，我们就进行了后续的比较。首先将数组长度设置为期望的参数长度，然后和我们设置的最大长度比较。如果没有这个最大长度MAX_ARRAY_SIZE大的话，就直接分配这么长的数组。否则就分配最大长度的数组来尝试，这个最大的长度就是Integer.MAX_VALUE。

    有了这部分的讨论，我们再来看添加元素的实现时就毫无压力了：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

     我们每次增加元素前只要调用一下ensureCapacityInternal这个方法。它就帮我们把底层的数组调整全都做了。这里要做的无非就是把数组元素位置调整一下，然后长度加个1.addAll的两个方法也类似，无非就是传进来的是一个集合类型，我们要保证新传进来的数组长度加上原来元素的长度都在数组范围内。剩下的事情就是一通拷贝。显得一点技术含量都没有，这里就不再赘述了。

删除元素

    在ArrayList里面删除元素主要包含有3种情形，一种是删除一个元素，一种是删除一个区段范围内的元素，还有一种是删除所有的元素。他们的总体情况如下表：

 

方法名称	方法签名	种类
remove	public E remove(int index)	删除单个元素
remove	public boolean remove(Object o)	删除单个元素
removeRange	protected void removeRange(int fromIndex, int toIndex)	删除区段内元素
removeAll	public boolean removeAll()	删除所有元素
clear	public void clear()	删除所有元素

 

remove()方法的两种重载方法。具体的函数签名如下：

public E remove(int index) 

public boolean remove(Object o)

     他们分别表示删除指定索引位置的元素和删除指定的元素。

    还有一个是clear和removeRange方法，clear负责将数组里所有的元素删除。removeRange方法则删除指定区段范围内的元素。我们先把他们的实现代码贴出来，然后再来一一分析。

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // Let gc do its work

    return oldValue;
}

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])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

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
}

public void clear() {
    modCount++;

    // Let gc do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // Let gc do its work
    int newSize = size - (toIndex-fromIndex);
    while (size != newSize)
        elementData[--size] = null;
}

    我们先看remove(int index)这个方法的实现。在删除元素之前，我们先用rangeCheck方法判断指定的参数是否合法。因为有可能我们传入的参数不是在0到数组长度之间的。在找到要删除的元素之后，从它开始后面的元素向前移一位来实现元素的删除。这里int numMoved = size - index - 1;这一句指定了数组拷贝的长度。因为是要从index + 1这个元素到size - 1之间包括头尾这两个元素的一段往前挪一位，所以要移动的元素数目为size - index -1。

    remove(Object o)这个方法的实现考量是不一样的。因为它是要从数组中删除一个指定的元素，所以要删除它之前我们必须要遍历整个数组来找到它。如果根本就找不到，那根本就什么都不需要做了。如果找到这个要删除的元素，则和前面一个方法的处理流程一样，后面一个元素到末尾的都往前移一位。

    remove这两个重载的函数一般情况下不会混用，但是在一定情况下如果不理解清楚也会带来一些奇怪的问题。在我的这一篇文章中进行过详细的描述。

    clear方法显然非常的简单。它将数组里所有引用都置为null，这样做是防止内存泄露，然后再将数组长度设置为0.

    removeRange方法的参数指定了起始到终止的数据范围，所以实现的方法只要把终止元素到数组末尾的元素挪到原来起始位置的后面，再把空缺的那部分置空就可以了。

查找元素

    查找元素主要包含有如下几个方法：contains， indexOf, lastIndexOf。最核心的就是indexOf方法：

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

    这部分的代码非常简单，就是从头往后一直遍历和比较元素，找到相等的就返回。只是要考虑目的元素为null的情况。

    lastIndexOf也很类似，只是从数组的末尾往前遍历，寻找目的元素。

LinkedList

    我们在书本上看到的介绍也知道，如果我们要建立一个更加通用一点的链表结构的话，需要定义一个专门的节点数据类型。在jdk里，专门定义了一个内部类，它也决定了LinkedList是一个双向链表：

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内部使用的数据节点类型。实际上因为它也仅限与在LinkedList内部使用，所以才被定义成内部的private static class。我们实际上在构造LinkedList的时候不需要自己来构造Node对象，因为在其内部定义的构造函数已经做了，我们只需要指定E这个参数的类型就可以了。

    LinkedList里面包含了3个元素:

transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     * (first.prev == null && first.item != null)
     */
transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
transient Node<E> last;

    从注释就可以直观的看到，分别代表链表的长度，指向链表头和尾部的引用。

    linkedList和ArrayList有很多在元素的添加、删除查找上面接口相同的方法。和ArrayList比较起来的区别在于它是通过内部遍历链表再来进行操作的。这部分就针对几个典型的操作挑几个来分析。

添加元素

    添加元素里面比较典型的有linkFirst, linkLast。表示在链表头之前添加元素和链表尾部后面添加元素。他们的实现过程如下：

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}


public void addLast(E e) {
    linkLast(e);
}

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++;
}

    这里要考虑的一个点就是不管是在头之前还是在尾之后添加元素，要注意判断头尾节点为空的情况。同时，在更新完之后对长度值加1.LinkedList有一个比ArrayList好的地方，因为它可以很灵活的添加元素而不需要做大的调整。在ArrayList里面如果元素数量足够大了要调整和拷贝元素。

删除元素

    删除元素里面典型的两个操作是removeFirst()和removeLast()。

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

    在移除元素的时候，首先要判断first和last是否为空。当他们为空的时候意味着整个链表都是空的。还有一种需要考虑的情况就是如果整个链表只有一个元素，在删除了之后，实际上链表就空了。这里需next == null;和 prev == null;这两句就是分别在删除头和尾元素时判断删除后链表为空的条件。

    LinkedList和ArrayList很多相同的部分比如索引数据，他们的实现都比较简单，这里就不再一一列举。

其他特性

    如果我们看LinkedList的类声明：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

    它实现了一个Deque的接口，这个接口定义了队列的实现规范。在后面一篇文章里讨论队列实现的时候，我们会重点讲述，这里就暂时省略。

    另外，LinkedList还有一个有意思的特性，它本身也实现了一个栈的规范。和我们前面通过继承vector来实现Stack不一样。它采用每次直接在链表头之前添加元素来实现push方法，删除链表头元素实现pop方法。和栈实现相关的方法实现如下：

public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

   这样，以后我们如果要使用栈的话，除了声明Stack类以外，把LinkedList当成Stack使也是可行的。

总结

    要实现一个简单的ArrayList和LinkedList可以说是比较简单直观的事情，一个是只要声明一个数组，然后做索引访问就可以了。而另外一个是声明一个实体对象，并指定一个指向同类型的引用来建立链表。但是如果要实现一个比较实用的List需要考虑的地方就比较多。参照jdk里面的实现，我们可以看到很多实际工程中的限制在具体的实现中带来了哪些考量。另外，通过观察详细的实现，我们也可以澄清很多想当然的用法。

参考资料

http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html

 http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html