LinkedList 一個雙向鏈表。
本身是基于鏈表進行封裝的列表, 所以具備了鏈表的特性: 變更簡單, 容量是無限的, 不必像數(shù)組提前聲明容量等。
同時 LinkedList 支持存儲包括 null 在內(nèi)的所有數(shù)據(jù)類型。

1 鏈表

了解 LinkedList 之前, 我們需要先了解一下雙向鏈的特點

1. 單鏈表, 雙鏈表, 循環(huán)鏈表的定義, 可以看一下這個
2. 鏈表內(nèi)存是散亂的, 每一個元素存儲本身內(nèi)存地址的同時還存儲下一個元素的地址
3. 鏈表具備了增刪快, 查找慢的特點
4. LinkedList 是基于雙向鏈表設(shè)計的, 所以具備了鏈表的特點

2 LinkedList 中每個節(jié)點的定義

private static class Node<E> {/** 當前節(jié)點的內(nèi)容 */E item;/** 下一個節(jié)點 */Node<E> next;/** 上一個節(jié)點 */Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {// 當前節(jié)點的數(shù)據(jù) = elementthis.item = element;// 當前節(jié)點的后置節(jié)點 = nextthis.next = next;// 當前節(jié)點的前置節(jié)點 = prevthis.prev = prev;}
}

Node 節(jié)點中除了指向下一個節(jié)點的 next, 還包含指向上一個節(jié)點的 prev, 所以 LinkedList 是一個雙向的鏈表。

3 LinkedList 中的幾個屬性

public LinkedList<E> {transient int size = 0;transient Node<E> first;transient Node<E> last;
}

3.1 size

表示當前鏈表中的節(jié)點個數(shù)。

3.2 first

整個雙向鏈表的頭節(jié)點

3.3 last

整個雙向鏈表的尾節(jié)點

重要的就這個幾個屬性了

4 LinkedList 的構(gòu)造方法

public LinkedList<E> {// 構(gòu)造函數(shù) 1: 無參構(gòu)造函數(shù)public LinkedList() {}// 構(gòu)造函數(shù) 2: 給定一個 Collection 的構(gòu)造public LinkedList(Collection<? extends E> c) {// 省略}
}

4.1 無參的構(gòu)造函數(shù)

public LinkedList() {
}

就是單純的聲明 LinkedList 的實例, 沒有其他的邏輯了

4.2 給定一個 Collection 的構(gòu)造

public LinkedList(Collection<? extends E> c) {// 調(diào)用自身無參的構(gòu)造函數(shù)this();// 將集合 c 添加到當前的鏈表中addAll(c);
}/*** 將集合對象全部添加到當前鏈表中*/
public boolean addAll(Collection<? extends E> c) {// 調(diào)用 addAll 重寫方法在 size 的位置添加數(shù)據(jù)return addAll(size, c);
}/*** 指定位置的批量插入*/
public boolean addAll(int index, Collection<? extends E> c) {// 判斷 0 <= index <= size, 不滿足拋出異常checkPositionIndex(index);// 集合轉(zhuǎn)為數(shù)組Object[] a = c.toArray();int numNew = a.length;// 需要插入的集合沒有數(shù)據(jù), 直接結(jié)束if (numNew == 0)return false;// pred: 新增的元素的將要插入的位置的前一個節(jié)點  // succ: 新增的元素的將要插入的位置的節(jié)點// 如果新增的元素的節(jié)點位置為 a, 那么 pred 就是 a 的前一位的節(jié)點, succ 就是 a 節(jié)點Node<E> pred, succ;// 需要添加的元素剛好追加在已有的后面的if (index == size) {succ = null;pred = last;} else {// 獲取指定位置的節(jié)點succ = node(index);pred = succ.prev;}    for (Object o : a) {E e = (E) o;Node<E> newNode = new Node<>(pred, e, null);// 第一次創(chuàng)建時, 那么第一個節(jié)點就是 first節(jié)點if (pred == null)first = newNode;else// 將 pred 的下一個節(jié)點指向新創(chuàng)建的節(jié)點pred.next = newNode;  // 將 pred 改為當前節(jié)點, 方便下一個元素操作pred = newNode;    }   // succ 是為空的, 表示直接在已有的數(shù)據(jù)后面追加元素的話, 所以將最后節(jié)點設(shè)置為新增元素的最后一個元素的節(jié)點if (succ == null) {last = pred;} else {// 原有數(shù)據(jù)后半部分拼接到現(xiàn)在鏈表的后半部分pred.next = succ;succ.prev = pred;} // 當前的長度size += numNew;// 修改次數(shù)加1 modCount++;return true;
}/*** 校驗 index 的值滿足:  0 <= index <= size*/
private void checkPositionIndex(int index) {if (!isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}/** 判斷 index 是否大于等于 0 并且小于等于 size*/
private boolean isPositionIndex(int index) {return index >= 0 && index <= size;
}/*** 獲取指定位置的節(jié)點*/
Node<E> node(int index) {// 此次做了一個小優(yōu)化: 當要查找的位置小于現(xiàn)有數(shù)據(jù)的一半, 從前往后找, 大于的話, 從后面開始找// size >> 1 相當于 size / 2if (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;}
}

從代碼可知

1. LinkedList 是基于雙向鏈表實現(xiàn)了
2. LinkedList 的數(shù)據(jù)是通過 first(節(jié)點) 和 last(節(jié)點) 和 size 三個共同維護的
3. LinkedList 內(nèi)部的數(shù)據(jù)通過泛型, 保持了自己的類型, 沒有轉(zhuǎn)為 Object。

5 LinkedList 幾個常用的方法

5.1.1 添加數(shù)據(jù)

直接在鏈表末尾添加元素

// 直接添加一個元素
public boolean add(E e) {// 默認新增到鏈表的末尾linkLast(e);return true;
}/*** 將入?yún)⒌脑靥砑拥芥湵淼哪┪?/
void linkLast(E e) {// 獲取鏈表的尾結(jié)點final Node<E> l = last;// 將數(shù)據(jù)封裝為 Node 節(jié)點final Node<E> newNode = new Node<>(l, e, null);// 鏈表的尾結(jié)點等于新的節(jié)點last = newNode;// 如果鏈表一開始的尾結(jié)點為空, 表示鏈表一開始沒有數(shù)據(jù)if (l == null)// 鏈表的頭節(jié)點也等于當前的新節(jié)點first = newNode;else// 一開始的為節(jié)點有值, 將原來的尾結(jié)點的下一個節(jié)點設(shè)置為當前新的節(jié)點l.next = newNode;    // 鏈表個數(shù) + 1size++;// 修改次數(shù) + 1modCount++    
}

指定位置的插入

public void add(int index, E element) {// 判斷 0 <= index <= size, 不滿足拋出異常checkPositionIndex(index);// index == size 要插入的位置剛好在末尾if (index == size)linkLast(element);else // 插入到某個節(jié)點的前面linkBefore(element, node(index));    
}/*** 將元素插入到某個節(jié)點的前面*/
void linkBefore(E e, Node<E> succ) {// 獲取某個節(jié)點的前置節(jié)點final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);// 設(shè)置插入位置的節(jié)點的前置節(jié)點為需要插入的新節(jié)點succ.prev = newNode;// 插入位置的節(jié)點的前置節(jié)點為空, 表示沒有頭節(jié)點if (pred == null)first = newNode;else// 需要插入的位置的前置節(jié)點的下一個節(jié)點為新節(jié)點pred.next = newNode;    // 個數(shù)加 1size++;// 修改次數(shù) + 1modCount++;        
}

在頭部插入

public void addFirst(E e) {linkFirst(e);
}/*** 在鏈表的頭節(jié)點前新增元素*/ 
private void linkFirst(E e) {// 獲取頭節(jié)點final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);// 頭節(jié)點等于新節(jié)點first = newNode;// 原本的頭節(jié)點為空, 表示沒有數(shù)據(jù)if (f == null)// 設(shè)置尾節(jié)點為新節(jié)點last = newNode;else// 設(shè)置原本的頭節(jié)點的前置節(jié)點為當前的節(jié)點f.prev = newNode;size++;modCount++;        
}

還有前面看到的

1. 插入一個 Collection 的 addAll(Collection c)
2. 指定位置的插入一個 Collection 的 addAll(int index, Collection c)

5.1.2 刪除數(shù)據(jù)

直接刪除 (默認刪除第一個元素)

public E remove() {return removeFirst();
}/*** 刪除鏈表第一個元素*/
public E removeFirst() {final Node<E> f = first;// 頭節(jié)點為空if (f == null)throw new NoSuchElementException();return unlinkFirst(f);
}/*** 刪除指定的節(jié)點*/
private E unlinkFirst(Node<E> f) {// 獲取刪除節(jié)點的數(shù)據(jù)final E element = f.item;// 找到刪除元素的下一個元素final Node<E> next = f.next;// 清空刪除元素的信息f.item = null;f.next = null;// 將頭節(jié)點重新設(shè)置為刪除元素的下一個元素first = next;// 如果原本刪除元素就是沒有后續(xù)元素時, 將最后的元素設(shè)置為 nullif (next == null)last = null;else// 將新的第一個元素的前置節(jié)點設(shè)置為 nullnext.prev = null;  // 元素個數(shù) - 1    size--;// 修改次數(shù) + 1modCount++;// 返回數(shù)據(jù)return element;          
}

指定位置的刪除

public E remove(int index) {// 檢測刪除的位置是否正確checkElementIndex(index);return unlink(node(index));
}private void checkElementIndex(int index) {// 如果不滿足  0 <= index < size, 就拋出異常if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}private boolean isElementIndex(int index) {return index >= 0 && index < size;
}E unlink(Node<E> x) {final E element = x.item;// 得到將要移除的元素的后置節(jié)點final Node<E> next = x.next;// 得到將要移除的元素的前置節(jié)點final Node<E> prev = x.prev;// 如果前置節(jié)點為空, 說明移除的為頭節(jié)點, 重新設(shè)置頭節(jié)點為刪除節(jié)點的后置節(jié)點if (prev == null) {first = next;} else {// 將前置節(jié)點的下一個節(jié)點設(shè)置為后置節(jié)點prev.next = next;// 設(shè)置刪除節(jié)點前置節(jié)點為 nullx.prev = null;}// 如果后置節(jié)點為空, 說明移除的為尾節(jié)點, 重新設(shè)置尾節(jié)點為刪除節(jié)點的前置節(jié)點if (next == null) {last = prev;} else {// 將后置節(jié)點的前置節(jié)點設(shè)置為前置節(jié)點next.prev = prev;// 設(shè)置刪除節(jié)點后置節(jié)點為 nullx.next = null;}// 將刪除節(jié)點的數(shù)據(jù)設(shè)置為 nullx.item = null;size--;modCount++;return element;
}

指定刪除元素

public boolean remove(Object o) {// 需要刪除的節(jié)點為 nullif (o == null) {// 找到第一個為 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) {// 找到節(jié)點的數(shù)據(jù)等于要刪除的節(jié)點if (o.equals(x.item)) {unlink(x);return true;}}}
}

除了上面幾個還有

1. 刪除第一個 removeFirst()
2. 刪除最后一個 removeLast()
3. 刪除第一個符合的元素 removeFirstOccurrence(Object o)
4. 刪除最后一個符合的元素 removeLastOccurrence(Object o)

5.1.3 獲取數(shù)據(jù)

獲取指定位置的數(shù)據(jù)

public E get(int index) {// 確保 0 <= index < sizecheckElementIndex(index);// 定位到對應(yīng)位置的節(jié)點的數(shù)據(jù)return node(index).item;
}

獲取第一個的數(shù)據(jù)

public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;
}

獲取最一個的數(shù)據(jù)

public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;
}

