java基礎集合類——LinkedList 源碼略讀

1.概覽

LinkedList是java的動態數組另一種實現方式，底層是基于雙向鏈表，而不是數組。

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList實現了動態數組與雙向隊列兩個接口，提供了兩種方法集合，可以用來實現隊列、棧之類的功能。

2. 成員變量

先來看成員變量

    transient int size = 0;transient Node<E> first;transient Node<E> last;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;}}

鏈表一般就是有個head的節點就能完成對應的工作。LinkedList實現了雙向鏈表，除了head,還有一個last節點和一個size參數，這主要是為了效率考慮，不然查詢一次長度或者尾都得來一次全鏈路迭代，太慢了。Node內部類就不說了，非常簡單的一個節點類。

3. 方法

3.1 構造方法

    public LinkedList() {// 此時first=last=null,size=0}public LinkedList(Collection<? extends E> c) {this();addAll(c);}

3.2 添加元素

添加一個元素

    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;elsel.next = newNode;size++;modCount++;}    

很簡單的添加邏輯，再來看一下addAll的實現

    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;elsepred.next = newNode;pred = newNode;}if (succ == null) {last = pred;} else {pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;}

3.3 刪除元素

    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;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;}

3.4 修改元素

    public E set(int index, E element) {checkElementIndex(index);Node<E> x = node(index);E oldVal = x.item;x.item = element;return oldVal;}

3.5 檢索元素

    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;}}

檢索是LinkedList比較值得看的一個方法，java的實現很簡單，先判斷index是大于當前size的一半還是小于，如果是大于則從尾節點往前否則從首結點往后檢索。從代碼上看，雖然雙向鏈表的實現讓性能快了一點，但還是O(n)的耗時，我覺得后續版本的優化可以向HashMap那樣，當判斷LinkedList的size大于一個閾值時可以將雙向鏈接改造為紅黑樹或者跳表，從而實現O(lgn)的性能，當然這樣也對空間消耗更多一點。

3.6 清空元素

    public void clear() {// Clearing all of the links between nodes is "unnecessary", but:// - helps a generational GC if the discarded nodes inhabit//   more than one generation// - is sure to free memory even if there is a reachable Iteratorfor (Node<E> x = first; x != null; ) {Node<E> next = x.next;x.item = null;x.next = null;x.prev = null;x = next;}first = last = null;size = 0;modCount++;}

從代碼上看，LinkedList的clear方法是沒有內存泄漏問題的，注意有個for循環，這里是為了gc優化。