ArrayList和LinkedList源码浅析

ArrayList和LinkedList 源码浅析

在Colletion Framework中，List是最常用的接口，而ArrayList和LinkedList是List最常见的实现，ArrayList是最综合和通用的实现，底层采用数组，而LinkedList底层采用链表进行实现。

下面看类图：

image.png

Collection接口

Collection定义的接口是

//查询
java.util.Collection#size
java.util.Collection#isEmpty
java.util.Collection#contains
java.util.Collection#iterator
java.util.Collection#toArray()
java.util.Collection#toArray(T[])
//修改
java.util.Collection#add
java.util.Collection#remove
//批量操作
java.util.Collection#containsAll
java.util.Collection#addAll
java.util.Collection#removeAll
java.util.Collection#removeIf
java.util.Collection#retainAll
java.util.Collection#clear

//比较和Hash
java.util.Collection#equals
java.util.Collection#hashCode
//关于java stream
java.util.Collection#spliterator
java.util.Collection#stream
java.util.Collection#parallelStream

可以看到 六个基本操作，

toArray() 和 toArray(T[])的区别是，

1.前者返回的是Object数组，类型不对还要自己去转很麻烦。

2.后者会把返回的结果保存到参数传递进来的数组中，而且支持泛型。

3.如果后者T[]的大小如果小于容器的大小，会自动扩容。

4.前者等价于toArray(new Object[0]);

removeIf 原型如下：

  default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
  }

而Predicate接口如下：

java.util.function.Predicate#test
java.util.function.Predicate#and
java.util.function.Predicate#negate
java.util.function.Predicate#or
java.util.function.Predicate#isEqual

即使用迭代器把满足一定条件的元素移除。 就像perl里的grep,python 里的filter。

equals 和 hascode 所有对象都要实现, equals要满足，自反，对称，传递，一致，不等于null。

最后看spliterator，stream，parallelStream；

spliterator 是 java stream遍历时的可切割迭代器，用于支持并行遍历。

  @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }

    public static <T> Spliterator<T> spliterator(Collection<? extends T> c,
                                                 int characteristics) {
        return new IteratorSpliterator<>(Objects.requireNonNull(c),
                                         characteristics);
    }

stream，parallelStream； 是将collection转换成stream, stream 可以使用java stream一系列操作，是数据源，这里不进一步阐述。

AbstractColletion实现了大部分接口，不过都是只用基本的API，AbstractList 进一步实现了List中的接口，并且实现了四个内部类，两个迭代器，Itr，ListItr，分别是普通迭代器和双向迭代器，两个子List，sublist和RandomAccessSubList，使用委托或者说组合的方式，在原本List的基础进行偏移操作，并不会耗费新的空间。

ArrayList

到了ArrayList ，使用数组作为内部容器，初始大小是10, 而且会懒加载。

当空间不够时，会扩容，

private void grow() {
  ...
  int newCapacity = oldCapacity + (oldCapacity >> 1);   采用是1.5倍
}

但是ArrayList是不会自动缩小，可以手动缩小容量，trimToSize

并且ArrayList并没有实现循环队列，删除头部节点，后面是会整体移动的。

    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; // clear to let GC do its work

        return oldValue;
    }

ArrayList 不仅重载了AbstractList中的四个内部类中的三个，两个迭代器和subList，还实现了ArrayListSplititerator，因为数组是可以随机访问的，因此，可以实现并行的迭代器。

LinkedList

AbstractSequentialList 是介与LinkedList与AbstractList之间的一个抽象类, 代表直线顺序访问的列表，并实现了部分方法，使用迭代器进行顺序访问。而支持随机访问的，建议是直接实现AbstractList，比如ArrayList。

LinkedList 是双向链表实现，内部有一个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的实现，没有哨兵, 并且不是循环链表：

    /**
     * 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;

内部类方面：

重新实现了ListItr和降序迭代器DescendingIterator，还重新实现Spliterator。

clone 方面，链表需要手动把链表进行重建，并且也是浅拷贝。

接口方面，比ArrayList多实现了Deque, 我们看一下Deque接口的继承关系如下：

Deque->Queue->Collection

Deque 是 双向队列，可以在头尾都做操作:

java.util.Deque#addFirst
java.util.Deque#addLast
java.util.Deque#offerFirst
java.util.Deque#offerLast
java.util.Deque#removeFirst
java.util.Deque#removeLast

java.util.Deque#pollFirst
java.util.Deque#pollLast
java.util.Deque#getFirst
java.util.Deque#getLast
java.util.Deque#peekFirst
java.util.Deque#peekLast

java.util.Deque#removeFirstOccurrence
java.util.Deque#removeLastOccurrence

java.util.Deque#add
java.util.Deque#offer
java.util.Deque#remove()
java.util.Deque#poll
java.util.Deque#element
java.util.Deque#peek

java.util.Deque#push
java.util.Deque#pop

java.util.Deque#remove(java.lang.Object)
java.util.Deque#contains
java.util.Deque#size
java.util.Deque#iterator
java.util.Deque#descendingIterator

可以看到Deque的设计上似乎有很多冗余，例如把父类接口上的方法又写了一遍，而且作为一个双向队列，貌似6个操作就足够了为什么需要前面12个方法。

	First Element (Head)	Last Element (Tail)
	Throws exception	Special value	Throws exception	Special value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

分别是抛异常和不抛异常。

另外，扩展Queue的方法虽然和deque的方法等价，但是仍然写了下来。

同时实现Stack的方法，（stack是desperate的）

push,pop,peek 这些操作都是在 Deque的前面（First）开始的。

最后都是来自collection接口的基本操作。

因此需要双向队列，队列，栈，列表的时候都可以使用LinkedList作为实现。

另外Deque还有其他的实现：

• ConcurrentLinkedList
• LinkedBlockingDeque
• ArrayDeque