5.1.4 更新數(shù)據(jù)

更新指定位置節(jié)點的屬性值

public E set(int index, E element) {// 確保 0 <= index < sizecheckElementIndex(index);// 獲取指定位置的節(jié)點數(shù)據(jù)Node<E> x = node(index);// 獲取指定節(jié)點是舊數(shù)據(jù)E oldVal = x.item;// 更新指定節(jié)點的數(shù)據(jù)x.item = element;// 返回舊數(shù)據(jù)return oldVal;
}

6 LinkedList 補充

1. LinkedList 實現(xiàn)了 Serializable 接口, 但是他的屬性都是設(shè)置為 transient ?

LinkedList 重寫了序列化方法 writeObject 和反序列化方法 readObject。 在序列化中, 重新通過遍歷所有節(jié)點, 把所有節(jié)點數(shù)據(jù)寫入到 ObjectOutputStream。

2. LinkedList 支持 fail-fast 機制 ?

通過繼承關(guān)系可以指定 LinkedList 也是實現(xiàn)了 AbstractList, 具備了 modCount, 在修改中也會增加 modCount 的值, 所以 LinkedList 也支持 fail-fast 機制。

3. LinkedList不是一個線程安全的集合 ?

LinkedList 是線程不安全的, 如果需要保證線程的安全性, 可以考慮使用 Collections.synchronizedList(Lise l) 函數(shù)返回一個線程安全的 LinkedList 類。

