java容器類分析：Collection,List,ArrayList

1、 Iterable 與 Iterator

Iterable 是個介面，實現此介面使集合對象可以通過迭代器遍歷自身元素.

public interface Iterable<T>

第一個介面iterator()是jdk1.5引入的，需要子類實現一個內部迭代器Iterator遍歷元素。

後兩個介面是JDK1.8後新添加的，forEach(Consumer action)是為了方便遍歷操作集合內的元素,spliterator()則提供了一個可以並行遍歷元素的迭代器,以適應現在cpu多核時代並行遍歷的需求.

其中我們可以看下default修飾符,這也是Java 8後新出現的,我們知道,如果我們給一個介面新添加一個方法,那麼所有他的具體子類都必須實現此方法,為了能給介面拓展新功能,而又不必每個子類都要實現此方法,Java 8新加了default關鍵字,被其修飾的方法可以不必由子類實現,並且由dafault修飾的方法在介面中有方法體,這打破了Java之前對介面方法的規範.

Iterator 為迭代器類，用於遍歷容器。

public interface Iterator<E>

AbstartList中實現了Iterator類作為List內部的迭代器，用於訪問內部元素，其代碼如下：

  1 private class Itr implements Iterator<E> {
  2         /**
  3          * Index of element to be returned by subsequent call to next.
  4          */
  5         int cursor = 0;
  6 
  7         /**
  8          * Index of element returned by most recent call to next or
  9          * previous.  Reset to -1 if this element is deleted by a call
 10          * to remove.
 11          */
 12         int lastRet = -1;
 13 
 14         /**
 15          * The modCount value that the iterator believes that the backing
 16          * List should have.  If this expectation is violated, the iterator
 17          * has detected concurrent modification.
 18          */
 19         int expectedModCount = modCount;
 20 
 21         public boolean hasNext() {
 22             return cursor != size();
 23         }
 24 
 25         public E next() {
 26             checkForComodification();
 27             try {
 28                 int i = cursor;
 29                 E next = get(i);
 30                 lastRet = i;
 31                 cursor = i + 1;
 32                 return next;
 33             } catch (IndexOutOfBoundsException e) {
 34                 checkForComodification();
 35                 throw new NoSuchElementException();
 36             }
 37         }
 38 
 39         public void remove() {
 40             if (lastRet < 0)
 41                 throw new IllegalStateException();
 42             checkForComodification();
 43 
 44             try {
 45                 AbstractList.this.remove(lastRet);
 46                 if (lastRet < cursor)
 47                     cursor--;
 48                 lastRet = -1;
 49                 expectedModCount = modCount;
 50             } catch (IndexOutOfBoundsException e) {
 51                 throw new ConcurrentModificationException();
 52             }
 53         }
 54 
 55         final void checkForComodification() {
 56             if (modCount != expectedModCount)
 57                 throw new ConcurrentModificationException();
 58         }
 59     }
 60 

2、Collection

Collection 是容器類的介面，裡面可以存放很多Elements，很多容器都實現了該介面。

public interface Collection<E> extends Iterable<E>

上述很多函數的實現可以參考 AbstactList中的實現。

3. List

List是一個介面，繼承了Collection中的所有介面，並且添加了自身相關介面和具體實現。

由上圖可以看出，Collection分成了三個分支，List就是其中一個，下麵我們具體分析一下增加的介面。

public interface List<E> extends Collection<E>

上表可以看出，增加了 和index相關的介面，根據index對List進行的get、set、remove等操作。另一類添加的介面是ListIteator相關的，獲取List的迭代器。

3.1 ListIterator

public interface ListIterator<E> extends Iterator<E>

ListIterator 不光包含Iterator中的三個介面還增加了作為一個List迭代器應該有的介面，如 next(),previous()等

首先需要明確ListIterator迭代器的作用：

1. 允許我們向前、向後兩個方向遍歷 List;
2. 在遍歷時修改 List 的元素；
3. 遍歷時獲取迭代器當前游標所在位置。

註意，迭代器 沒有當前所在元素一說，它只有一個游標( cursor )的概念，這個游標總是在元素之間，比如這樣:

迭代器的初始位置：

調用next()後迭代器的位置

調用 previous() 游標就會回到之前位置。當向後遍歷完元素，游標就會在元素 N 的後面

