現在網上對于ArrayList和LinkedList的分析文章非常多，但是基本分析的都有一些錯誤。所以我想通過源碼分析的角度才能正好的理解ArrayList和 LinkedList
ArrayList的基于數組，內部就是一個Object[]的數組。默認的capacity為10。
// 默認的數組容量為10 PRivate static final int DEFAULT_CAPACITY = 10; // Object[]數組 transient Object[] elementData; // 當前數組的大小 private int size; // 數組最大長度 private static final int MAX_ARRAY_SIZE = 2147483639;ArrayList的add操作，每次都需要檢查是否擴容，capacity越小，擴容越頻繁，擴容非常耗時。
public boolean add(E arg0) { // 檢查是否需要擴容 this.ensureCapacityInternal(this.size + 1); this.elementData[this.size++] = arg0; return true; }ArrayList擴容機制，當添加一個元素，如果添加元素之后的長度大于原來數組最大長度，就需要擴容，每次擴容的長度為當前最大的一半
private void grow(int arg0) { // 獲取數組的長度 int arg1 = this.elementData.length; // 數組長度右移1位（相當于除2） int arg2 = arg1 + (arg1 >> 1); if (arg2 - arg0 < 0) { arg2 = arg0; } // 默認最大長度為2147483639 if (arg2 - 2147483639 > 0) { arg2 = hugeCapacity(arg0); } // 通過Arrays.copyOf方法進行擴容 this.elementData = Arrays.copyOf(this.elementData, arg2); }LinkedList是一個雙鏈表，有一個firstNode和一個LastNode。
// 鏈表長度 transient int size; // 頭節點 transient LinkedList.Node<E> first; // 尾節點 transient LinkedList.Node<E> last;LinkedList的add操作：添加一個新的元素時，將創建一個新的Node節點，并設置Node的前節點，設置Node的后節點為null。
void linkLast(E arg0) { LinkedList.Node arg1 = this.last; // 設置arg2的前節點為arg1，后節點為null LinkedList.Node arg2 = new LinkedList.Node(arg1, arg0, (LinkedList.Node) null); // 將arg2節點作為最后一個節點 this.last = arg2; if (arg1 == null) { this.first = arg2; } else { // 設置arg1的后節點為arg2 arg1.next = arg2; } ++this.size; ++this.modCount; }Node類
private static class Node<E> { E item; LinkedList.Node<E> next; LinkedList.Node<E> prev; Node(LinkedList.Node<E> arg0, E arg1, LinkedList.Node<E> arg2) { this.item = arg1; this.next = arg2; this.prev = arg0; } }ArrayList的get操作：檢查數組是否越界，然后根據下標獲取結果
public E get(int arg0) { // 檢查是arg0是否超過的數組的長度，超過長度拋出IndexOutOfBoundsException this.rangeCheck(arg0); // 根據下標獲取結果 return this.elementData(arg0); }LinkedList的get操作 ：根據傳入的值進行判斷，如果傳入的值在0~size/2,那么從頭節點開始遍歷，如果傳入的值在size/2~size范圍，那么從尾節點開始遍歷。
LinkedList.Node<E> node(int arg0) { LinkedList.Node arg1; int arg2; // arg0是否小于鏈表的大小的一半 if (arg0 < this.size >> 1) { arg1 = this.first; // 從頭節點開始遍歷 for (arg2 = 0; arg2 < arg0; ++arg2) { arg1 = arg1.next; } return arg1; } else { arg1 = this.last; // 從尾節點開始遍歷 for (arg2 = this.size - 1; arg2 > arg0; --arg2) { arg1 = arg1.prev; } return arg1; } }ArrayList的remove操作：判斷傳入的值是否超過數組最大長度，然后獲取需要移除的元素的值，再判斷被移除的元素是否是最后一位，如果不是，則將傳入值之后的所有元素左移一位，最后將最后一位元素設為null。
public E remove(int arg0) { // 檢查數組是否越界 this.rangeCheck(arg0); ++this.modCount; // 獲取移除的元素值 Object arg1 = this.elementData(arg0); // 判斷是否是最后一個元素，arg2等于0，代表最后一個元素 int arg2 = this.size - arg0 - 1; if (arg2 > 0) { // 將所有元素左移一位 System.arraycopy(this.elementData, arg0 + 1, this.elementData, arg0, arg2); } // 設置最后一位值為null，并且size-1 this.elementData[--this.size] = null; return arg1; }LinkedList的remove操作：先判斷是否越界，然后通過get方法獲取被移除的節點，判斷是否是first節點和last節點，并設置移除節點所有屬性為null和將被移除的節點前后節點連接。
// 在操作unlink之前需要通過get方法獲取被移除的節點E unlink(LinkedList.Node<E> arg0) { Object arg1 = arg0.item; // 獲取移除值的后節點 LinkedList.Node arg2 = arg0.next; // 獲取移除值的前節點 LinkedList.Node arg3 = arg0.prev; // 判斷移除的是否是第一個節點，如果是就講移除節點的后節點設置為第一個節點 if (arg3 == null) { this.first = arg2; } else { arg3.next = arg2; arg0.prev = null; } // 判斷移除的是否是最后一個節點 if (arg2 == null) { this.last = arg3; } else { arg2.prev = arg3; arg0.next = null; } arg0.item = null; --this.size; ++this.modCount; return arg1; }add：當數據小于5萬以下，通過add操作，LinkedList比ArrayList速度明顯快，但當數據逐漸再增大，ArrayList的數組明顯比LinkedList快很多很多。
原因分析：ArrayList的默認capacity的值為10，當插入大量數據時（大約5萬條），ArrayList需要多次擴容，所以影響ArrayList的速度。但是當數據量再逐漸增大，ArrayList的擴容大小按指數增張，后面擴容的次數會越少，然而每次擴容的容量卻越大，所以導致最終ArrayList的總體速度反而更快。單純從add操作上看，ArrayList的速度比LinkedList的速度快，但是因為ArrayList前期由于需要擴容的次數太多，從而拖慢了ArrayList的速度。
解決方案：使用ArrayList數據量很大時，最好指定ArrayList的數組大小。
get：ArrayList的get操作明顯快于LinkedList的get操作。
原因分析：ArrayList通過下標直接獲取值，而LinkedList需要通過移動指針（很費時）來獲取對應值，每取一個數都要從頭或者從尾部開始移動指針來獲取對應的值。
remove：在數據量小的情況下，LinkedList的remove速度明顯比ArrayList快，但是一旦數據量非常的大，并且刪除的數據都是隨機分布時，LinkedList的速度會非常的慢。
原因分析：ArrayList的remove刪除元素后，需要左移一位（比較耗時），但是LinkedList的remove操作，先通過get方法獲取指定的值，因為get方法需要通過移動指針來獲取指定值，一旦數據量非常大時，get操作非常的耗時。所以導致一旦數據量很大，并且隨機刪除元素時，LinkedList的速度反而很慢。數據量小的情況下，LinkedList的remove的速度要快。
新聞熱點
疑難解答
