List

该接口继承了Collection，有部分函数是直接override的，但也没有给default实现，用意不明。

int size();
boolean isEmpty();
......

也加上了一些额外的函数

default void replaceAll(UnaryOperator<E> operator);//采用listIterator实现
default void sort(Comparator<? super E> c);//先使用toArray,再对array排序，最后使用listIterator挨个set进去
//一些对下标的操作,掠过
ListIterator<E> listIterator();//返回一个列表迭代器
ListIterator<E> listIterator(int index);//返回从指定位置开始的列表迭代器

AbstractList

继承了AbstractCollection，实现了List ，和AbstractCollection类似，使用接口中已有函数来实现部分接口，与存储细节无关。例如

public int indexOf(Object o) {
    ListIterator<E> it = listIterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return it.previousIndex();
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return it.previousIndex();
    }
    return -1;
}

ModCount

提供了一个快速失败的策略，内部存储了一个modCount，在Itr 与SubList中，均有对此值进行校验，如果在迭代的过程中，值发生变化，就会抛ConcurrentModificationException。

Itr

内部类实现了Iterator，采用了游标cursor与lastRet实现功能。

ListItr

内部内，继承了Itr，添加了一些额外的函数。（双向移动和Set

默认的迭代器的remove，额外的set，add 均使用AbstractList中的函数进行实现。例如

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();
    try {
        AbstractList.this.remove(lastRet);
        if (lastRet < cursor)
            cursor--;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException e) {
        throw new ConcurrentModificationException();
    }
}

SubList

并非public类，继承了AbstractList，持有父List和offset，操作都是转到父List上实现的。例如

public void add(int index, E element) {
    rangeCheckForAdd(index);
    checkForComodification();
    l.add(index+offset, element);//l为父List
    this.modCount = l.modCount;
    size++;
}

ArrayList

数组实现的List，继承AbstractList

构造

无参构造器实际上是不会分配空间的，虽然有默认的DEFAULT_CAPACITY(10) ，指向静态变量DEFAULTCAPACITY_EMPTY_ELEMENTDATA({})

有参构造器会直接分配所需要的空间，如果传入的大小为0，则指向静态变量EMPTY_ELEMENTDATA({})

无参基本可以等同于未分配空间的ArrayList(10)

自动扩容

每次添加数据都会进行ensureCapacityInternal(int minCapacity)，minCapacity为即将到达的容量

首先会调用calculateCapacity进行比较，如果当前是默认DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就保证能容纳max(DEFAULT_CAPACITY,minCapacity)，否则就保证minCapacity

如果需要保证的容量minCapacity大于1.5倍当前底层数组elementData长度，那就增长到minCapacity长度。如果大于MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8），也没有溢出，那就扩容到Integer.MAX_VALUE

手动扩容

如果是无参构造的，那么保证容量为max(minCapacity,DEFAULT_CAPACITY)

如果是有参构造的，那么保证容量为minCapacity

缩容

并未看到用自动缩容的过程，需要手动调用trimToSize()，直接将底层数组调整到当前size，中间有复制数组的过程

删除

删除指定下标（或下标范围），需要先挪动数组，再对结尾置null，方便回收。

LinkedList

链表实现，内部持有一头一尾两个引用。

• 通过下标进行操作的时候，node(int index) 会判断从哪个方向进行遍历（最多size/2 ）。

• 内部类ListItr 进行add（），remove()等操作的时候，和ArrayList不一样，并不是调用外部的函数进行操作，而是自己进行操作，最后并不是expectedModCount = modCount，而是expectedModeCount++

  public void remove() {
      checkForComodification();
      if (lastReturned == null)
          throw new IllegalStateException();
      Node<E> lastNext = lastReturned.next;
      unlink(lastReturned);
      if (next == lastReturned)
          next = lastNext;
      else
          nextIndex--;
      lastReturned = null;
      expectedModCount++;
  }