也就是說長度為 N 的集合會有 N+1 個游標的位置。

3.2 AbstractCollection / AbstractList

        在上面的繼承關係圖中並沒有顯示出AbstractCollect和AbstractList的存在，但是在閱讀源碼的時候經常遇到這兩個類，下麵講一下這兩個類的作用。

      首先需要明確的一點是AbstractCollect和AbstractList都是抽象類而不是介面，它們分別實現了Collection和List介面中的部分函數。這樣繼承者直接繼承AbstractXXXX 而不需要自己重覆實現裡面的所有介面。這兩個抽象類抽離了公共部分，進行了實現，減少後續類的工作量。

       ArrayList 和LinkedList都直接或者間接繼承了AbstartList類。下圖為這兩個類的繼承關係：

        具體這兩個類裡面實現了哪些介面，請自己閱讀源碼不再講解。

LinkedList中modCount和expectedModCount作用

在AbstractList中可以看到這兩個變數，它們用於表示List被修改的次數，這其中包括了調用集合本身的add等方法等修改方法時進行的修改和調用集合迭代器的修改方法進行的修改。而expectedModCount則是表示迭代器對集合進行修改的次數。

那麼知道這兩個值有什麼作用呢？

如果創建多個迭代器對一個集合對象進行修改的話，那麼就會有一個modCount和多個expectedModCount，且modCount的值之間也會不一樣，這就導致了moCount和expectedModCount的值不一致，從而產生異常。

https://www.cnblogs.com/zhangcaiwang/p/7131035.html

3.3 ArrayList

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable我們看到ArrayList的定義的時候很可能會出現一個疑問，為什麼它已經繼承了AbstractList了還需要去實現List<E>介面？ 答案是，後面的List<E>可以去掉，這裡只是讓閱讀者明白ArrayList是個List。 終於好不容易到了開發者常用的類了，有點竊喜：transient Object[] elementData;這個很重要的成員變數elementData數組用來存放ArrayList中的元素，當第一個元素添加進來後，它的預設長度變為10。（java中“transient”關鍵字修飾的成員變數在類序列化的過程中不會被持久化到文件中，保證該成員變數保存信息的安全。）
ArrayList的構造函數中可以直接指定elementData數組的長度，那麼問題來了，當數組已經完全被占用再向ArrayList中添加元素時，如何再分配更大長度的數組？如何把舊數據拷貝到新數組中？答案見下麵這段源碼

  1 private void grow(int minCapacity) {  //最少需要的容量 
  2         // overflow-conscious code
  3         int oldCapacity = elementData.length;
  4         int newCapacity = oldCapacity + (oldCapacity >> 1);   // 分配最小容量的 1.5倍
  5         if (newCapacity - minCapacity < 0)       
  6             newCapacity = minCapacity;
  7         if (newCapacity - MAX_ARRAY_SIZE > 0)
  8             newCapacity = hugeCapacity(minCapacity);   // 最大容量比較（Inter.MAX_VALUE）
  9         // minCapacity is usually close to size, so this is a win:
 10         elementData = Arrays.copyOf(elementData, newCapacity);  // 將舊數據拷貝到新數組中
 11     }

其它介面不再細說。

3.4 LinkedList

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

作為一個鏈表類型，首先需要熟悉一下節點類：Node(LinkedList靜態內部類)

  1 private static class Node<E> {
  2         E item;
  3         Node<E> next;
  4         Node<E> prev;
  5 
  6         Node(Node<E> prev, E element, Node<E> next) {
  7             this.item = element;
  8             this.next = next;
  9             this.prev = prev;
 10         }
 11     }

在LinkedList中有三個主要成員變數：

• transient int size = 0;      // 鏈表長度
• transient Node<E> first;  // 鏈表的首節點
• transient Node<E> last;  // 鏈表的末節點

LinkedList構造方法：

  1  /**
  2      * Constructs an empty list.
  3      */
  4     public LinkedList() {
  5     }
  6 
  7     /**
  8      * Constructs a list containing the elements of the specified
  9      * collection, in the order they are returned by the collection's
 10      * iterator.
 11      *
 12      * @param  c the collection whose elements are to be placed into this list
 13      * @throws NullPointerException if the specified collection is null
 14      */
 15