List

List是一個維持內(nèi)部元素有序的采集器热鞍，其中的每個元素都會擁有一個索引，每個元素都可以
通過他的索引獲取到元素，并且索引的開始下標(biāo)是從0開始的申眼，List中的元素還可重復(fù)啦鸣。
而Set中不不含重復(fù)元素的潮饱。

以上便List的定義。實際中List僅是一個接口诫给，并沒有具體的方法實現(xiàn)香拉，只是定義好了統(tǒng)一的方法啦扬。

以下便是List的繼承結(jié)構(gòu)：

• Iterable
  • Collection
    • List

我們先來看看頂級的Iterable：

Instances of classes that implement this interface can be used with
the enhanced for loop.
也就是說繼承了這個接口能增強(qiáng)子類的循環(huán)能力。

Iterable中有唯一定義的接口方法：

Iterator<T> iterator();

他的作用就是返回一個Iterator<T>的實例凫碌。

接下來看看Iterator到底是什么東西

他是一個對象序列的迭代器扑毡，例如說集合。
它擁有三個接口方法：

//是否還有更多的沒有被迭代的元素盛险，有則返回true僚楞，否則返回false
public boolean hasNext();

 //返回下一個對象元素，并且是迭代器前進(jìn)枉层，如果沒有元素了的話會拋出NoSuchElementException
 public E next();

 //移除最后通過next()返回對象元素泉褐。此方法只能在調(diào)用next()后才能調(diào)用，否則會拋出IllegalStateException
 public void remove();

我們再來看看Collection接口：

Collection是所受Collection類型的根節(jié)點鸟蜡，也就是說所有的集合類型的都會實現(xiàn)這個接口膜赃。

而List在Collection的基礎(chǔ)上增加了以下接口方法：

此外還有：

ListIterator<E> listIterator();
ListIterator<E> listIterator(int location);

其中ListIterator繼承子Iterator佳恬，新添加了幾個方法：

public boolean hasPrevious();
public int nextIndex();
public E previous();
public int previousIndex();
void set(E object);

ArrayList

ArrayList繼承自AbstractList，實現(xiàn)了Cloneable于游，Serializable毁葱，RandomAccess接口
而AbstractList繼承自AbstractCollection<E>實現(xiàn)了List<E>接口，是一個抽象類贰剥，他的子類必須實現(xiàn)iterator(),size()這個兩個抽象方法倾剿，以使得可以創(chuàng)建處一個不可變的集合。而創(chuàng)建一個可修改的集合類型則需要重寫add()方法。

ArrayList是List的一個基于數(shù)組的實現(xiàn)類前痘，支持增加凛捏，移除，替換等元素操作芹缔。并且支持所有元素類型包括null坯癣。它的所有操作同步進(jìn)行的。而CopyOnWriteArrayList則可以用于高度并發(fā)最欠，頻繁遍歷的情形示罗。

數(shù)組容量增長步長。

private static final int MIN_CAPACITY_INCREMENT = 12;

構(gòu)造函數(shù)

初始化時指定數(shù)組容量芝硬，直到自己數(shù)據(jù)容量的時候蚜点，最好都指定。默認(rèn)是一個空數(shù)組拌阴。

public ArrayList(int capacity) {
    if (capacity < 0) {
        throw new IllegalArgumentException("capacity < 0: " + capacity);
    }
    array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}

public ArrayList() {
    array = EmptyArray.OBJECT;
  }

　//指定一個collection初始化的時候
 public ArrayList(Collection<? extends E> collection) {
   if (collection == null) {
       throw new NullPointerException("collection == null");
   }
   //先轉(zhuǎn)化成數(shù)組
   Object[] a = collection.toArray();

   if (a.getClass() != Object[].class) {
      　//創(chuàng)建一個長度為collection長度的新數(shù)組禽额，并將collection數(shù)組復(fù)制到新數(shù)組中
       Object[] newArray = new Object[a.length];
       System.arraycopy(a, 0, newArray, 0, a.length);
       a = newArray;
   }
   array = a;
   size = a.length;
}

添加

添加的時候基本策略是，有指定添加的索引位置的時候就檢查是否索引越界皮官，如果是則直接拋出越界異常脯倒。然后是檢查當(dāng)前數(shù)組是否已經(jīng)裝滿，如果是則計算新的數(shù)組容量捺氢，并創(chuàng)建一個新的數(shù)組藻丢，原數(shù)組的元素復(fù)制到新數(shù)組并將新添加的元素加入到list的末尾，更新size值摄乒。

