线性表及ArrayList/LinkedList源码分析总结

    int [] arr = new int[10]
    ......
    int [] newArr = new int[arr.length*2]
    for(int i=0;i<arr;i++){
        newArr[i] = arr[i];
    }
    arr = new Arr;

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

    public boolean remove(Object o) {         //删除分为两种情况，一种是删链表中的null元素，一种是删正常元素
        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;   //x.item表示当前的x节点
        final Node<E> next = x.next;    //x.next表示x后继引用，next同
        final Node<E> prev = x.prev;    //x.prev是x的前继引用，prev同
        ......

        if (prev == null) { //如果prev为null，则表示x为第一个结点，此时删除x的做法只需要将x的
            first = next;   //下一个节点设为第一个节点即可，first表示链表的第一节点。
        } else {
     ①      prev.next = next;   //否则的话，x为普通节点。那么只要将x的前一个结点(prev)的后继引用指向x的下一个 
            x.prev = null;      //节点就行了,也就是(向后)跳过了x节点。x的前继引用删除，断开与前面元素的联系。
        }

        if (next == null) {
            last = prev;    //如果x节点后继无人，说明他是最后一个节点。直接把前一个结点作为链表的最后一个节点就行
        } else {
     ②      next.prev = prev;   //否则x为普通节点，将x的下一个节点的前继引用指向x的前一个节点，也就是(向前)跳过x.   
            x.next = null;  //x的后继引用删除，断了x的与后面元素的联系
        }

        x.item = null;  //删除x自身
        size--;     //链表长度减1
        modCount++;
        return element;
    }

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

        if (index == size)  //size表示整个链表的长度，如果指定的索引等于链表的长度，那么就把这个元素添加到链表末尾
            linkLast(element);
        else        //否则执行linkBefore()方法，添加到末尾之前的元素前面
            linkBefore(element, node(index));
    }

    /**
     * Returns the (non-null) Node at the specified element index.返回指定索引处的非空元素
     */
    Node<E> node(int index) {
        if (index < (size >> 1)) {  //size >> 1,表示二进制size右移一位，相当于size除以2
            Node<E> x = first;
            for (int i = 0; i < index; i++) //如果指定的索引值小于size的一般，那么从第一个元素开始，
                x = x.next;         //指针向后移动查找,一直到指定的索引处
            return x;
        } else {            //else,从最后一个元素开始，向前查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {    //e为我们要插入的元素，succ为我们要插入索引处的元素

        final Node<E> pred = succ.prev;     //先将succ的前继引用(或者前一个结点的元素)保存在pred变量中
        final Node<E> newNode = new Node<>(pred, e, succ);  //创建一个新节点，也就是我们要插入的这个元素
                                    //注意new Node<>(pred, e, succ);这三个参数，可以参照(1.3)处的源码
     ① succ.prev = newNode; //succ的前继引用指向NewNode
        if (pred == null)       //如果这个前继引用为空，那就说明我们插入的元素是在最前面
            first = newNode;    //直接让newNode做第一个元素就行了
        else
    ②       pred.next = newNode;    //否则的话，在让pred的后继引用指向newNode节点
        size++;
        modCount++;
    }

public interface Collection<E> extends Iterable<E> {

    int size(); //@return the number of elements in this collection
    boolean isEmpty();  //@return <tt>true</tt> if this collection contains no elements
    boolean contains(Object o); //Returns <tt>true</tt> if this collection contains the specified element.
    Object[] toArray(); //Returns an array containing all of the elements in this collection.
    boolean remove(Object o);   //<tt>true</tt> if an element was removed as a result of this call
    boolean add(E e);   //<tt>true</tt> if this collection changed as a result of the call
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    ......
}

public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
     Iterator<T> iterator();

    /*
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
     default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    ......
}

    List<String> items = new ArrayList<>();
    items.add("A");
    items.add("B");
    items.add("C");
    items.add("D");
    items.add("E");

    for(String item : items){
        System.out.println(item);
    }

    List<String> items = new ArrayList<>();
    items.add("A");
    items.add("B");
    items.add("C");
    items.add("D");
    items.add("E");

    //lambda
    //Output : A,B,C,D,E
    items.forEach(item->System.out.println(item));

    //Output : C
    items.forEach(item->{
        if("C".equals(item)){
            System.out.println(item);
        }
    });

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
     default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

    /**
     * Removes from the underlying collection the last element returned
     * by this iterator (optional operation).  This method can be called
     * only once per call to {@link #next}.  
     * ......
     *
     * @throws IllegalStateException if the {@code next} method has not
     *         yet been called, or the {@code remove} method has already
     *         been called after the last call to the {@code next}
     *         method
     */

public class IteratorTest{
    public static void main(String[] args){
        ...
        Iterator it = books.iterator();
        while(it.hasNext()){
            String book = (String)it.next();
            if("book.equals("hhhhhh"))
                it.remove();    //删除上一次next()返回的元素，也就是"hhhhhh"
            book = "666666";  *
        }
    }
}

public class IteratorTest{
    public static void main(String[] args){
        ...
        Iterator it = books.iterator();
        while(it.hasNext()){
            String book = (String)it.next();
            if("book.equals("hhhhhh"))
                books.remove(book);     //错误，在迭代时调用了修改集合本身的方法
        }
    }
}

public class ForeachTest{
    public static void main(String[] args){
        ...
        for(Object obj : books){
            String book = (String)it.next();    //此处的book也不是变量本身
            if("book.equals("hhhhhh"))
                books.remove(book);     //错误，在迭代时调用了修改集合本身的方法
        }
    }
}
上面加注释的两个地方，是foreach循环与Iterator迭代类似的地方。

public interface List<E> extends Collection<E> {
    ......  //省略一些collection中展示过的方法

    /**同时List接口定义了一些自己的方来实现“有序”这一功能特点*/
    /**
     *返回列表中指定索引的元素
     */
    E get(int index);
    /**
     *设定某个列表索引的值
     */
    E set(int index, E element);
    /**
     *在指定位置插入元素，当前元素和后续元素后移
     *这是可选操作，类似于顺序表的插入操作
     */
    void add(int index, E element);
    /**
     * 删除指定位置的元素(可选操作)
     */
    E remove(int index);
    /**
     * 获得指定对象的最小索引位置，没有则返回-1
     */
    int indexOf(Object o);
    /**
     * 获得指定对象的最大索引位置
     * 可以知道的是若集合中无给定元素的重复元素下
     * 其和indexOf返回值是一样的
     */
    int lastIndexOf(Object o);
    /**
     *一种更加强大的迭代器，支持向前遍历，向后遍历插入删除操作
     */
    ListIterator<E> listIterator();          *
    ListIterator<E> listIterator(int index);    *
    /**
     * 返回索引fromIndex(包括)和toIndex(不包括)之间的视图。
     */
    List<E> subList(int fromIndex, int toIndex);
}

public interface ListIterator<E> extends Iterator<E> {

    boolean hasNext();
    E next();
    void remove();

    /**下面是在Iterator基础上增加的方法*/
    boolean hasPrevious();  //是否还有前继元素
    E previous();   //返回前一个元素
    int nextIndex();    //返回下一个元素的索引
    int previousIndex();    //返回前一个元素的索引
    void set(E e);  //替换由上一次next()或者previous()方法返回的元素.
    void add(E e);  //在上一次由next()方法返回的元素之前，或者在上一次previous()方法返回的元素之后，添加一个元素
}

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

    private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10;     //默认的初始容量
    private static final Object[] EMPTY_ELEMENTDATA = {};   //共享的空数组实例
    /**
     * 储存ArrayList元素的数组缓冲区。ArrayList的容量就是该缓冲数组的长度。任何以EMPTY_ELEMENTDATA作为
     * 数据元素的空ArrayList，在他们添加第一个元素的时候，都将被扩展至DEFAULT_CAPACITY(默认为10)长度。
     */
    transient Object[] elementData;
    private int size;   //ArrayList的大小,即他所包含的元素的个数

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

    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;   //EMPTY_ELEMENTDATA等于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);
    }

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //   扩容检查，确保当前数组在扩容之后可以容纳它的参数个大小的元素
        elementData[size++] = e;    // 将e增加至list的数据尾部，容量+1
        return true;
    }

    public void add(int index, E element) {     //在指定位置添加一个元素
        if (index > size || index < 0)      //判断是否越界
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        // 对数组进行复制处理，目的就是空出index的位置插入element，并将index后的元素位移一个位置
        ensureCapacityInternal(size + 1);  // 扩容检查
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;   //将元素添加到指定的位置
        size++;         //容量+1
    }

    public boolean addAll(Collection<? extends E> c) {  //将整个collection集合和添加到List结尾
        Object[] a = c.toArray();   //将c转化成Object类数组
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  //扩容检查
        System.arraycopy(a, 0, elementData, size, numNew);  //将c添加到list尾部
        size += numNew;     //更新当前容器大小
        return numNew != 0;
    }

    public boolean addAll(int index, Collection<? extends E> c) {   //在指定额索引处添加整个集合
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // 扩容检查

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    public E remove(int index) {    //根据索引位置删除元素
        if (index >= size)      //越界检查
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index];    //去除要删除的元素，该方法最终会返回这个值

        int numMoved = size - index - 1;    //计算数组要复制的值的数量
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);    //复制数组
        //数组最后一个元素置空，让垃圾回收器工作。因为删了一个元素，index之后的元素都往前移动了一个位置
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

    public boolean remove(Object o) {   //根据内容删除，只删除匹配的那个
        if (o == null) {    //对要删除的元素进行是否为null的判断
            for (int index = 0; index < size; index++)  //遍历数组，掘地三尺找这个要删除的null元素
                if (elementData[index] == null) {   //找到null值了.(注意这个null值需要用"=="判断)
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) { //非null是用.equals()比较
                    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; // clear to let GC do its work
    }

    private void ensureCapacityInternal(int minCapacity) {  //minCapacity就是我们需要的最小容量
        if (elementData == EMPTY_ELEMENTDATA) { //如果此时elementData等于空数组
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  //如果minCapacity比默认值10小，则
                                //minCapacity为10，否则为他自己。
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        //如果当前的数组长度小于我们所需要的minCapacity值(当前数组长度不够)，则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;   //oldCapacity等于当前数组的长度
        //oldCapacity >> 1，表示二进制的向右移一位，相当于十进制的除以2
        int newCapacity = oldCapacity + (oldCapacity >> 1); //newCapacity = 1.5 * oldCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;  //如果此时newCapacity还是小于我们所需要的minCapacity，那就让他等于minCapacity
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //以这个新的长度为标准重新创建，将原来数组中的元素拷贝一份到新的数组中去。Arrays.copyOf底层实现是System.arrayCopy()
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

public class randomAccessTest {
    private static long startTime;
    private static long endTime;

    public static void main(String[] args){
        List list  = new ArrayList();
        for(int i=0; i<1000; i++){
            list.add(i);
        }
        startTime = System.nanoTime();
        randomAccess(list);
        endTime = System.nanoTime();
        long time = endTime - startTime;
        System.out.println("randomAccessTime = " + time + "ns");
    }

    public static void randomAccess(List list){
        for(int i=0; i<list.size(); i++){

        }
    }
}

public class iteratorTest {
    private static long startTime;
    private static long endTime;

    public static void main(String[] args){
        List list  = new ArrayList();
        for(int i=0; i<1000; i++){
            list.add(i);
        }
        startTime = System.nanoTime();
        iterator(list);
        endTime = System.nanoTime();
        long time = endTime - startTime;
        System.out.println("iteratorTime = " + time + "ns");
    }

    public static void iterator(List list){
        Iterator iter = list.iterator();
        while( iter.hasNext()) {
            iter.next();
        }
    }
}

public class foreachTest {
    private static long startTime;
    private static long endTime;

    public static void main(String[] args){
        List list  = new ArrayList();
        for(int i=0; i<1000; i++){
            list.add(i);
        }
        startTime = System.nanoTime();
        foreach(list);
        endTime = System.nanoTime();
        long time = endTime - startTime;
        System.out.println("foreachTime = " + time + "ms");
    }

    public static void foreach(List list){
        for(Object obj:list) {

        }
    }
}

randomAccessTime = 7x10^5 ns
iteratorTime = 6x10^6ns
foreachTime = 5x10^6ns

/**
 * ......
 * As a rule of thumb, a
 * <tt>List</tt> implementation should implement this interface if,
 * for typical instances of the class, this loop:
 * <pre>
 *     for (int i=0, n=list.size(); i < n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>
 * /
 * 根据经验，一个list类的实现类应当实现这个接口，对于典型的该类的实例，上面的循环快于下面的循环。

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

    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;

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

    /**构造一个空的构造函数，这个构造函数，也真够空的**/
    public LinkedList() {
    }

    /**构造一个包含指定collection元素的表，这些元素按照collection的迭代器返回的顺序排列**/
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        final Node<E> l = last; //last表示双链表中的最后一个元素，l表示指向最后一个元素的引用
        final Node<E> newNode = new Node<>(l, e, null); //新建一个后继引用为空的新节点，后继为空，意味着他是最后一个元素
        last = newNode; //直接让这个新建的元素作为链表的最后一个元素就行了
        if (l == null)  //指向原本链表最后一个元素的引用l为空，说明原来的链表是一个空链表。
            first = newNode;    //此时让这个新建的结点元素最为第一个结点(就他一个啊)
        else
            l.next = newNode;   //否则的话，让原链表的后继引用指向我们新建的这个节点，插入完成
        size++;
        modCount++;
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);  //越域判断

        Object[] a = c.toArray();
        int numNew = a.length;      // 要插入元素的个数
        if (numNew == 0)
            return false;

        Node<E> pred, succ;     //申明两个节点类的前继，后继引用(这个循环就是在找出原列表中插入索引处的前后引用)
        if (index == size) {    //索引等于链表的长度，说明是要求插在链表的最后面
            succ = null;
            pred = last;        //此时后继引用为空，前继引用指向原链表的最后一个元素
        } else {
            succ = node(index); //否则后继引用指向原链表索引处的元素。node()方法我们之前讲过，二分法查找索引处元素
            pred = succ.prev;   //前继引用指向原链表索引处元素的前一个元素，完成插入
        }

        for (Object o : a) {    //遍历我们要插入的这个集合
            E e = (E) o;
            //新建一个结点，以pred作为前继引用，该for循环中每次遍历得到的collection集合中的e作为结点本身元素，
            //null作为后继引用。在第一次进行该循环时，通过上一个if的赋值，pred指向原链表中指定索引处的前一个元素。
            Node<E> newNode = new Node<>(pred, e, null);    //在第一次循环遍历的时候，这个新节点就是collection集合的第一个元素
            if (pred == null)   //如果pred为空，说明原链表为空
                first = newNode;    //新节点等于第一个节点
            else
                pred.next = newNode;    //否则，原链表中指定索引处的前一个元素 的后继引用指向这个新节点。
            pred = newNode; //然后将这个pred指向这个新的节点(在第一次循环中，这个新节点表示collection集合中的第一个元素)，相当于工作指针后移，然后重复上述过程。
        }

        //上述循环结束后，pred指针已经指向了collection集合的最后一个元素，此时由于succ没动过，因此他还是指向原链表中指定索引处的后一个元素
        if (succ == null) { //如果succ为null，和第一个if中的情况一样，说明这是在原链表的末尾插入元素
            last = pred;    //直接让此时的pred也就是collection中的最后一个元素作为插入后链表的最后一个元素就可以了
        } else {        //否则的话说明是在原链表中间插入元素
            pred.next = succ;   //此时让collection中最后一个元素的后继指针指向 原链表索引处的后一个元素，完成差诶工作
            succ.prev = pred;   //同时让succ的前继指针指向collection的最后一个元素，完成双向链表的建立
        }

        size += numNew; //增加链表长度
        modCount++;
        return true;
    }

public class usuallyforTest {
    private static long startTime;
    private static long endTime;
    private static final int SIZE = 10000;

    public static void main(String[] args){

        List<Integer> arraylist = new ArrayList<Integer>(SIZE);
        List<Integer> linkedlist  = new LinkedList<Integer>();
        for(int i=0; i<SIZE; i++){
            linkedlist.add(i);
            arraylist.add(i);
        }
        startTime = System.currentTimeMillis();
        usuallyfor(linkedlist);
        endTime = System.currentTimeMillis();
        long linkedlistTime = endTime - startTime;
        System.out.println("usuallyforLinkedlistTime = " + linkedlistTime + "ms");

        startTime = System.currentTimeMillis();
        usuallyfor(arraylist);
        endTime = System.currentTimeMillis();
        long arraylistTime = endTime - startTime;
        System.out.println("usuallyforArraylistTime = " + arraylistTime + "ms");
    }

    public static void usuallyfor(List<Integer> list){
        for(int i=0; i<list.size(); i++){
            if(list.get(i) % 2 == 0){
                list.remove(i);
            }
        }
    }
}

usuallyforLinkedlistTime = 57ms
usuallyforArraylistTime = 7ms

usuallyforLinkedlistTime = 232ms
usuallyforArraylistTime = 29ms

    public static void usuallyfor(List<Integer> list){
        for(int i=0; i<list.size(); i++){
            if(list.get(i) % 2 == 0){
                list.remove(i);
            }
        }
    }

public class iteratorTest {
    private static long startTime;
    private static long endTime;
    private static final int SIZE = 10000;

    public static void main(String[] args){

        List<Integer> arraylist = new ArrayList<Integer>(SIZE);
        List<Integer> linkedlist  = new LinkedList<Integer>();
        for(int i=0; i<SIZE; i++){
            linkedlist.add(i);
            arraylist.add(i);
        }
        startTime = System.currentTimeMillis();
        iterator(linkedlist);
        endTime = System.currentTimeMillis();
        long linkedlistTime = endTime - startTime;
        System.out.println("iteratorLinkedlistTime = " + linkedlistTime + "ms");

        startTime = System.currentTimeMillis();
        iterator(arraylist);
        endTime = System.currentTimeMillis();
        long arraylistTime = endTime - startTime;
        System.out.println("iteratorArraylistTime = " + arraylistTime + "ms");
    }

    public static void iterator(List<Integer> list){
        Iterator<Integer> iter = list.iterator();
        while( iter.hasNext()) {
            if(iter.next() % 2 == 0){
                iter.remove();
            }
        }
    }
}

iteratorLinkedlistTime = 2ms
iteratorArraylistTime = 10ms

iteratorLinkedlistTime = 4ms
iteratorArraylistTime = 34ms