ArrayList和LinkedList都是List的實現類，是在日常開發中經常被使用到的兩個集合，我們來結合源碼看下兩個集合的不同之處。

先來看下ArrayList的源碼：

// 默認的初始化大小private static final int DEFAULT_CAPACITY = 10;

ArrayList的底層數數組結構，我們創建ArrayList的時候，可以使用指定數組大小的構造函數或者直接是默認的構造函數。當使用默認構造函數的時候，數組的初始化大小是0，當第一次調用add()方法的時候，會變成默認的初始化大小10。

使用ArrayList的最多的就是add()方法了，我們直接來看add()方法的源碼：

public boolean add(E e) {//調用ensureCapacityInternal()看是否需要初始化以及擴容ensureCapacityInternal(size + 1); // Increments modCount!!//將數據添加到數組中elementData[size++] = e;return true;}

來看ensureCapacityInternal()方法：

private void ensureCapacityInternal(int minCapacity) {// 如果elementData為空，也就是第一次add的話，則返回默認容量和minCapacity中的最大值if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}// ensureExplicitCapacity()方法則進一步判斷是否需要擴容ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {modCount++;// 如果添加后的容量大于原來的容量，則調用擴容方法if (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// 原來的容量int oldCapacity = elementData.length;//將原來的容量右移一位，相當于是*2^-1，總容量為原來的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 將舊數據拷貝到新數組中elementData = Arrays.copyOf(elementData, newCapacity);}

ArrayList的add方法邏輯很清晰，也沒有過多的方法嵌套，就是添加數據到數組中，判斷一下是否需要擴容，需要的話就進行擴容操作。

山東掌趣網絡科技

get方法：

public E get(int index) {rangeCheck(index);checkForComodification();return ArrayList.this.elementData(offset + index);}

get()就是直接獲取該索引處的元素。

接下來我們就來分析下remove()方法：

remove(int index)方法：

public E remove(int index) {// 越界檢查rangeCheck(index);modCount++;E oldValue = elementData(index);// 判斷是否是最后一個元素int numMoved = size - index - 1;// 如果不是，則需要將index之后的元素往前移動一位if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);// 將最后一個元素刪除，幫助GCelementData[--size] = null; // clear to let GC do its workreturn oldValue;}

remove(Object o)方法：

public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;}

remove邏輯比較簡單，直接來看fastRemove()方法：

private void fastRemove(int index) {// modCount，繼承于AbstractList。記錄著集合的修改次數modCount++;int numMoved = size - index - 1;// 判斷是否是最后一個元素，這里的操作和remove(index)一樣if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its work}

接下來我們來看下刪除的例子：

山東掌趣網絡科技

public class ArrayListDemo {public static void main(String[] args) {List list=new ArrayList();list.add("jack");list.add("tom");list.add("tom");list.add("mary");list.add("danel");System.out.println("刪除之前的集合--:"+list);// for循環刪除字符串為tom的元素for(int i=0;i

我們看到，集合中元素為“tom”的并未完全刪除掉，結合上面remove(int index)的源碼，List調用remove(index)方法后，會移除index位置上的元素，index之后的元素就全部依次往前移，當刪除掉一個元素后，size的值就變成了4，此時tom的索引位置為1，由于之前遍歷的時候，i已經是1了，再次遍歷的時候，i是從2開始，所以tom這個元素邊不會再被遍歷到，所以會存在漏刪的情況。

山東掌趣網絡科技

再來看一個例子，使用foreach來遍歷刪除:

for(String name : list){if("tom".equals(name)){list.remove(name);}}Exception in thread "main" java.util.ConcurrentModificationExceptionat java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)at java.util.ArrayList$Itr.next(ArrayList.java:851)at ArrayListDemo.main(ArrayListDemo.java:14)

代碼報了ConcurrentModificationException異常，為什么會出現這個異常呢，還記得上面源碼分析的時候提到過一個成員變量modCount嗎，modCount繼承于AbstractList，記錄著集合的修改次數，也就是每次add或者remove的話modCount值都會被修改，根據報錯的地方，跟蹤到它的源碼：

final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}

expectedModCount表示對ArrayList修改次數的期望值，我們來看下expectedModCount的源碼位置，是內部類Itr的成員變量：

private class Itr implements Iterator {int cursor; // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint expectedModCount = modCount;public boolean hasNext() {return cursor != size;}、、、、

foreach之所以能工作，是因為這些集合類都實現了Iterable接口，該接口中定義了Iterator迭代器的產生方法，并且foreach就是通過Iterable接口在序列中進行移動，foreach語法最終被編譯器轉為了對Iterator.next()的調用，

每次foreach迭代的時候都有會有兩步操作：

第一步：iterator.hasNext() //判斷是否有下個元素

public boolean hasNext() {return cursor != size;}

第二步：下個元素是什么

public E next() {checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[lastRet = i];}

我們打印的異常也說明了這一點，Iterator初始化的時候將modCount 的值賦給了expectedModCount，此時這是一個固定值，而當調用remove方法的時候，會修改modCount ，當modCount 值與expectedModCount值不相等的時候，就會報ConcurrentModificationException異常。

那需要怎樣刪除ArrayList的數據呢？我們再看Iterator的源碼，里面有一個刪除的方法：

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

這個remove方法的源碼將修改后的modCount的值又重新復制給了expectedModCount ，所以不會再報ConcurrentModificationException異常，正確的刪除是獲取list集合的迭代器，然后通過迭代器調用它的remove方法。

Iterator iterator = list.iterator();while (iterator.hasNext()){String name = (String)iterator.next();if("tom".equals(name)){iterator.remove();}}

LinkedList源碼分析：

相比于ArrayList，它額外實現了雙端隊列接口Deque，這個接口主要是聲明了隊頭，隊尾的一系列方法。LinkedList是一個雙向鏈表結構，這里定義了鏈表的頭結點和尾結點：

// 鏈表的頭元素transient Node first;// 鏈表的尾元素transient Node last;

LinkedList的內部類，用以表示一個鏈表節點，一個節點除了保持自身的數據外，還持有前，后兩個節點的引用。所以就數據存儲上來說，它相比使用數組作為底層數據結構的ArrayList來說，會更加耗費空間。但也正因為這個特性，它刪除，插入節點很快

private static class Node {E item;Node next;Node prev;Node(Node prev, E element, Node next) {this.item = element;this.next = next;this.prev = prev;}}

每一個元素在LinkedList中都是在Node中存儲，每個Node中同時還存儲了當前元素的前節點和后節點。

我們再來看LikedList的add方法：

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

add方法沒做什么事情，只調用了linkLast()方法，真正做事的是linkLast(E e)，來看下這個方法：

void linkLast(E e) {// 將原尾結點賦值給lfinal Node l = last;// 新節點的頭節點是原集合的尾結點，它自己的尾節點為空final Node newNode = new Node<>(l, e, null);// 將新節點賦值給尾節點last = newNode;// 如果原集合的尾結點是null的話，說明原集合沒有值，它的頭結點就是現 在的新增的數據if (l == null)first = newNode;else //否則的話將原尾結點的下一個節點指向當前新增的數據l.next = newNode;size++; // 集合數量+1modCount++; //修改次數+1}

add()方法是將數據插入到鏈表的尾部，通過add(int index, E element)方法可以在指定位置插入指定元素。

public void add(int index, E element) {// 檢查指針是否越界checkPositionIndex(index);// 如果指定位置是最后一個的話，則直接在尾部插入if (index == size)linkLast(element);elselinkBefore(element, node(index));}

看下linkBefore(E e, Node succ)的源碼:

void linkBefore(E e, Node succ) {// assert succ != null;final Node pred = succ.prev;// 新節點的前驅節點是原索引處節點的前驅節點，next節點是原索引處節點final Node newNode = new Node<>(pred, e, succ);// 將原索引處的節點的前驅節點修改為新的節點succ.prev = newNode;if (pred == null)first = newNode;else//將原前驅節點的next節點修改為新的節點pred.next = newNode;size++;modCount++;}

get方法源碼：

Node node(int index) {// assert isElementIndex(index);// 首先判斷該索引時位于前半段還是后半段if (index < (size >> 1)) {Node x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}

LinkedList的get首先判斷需要獲取的數據在該鏈表的前半段還是后半段，這樣可以減少需要遍歷的數據，由于需要遍歷數據，所以獲取數據的速度會比ArrayList慢。

再來看下刪除的方法

public E remove(int index) {// 檢查下標是否越界checkElementIndex(index);return unlink(node(index));}E unlink(Node x) {// 得到要刪除的元素final E element = x.item;// 獲得刪除元素的前驅和后置節點final Node next = x.next;final Node prev = x.prev;// 前驅節點為null的話說明要刪除的節點是第一個節點if (prev == null) {first = next;} else {// 修改前驅節點的next節點指向被刪除節點的next節點prev.next = next;x.prev = null;}// 后置節點為null的話說明要刪除的節點是最后一個節點if (next == null) {last = prev;} else {// 修改next節點的前驅節點指向被刪除節點的前驅節點next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;}

remove(Object o)和remove(int index)稍有差別，但是基本都是調用unlink(Node x)方法。

在使用for循環或者是foreach迭代的時候，和ArrayList一樣，也會有漏刪或者報錯，因此仍然建議使用迭代器中的remove方法進行迭代刪除。

值得一提的是LinkedList還實現Dequeue接口，接口定義了隊列數據結構，元素是有序的(按插入順序)，先進先出

可以利用LinkedList實現一個隊列。LinkedList中的方法：

// 將指定的元素插入此隊列public boolean offer(E e) {return add(e);}// 獲取但不移除此隊列的頭；如果此隊列為空，則返回 null。public E peek() {final Node f = first;return (f == null) ? null : f.item;}// 獲取并移除此隊列的頭，如果此隊列為空，則返回 null。public E poll() {final Node f = first;return (f == null) ? null : unlinkFirst(f);}// 獲取并移除此隊列的頭public E remove() {return removeFirst();}、、、

例如簡單的隊列：

public class DequeDemo {public static void main(String[] args) {Queue queue = new LinkedList();queue.offer("tom");queue.offer("jack");queue.offer("mike");while (queue.peek()!=null){System.out.println(queue.poll());}}}

作為雙端隊列的一些方法，如： addFirst(Object ob):在隊首增加元素addLast(Object obj):在隊尾增加；peekFirst():查看隊首；peekLast:查看隊尾；pollFirst:移除隊首；pollLast:移除隊尾例如：

public class DequeDemo {public static void main(String[] args) {Deque queue = new LinkedList();queue.offer("tom");queue.offer("jack");queue.offer("mike");queue.addFirst("dannel");queue.addLast("mary");while (queue.peek()!=null){System.out.println(queue.poll());}}}danneltomjackmikemary

由于LinkedList底層是用雙向鏈表實現的，沒有初始化大小，也沒有擴容的機制。

總結

ArrayList和LinkedList都實現了List的接口，但是LinkedList還實現了Deque隊列接口，因此還可以當做隊列使用，

ArrayList的底層結構是數組，獲取元素的速度快，但是插入速度相對LinkedList較慢，LinkedList的底層是雙向鏈表結構，插入和刪除比較快，但是查找的速度相對ArrayList較慢。另外ArrayList和LinkedList在并發情況下沒有對數據進行同步，是線程不安全的。

山東掌趣網絡科技