[TOC] ## LinkedList :-:  ### 1\. 概覽 **LinkedList 底層是基于雙向鏈表實現的**，也是實現了 List 接口，所以也擁有 List 的一些特點 (JDK1.7/8 之后取消了循環，修改為雙向鏈表) 。 LinkedList 同時實現了 List 接口和 Deque 接口，也就是說它既可以看作一個順序容器，又可以看作一個隊列（Queue），同時又可以看作一個棧（Stack）。這樣看來， LinkedList 簡直就是個全能冠軍。當你需要使用棧或者隊列時，可以考慮使用 LinkedList ，一方面是因為 Java 官方已經聲明不建議使用 Stack 類，更遺憾的是，Java里根本沒有一個叫做 Queue 的類（它是個接口名字）。 關于棧或隊列，現在的首選是 ArrayDeque，它有著比 LinkedList （當作棧或隊列使用時）有著更好的性能。 基于雙向鏈表實現，內部使用 Node 來存儲鏈表節點信息。 ~~~java private static class Node<E> { E item; Node<E> next; Node<E> prev; } ~~~ 每個鏈表存儲了 Head 和 Tail 指針： ~~~java transient Node<E> first; transient Node<E> last; ~~~ LinkedList 的實現方式決定了所有跟下標相關的操作都是線性時間，而在首段或者末尾刪除元素只需要常數時間。為追求效率*LinkedList*沒有實現同步（synchronized），如果需要多個線程并發訪問，可以先采用`Collections.synchronizedList()`方法對其進行包裝。 ### 2\. add() :-:  add() 方法有兩個版本，一個是`add(E e)`，該方法在 LinkedList 的末尾插入元素，因為有 last 指向鏈表末尾，在末尾插入元素的花費是常數時間。只需要簡單修改幾個相關引用即可；另一個是`add(int index, E element)`，該方法是在指定下表處插入元素，需要先通過線性查找找到具體位置，然后修改相關引用完成插入操作。 ~~~java // JDK 1.8 public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } ~~~ `add(int index, E element)`的邏輯稍顯復雜，可以分成兩部分 1. 先根據 index 找到要插入的位置； 2. 修改引用，完成插入操作。 ~~~java public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } ~~~ 上面代碼中的`node(int index)`函數有一點小小的 trick，因為鏈表雙向的，可以從開始往后找，也可以從結尾往前找，具體朝那個方向找取決于條件`index < (size >> 1)`，也即是 index 是靠近前端還是后端。 ### 3\. remove() remove() 方法也有兩個版本，一個是刪除跟指定元素相等的第一個元素`remove(Object o)`，另一個是刪除指定下標處的元素`remove(int index)`。 :-:  兩個刪除操作都要： 1. 先找到要刪除元素的引用； 2. 修改相關引用，完成刪除操作。 在尋找被刪元素引用的時候`remove(Object o)`調用的是元素的 equals 方法，而`remove(int index)`使用的是下標計數，兩種方式都是線性時間復雜度。在步驟 2 中，兩個`revome()`方法都是通過`unlink(Node<E> x)`方法完成的。這里需要考慮刪除元素是第一個或者最后一個時的邊界情況。 ### 4\. get() ~~~java public E get(int index) { checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } ~~~ 由此可以看出是使用二分查找來看`index`離 size 中間距離來判斷是從頭結點正序查還是從尾節點倒序查。 * node() 會以`O(n/2)`的性能去獲取一個結點 * 如果索引值大于鏈表大小的一半，那么將從尾結點開始遍歷 這樣的效率是非常低的，特別是當 index 越接近 size 的中間值時。 ### 5\. 總結 * LinkedList 插入，刪除都是移動指針效率很高。 * 查找需要進行遍歷查詢，效率較低。 ### 6\. ArrayList 與 LinkedList * ArrayList 基于動態數組實現，LinkedList 基于雙向鏈表實現； * ArrayList 支持隨機訪問，LinkedList 不支持； * LinkedList 在任意位置添加刪除元素更快。 ### 面試題：ArrayList 與 LinkedList哪個更占空間？ https://www.cnblogs.com/yeya/p/13430797.html