一.?概述
LinkedList 是 Java 集合中比較常用的數(shù)據(jù)結(jié)構(gòu)卢肃，與 ArrayList 一樣幻锁，實現(xiàn)了 List 接口敞映，只不過 ArrayList 是基于數(shù)組實現(xiàn)的沸伏，而 LinkedList 是基于鏈表實現(xiàn)的糕珊。所以 LinkedList 插入和刪除方面要優(yōu)于 ArrayList，而隨機(jī)訪問上則 ArrayList 性能更好毅糟。
除了 LIst 接口之外红选，LinkedList 還實現(xiàn)了 Deque，Cloneable姆另，Serializable 三個接口喇肋。這說明該數(shù)據(jù)結(jié)構(gòu)支持隊列，克隆和序列化操作的蜕青。與 ArrayList 一樣苟蹈，允許 null 元素的存在，且是不支持多線程的右核。
二.?源碼解讀
屬性
LinkedList 提供了以下三個成員變量慧脱。size，first贺喝，last菱鸥。
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
其中 size 為 LinkedList 的大小，first 和 last 分別為鏈表的頭結(jié)點和尾節(jié)點躏鱼。Node 為節(jié)點對象氮采。
private static class Node<E> {
? ?E item;
? ?Node<E> next;
? ?Node<E> prev;
? ?Node(Node<E> prev, E element, Node<E> next) {
? ? ? ?this.item = element;
? ? ? ?this.next = next;
? ? ? ?this.prev = prev;
? ?}
}
Node 是 LInkedList 的內(nèi)部類，定義了存儲的數(shù)據(jù)元素染苛，前一個節(jié)點和后一個節(jié)點鹊漠，典型的雙鏈表結(jié)構(gòu)主到。
構(gòu)造方法
public LinkedList() {}
public LinkedList(Collection<? extends E> c) {
? ?this();
? ?addAll(c);
}
LinkedList 提供了兩個構(gòu)造方法：LinkedList() 和 LinkedList(Collection<? extends E> c)。
LinkedList() 僅僅構(gòu)造一個空的列表躯概，沒有任何元素登钥。size = 0。first 和 last 都為 null娶靡。
后一個構(gòu)造方法構(gòu)造一個包含指定 Collection 中所有元素的列表牧牢，該構(gòu)造方法首先會調(diào)用空的構(gòu)造方法，然后通過 addAll() 的方式把 Collection 中的所有元素添加進(jìn)去姿锭。
調(diào)用 addAll() 方法塔鳍，傳入當(dāng)前的節(jié)點個數(shù) size，此時 size 為
檢查 index 是否越界
將 collection 轉(zhuǎn)換成數(shù)組
遍歷數(shù)組呻此，將數(shù)組里面的元素創(chuàng)建為節(jié)點轮纫，并按照順序連起來。
修改當(dāng)前的節(jié)點個數(shù) size 的值
操作次數(shù) modCount 自增 1.
public boolean addAll(Collection<? extends E> c) {
? ?return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
? ?checkPositionIndex(index);
? ?Object[] a = c.toArray();
? ?int numNew = a.length;
? ?if (numNew == 0)
? ? ? ?return false;
? ?Node<E> pred, succ;
? ?if (index == size) {
? ? ? ?succ = null;
? ? ? ?pred = last;
? ?} else {
? ? ? ?succ = node(index);
? ? ? ?pred = succ.prev;
? ?}
? ?for (Object o : a) {
? ? ? ?@SuppressWarnings("unchecked") E e = (E) o;
? ? ? ?Node<E> newNode = new Node<>(pred, e, null);
? ? ? ?if (pred == null)
? ? ? ? ? ?first = newNode;
? ? ? ?else
? ? ? ? ? ?pred.next = newNode;
? ? ? ?pred = newNode;
? ?}
? ?if (succ == null) {
? ? ? ?last = pred;
? ?} else {
? ? ? ?pred.next = succ;
? ? ? ?succ.prev = pred;
? ?}
? ?size += numNew;
? ?modCount++;
? ?return true;
}
add 操作
添加元素到鏈表末尾
public boolean add(E e) {
? ?linkLast(e);
? ?return true;
}
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 方法直接調(diào)用了 linkLast 方法趾诗，而 linkLast 方法是不對外開放的蜡感。該方法做了三件事情蹬蚁，新增一個節(jié)點恃泪，改變其前后引用，將 size 和 modCount 自增 1犀斋。其中 modCount 是記錄對集合操作的次數(shù)贝乎。
在指定的位置插入元素
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));
}
private boolean isPositionIndex(int index) {
? ?return index >= 0 && index <= size;
}
void linkBefore(E e, Node<E> succ) {
? ?// assert succ != null;
? ?final Node<E> pred = succ.prev;
? ?final Node<E> newNode = new Node<>(pred, e, succ);
? ?succ.prev = newNode;
? ?if (pred == null)
? ? ? ?first = newNode;
? ?else
? ? ? ?pred.next = newNode;
? ?size++;
? ?modCount++;
}
首先檢查下標(biāo)是否越界，然后判斷如果 index == size 則添加到末尾叽粹，否則將該元素插入的 index 的位置览效。其中 node(index) 是獲取 index 位置的節(jié)點，linkBefore 負(fù)責(zé)把元素 e 插入到 succ 之前虫几。
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;
? ?}
}
可以看出 node() 方法這里寫的還是挺贊的锤灿，不是傻乎乎的從頭到尾或者從尾到頭遍歷鏈表，而是將 index 與 當(dāng)前鏈表的一半做對比辆脸，比一半小從頭遍歷但校，比一半大從后遍歷。對于數(shù)據(jù)量很大時能省下不少時間啡氢。
get 操作
很簡單状囱，首先獲取節(jié)點，然后返回節(jié)點的數(shù)據(jù)即可倘是。
public E get(int index) {
? ?checkElementIndex(index);
? ?return node(index).item;
}
remove 操作
移除指定位置的元素
public E remove(int index) {
? ?checkElementIndex(index);
? ?return unlink(node(index));
}
E unlink(Node<E> x) {
? ?// assert x != null;
? ?final E element = x.item;
? ?final Node<E> next = x.next;
? ?final Node<E> prev = x.prev;
? ?if (prev == null) {
? ? ? ?first = next; // 如果移除的是頭節(jié)點亭枷，那么頭結(jié)點后移
? ?} else {
? ? ? ?prev.next = next;
? ? ? ?x.prev = null; ?// 釋放節(jié)點的前一個元素
? ?}
? ?if (next == null) {
? ? ? ?last = prev; // 如果移除的是尾節(jié)點，尾結(jié)點前移
? ?} else {
? ? ? ?next.prev = prev;
? ? ? ?x.next = null; ?// 釋放節(jié)點的后一個元素
? ?}
? ?x.item = null; // 釋放節(jié)點數(shù)據(jù)
? ?size--;
? ?modCount++;
? ?return element;
}
先檢查下標(biāo)是否越界搀崭，然后調(diào)用 unlink 釋放節(jié)點叨粘。
移除指定元素
public boolean remove(Object o) {
? ?if (o == null) {
? ? ? ?for (Node<E> x = first; x != null; x = x.next) {
? ? ? ? ? ?if (x.item == null) {
? ? ? ? ? ? ? ?unlink(x);
? ? ? ? ? ? ? ?return true;
? ? ? ? ? ?}
? ? ? ?}
? ?} else {
? ? ? ?for (Node<E> x = first; x != null; x = x.next) {
? ? ? ? ? ?if (o.equals(x.item)) {
? ? ? ? ? ? ? ?unlink(x);
? ? ? ? ? ? ? ?return true;
? ? ? ? ? ?}
? ? ? ?}
? ?}
? ?return false;
}
判斷要移除的元素是否為 null，然后在遍歷鏈表，找到鈣元素第一次出現(xiàn)的位置升敲，移除并返回 true袍镀。
像其他的常用方法如：getFirst, getLast, removeFirst, removeLast, addFirst, addLast 等都很簡單，掃一眼源碼就能懂冻晤，我這里就不寫了苇羡。
迭代器
LInkedList 的 iterator() 方法是在其父類 AbstractSequentialList 中定義的，最終一路 debug 到 LinkedList 類這里鼻弧。其中 index 為 零设江。
public ListIterator<E> listIterator(int index) {
? ?checkPositionIndex(index);
? ?return new ListItr(index);
}
我們來看看 ListItr。
private Node<E> lastReturned;
? ?private Node<E> next;
? ?private int nextIndex;
? ?private int expectedModCount = modCount;
? ?ListItr(int index) {
? ? ? ?// assert isPositionIndex(index);
? ? ? ?next = (index == size) ? null : node(index);
? ? ? ?nextIndex = index;
? ?}
? ?public boolean hasNext() {
? ? ? ?return nextIndex < size;
? ?}
? ?public E next() {
? ? ? ?checkForComodification();
? ? ? ?if (!hasNext())
? ? ? ? ? ?throw new NoSuchElementException();
? ? ? ?lastReturned = next;
? ? ? ?next = next.next;
? ? ? ?nextIndex++;
? ? ? ?return lastReturned.item;
? ?}
? ? final void checkForComodification() {
? ? ? ?if (modCount != expectedModCount)
? ? ? ? ? ?throw new ConcurrentModificationException();
? ?}
}
篇幅有限 攘轩，我就只貼主要代碼了叉存。由源碼可以看出初始化 ListItr 時，將 nextIndex 指向 index度帮， 也就是零歼捏。如果該集合為空，那么 index == size 為 true笨篷，next 指向?null瞳秽，否則 next 指向下標(biāo)為零的元素，也就是第一個率翅。
hasNext 直接返回 nextIndex < size 簡單明了练俐。下面看看 next 方法，首先檢查 expectedModCount 與 modCount 是否相等冕臭，看似無關(guān)緊要的代碼保證了集合在迭代過程中不被修改[包括新增刪除節(jié)點等]腺晾。然后將 lastReturned 指向 next，next 后移一個節(jié)點辜贵，nextIndex 自增 1悯蝉，并返回 lastReturned 節(jié)點的元素。
總結(jié)
1托慨、從源碼可以看出 LinkedList 是基于鏈表實現(xiàn)的鼻由。如下圖：
2、在查找和刪除某元素時榴芳，區(qū)分該元素為 null和不為 null 兩種情況來處理嗡靡，LinkedList 中允許元素為 null。
3窟感、基于鏈表實現(xiàn)不存在擴(kuò)容問題讨彼。
4、查找時先判斷該節(jié)點位于前半部分還是后半部分柿祈，加快了速度
5哈误、因為基于鏈表哩至，所以插入刪除極快，查找比較慢蜜自。
6菩貌、實現(xiàn)了棧和隊列的相關(guān)方法，所以可作為棧重荠，隊列箭阶，雙端隊列來用。
