JDK源碼閱讀——LinkedList

2019-11-11 01:45:05

字體：大中小

來源：轉載

供稿：網友

序

作為數據結構中最基礎的兩種結構，數組與鏈表，在java中都有對應的實現——ArrayList與LinkedList。本文主要分析一下LinkedList中的比較重要的源碼。 LinkedList是實現了List與Deque的雙向鏈表。他不是線程安全的，在多線程情況下需要用戶手動保證線程安全性。系統推薦使用下面的方法來保證線程安全。

List list = Collections.synchronizedList(new LinkedList(...));

Field

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

構造器

//構造一個普通的新鏈表對象 public LinkedList() { } //構造一個新鏈表，并將入參集合append到新鏈表中 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }//append的核心代碼在這里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; //從尾部開始appedn if (index == size) { succ = null; pred = last; } else { //從中間開始append,如圖1 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; }

上述循環的作用就是鏈表的插入操作，如圖2。不停的移動pred，把輸入的集合全都append到鏈表尾部。