@Override public boolean add(E object) {
    Object[] a = array;
    int s = size;
    //原數(shù)組已滿
    if (s == a.length) {
        Object[] newArray = new Object[s +
                (s < (MIN_CAPACITY_INCREMENT / 2) ?
                 MIN_CAPACITY_INCREMENT : s >> 1)];
        System.arraycopy(a, 0, newArray, 0, s);
        array = a = newArray;
    }
    a[s] = object;
    size = s + 1;//容量加一
    modCount++;
    return true;
}

該方法是根據(jù)傳入的當(dāng)前數(shù)組容量值計算并返回新的容量值悠反，時空權(quán)衡。
擴(kuò)容策略：

1. 當(dāng)前容量小于最下增長量的一半：
   當(dāng)前容量＋最小增長量
2. 當(dāng)前容量大于等于最下增長量的一半:
   當(dāng)前容量＋當(dāng)前容量/2

private static int newCapacity(int currentCapacity) {
    int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
            MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
    return currentCapacity + increment;
}

查找

當(dāng)需要查找的元素對象不為空的時候馍佑，從頭開始遍歷數(shù)組的元素斋否，equals則直接返回對應(yīng)類型。
查找的元素對象為空時拭荤，從頭開始遍歷數(shù)組的元素茵臭，遇到一個　==null的元素的時候則直接返回對應(yīng)類型。

Object[] a = array;
int s = size;
if (object != null) {
    for (int i = 0; i < s; i++) {
        if (object.equals(a[i])) {
            ...
            return ...;
        }
    }
} else {
    for (int i = 0; i < s; i++) {
        if (a[i] == null) {
            ...
            return ...;
        }
    }
}

remove一個元素的時候會有這么一個操作：a[s] = null; 是為了防止內(nèi)存溢出舅世。

指定位置元素移除： public E remove(int index)旦委，只需檢測時候下標(biāo)越界。不越界則移除該位置的元素雏亚。

移除元素位置之后的元素都前移一位
System.arraycopy(a, index + 1, a, index, --s - index);
//此時a[s] == a[s－1]缨硝，所以可以刪除末尾的那個a[s]
a[s] = null;  // Prevent memory leak
size = s;

在每次list的增刪改操作的時候都會modCount++。modCount是用來記錄list的修改次數(shù)罢低，
主要是在ArrayList總的內(nèi)部迭代器ArrayListIterator中使用

ArrayListIterator

//剩余沒有被迭代到的元素數(shù)量
private int remaining = size;
//可被使用remove()移除的元素的索引, -1表示沒有可以被移除的元素
private int removalIndex = -1;
//期待的list操作次數(shù)查辩，可判斷是否存在并發(fā)操作
private int expectedModCount = modCount;

//是否迭代完
public boolean hasNext() {
    return remaining != 0;
}

public E next() {
    ArrayList<E> ourList = ArrayList.this;
    int rem = remaining;
    //存在并發(fā)操作
    if (ourList.modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    //已經(jīng)迭代完，繼續(xù)迭代拋出異常，　用hasNext()做檢查宜岛，避免此異常
    if (rem == 0) {
        throw new NoSuchElementException();
    }
    remaining = rem - 1;
    //ourList.size - rem處的元素
    return (E) ourList.array[removalIndex = ourList.size - rem];
}

public void remove() {
    Object[] a = array;
    int removalIdx = removalIndex;

    ...

    System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
    a[--size] = null;  // Prevent memory leak
    removalIndex = -1;//重新置為-1匀钧，表示該索引的元素已移除。除非被next()更新谬返。
    expectedModCount = ++modCount;//會更新list的操作次數(shù)
}

再來看看的ArrayList的迭代器中定義的equals策略

public boolean equals(Object o) {
    //引用相等
    if (o == this) {
        return true;
    }
    //參數(shù)o不是List的子類
    if (!(o instanceof List)) {
        return false;
    }
    List<?> that = (List<?>) o;
    int s = size;
    //兩個list的size不想等
    if (that.size() != s) {
        return false;
    }
    Object[] a = array;

    if (that instanceof RandomAccess) {
        for (int i = 0; i < s; i++) {
            Object eThis = a[i];
            Object ethat = that.get(i);
            if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
                return false;
            }
        }
    } else {  // 參數(shù)的list不支持隨機(jī)訪問之斯，則使用迭代器進(jìn)行迭代
        Iterator<?> it = that.iterator();
        for (int i = 0; i < s; i++) {
            Object eThis = a[i];
            Object eThat = it.next();
            if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
                return false;
            }
        }
    }
    return true;
}

至此，ArrayList已被你KO遣铝。