4. 不要用 for 遍歷 LinkedList ?

遍歷的代碼

List<String> list2 = new LinkedList<>();
list.add("1");
list.add("2");
list.add("3");for (int i = 0; i < list2.size(); i++) {String item = list2.get(i);System.out.println(item);
}

源碼中涉及的代碼:

public class LinkedList {public E get(int index) {checkElementIndex(index);return node(index).item;}Node<E> node(int 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;}}
}

如上: 我們通過 for 遍歷 LinkedList,

1. 第一次 get(0), node(0), 就是 first 節(jié)點
2. 第二次 get(1), node(1), 就是 first -> node1
3. 第三次 get(2), node(2), 就是 first -> node1 -> node2

每次通過 get() 就是需要從第一個節(jié)點一直找到對應(yīng)的位置, 才能找到需要的節(jié)點。
所以遍歷 LinkedList 可以使用 foreach (foreach 循環(huán)的原理就是迭代器) 或者迭代器。

5. LinkedList 還有其他的作用嗎

LinkedList 實現(xiàn)了 Deque 接口, 所以 LinkedList 可以作為雙端隊列, 同時 LinkedList 的雙向鏈表的特點, 還可以作為 Stack 使用, 但是 LinkedList 的這 2 個功能,
如果沒有什么特殊的要求的話, 都可以使用 ArrayDeque 替代, 后者的性能更好。