死磕 java集合之LinkedList原始碼分析
問題
(1)LinkedList只是一個List嗎?
(2)LinkedList還有其它什麼特性嗎?
(3)LinkedList為啥經常拿出來跟ArrayList比較?
(4)我為什麼把LinkedList放在最後一章來講?
簡介
LinkedList是一個以雙向連結串列實現的List,它除了作為List使用,還可以作為佇列或者棧來使用,它是怎麼實現的呢?讓我們一起來學習吧。
繼承體系
通過繼承體系,我們可以看到LinkedList不僅實現了List介面,還實現了Queue和Deque介面,所以它既能作為List使用,也能作為雙端佇列使用,當然也可以作為棧使用。
原始碼分析
主要屬性
// 元素個數 transient int size = 0; // 連結串列首節點 transient Node<E> first; // 連結串列尾節點 transient Node<E> last;
屬性很簡單,定義了元素個數size和連結串列的首尾節點。
主要內部類
典型的雙鏈表結構。
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() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
兩個構造方法也很簡單,可以看出是一個無界的佇列。
新增元素
作為一個雙端佇列,新增元素主要有兩種,一種是在佇列尾部新增元素,一種是在佇列首部新增元素,這兩種形式在LinkedList中主要是通過下面兩個方法來實現的。
// 從佇列首新增元素 private void linkFirst(E e) { // 首節點 final Node<E> f = first; // 建立新節點,新節點的next是首節點 final Node<E> newNode = new Node<>(null, e, f); // 讓新節點作為新的首節點 first = newNode; // 判斷是不是第一個新增的元素 // 如果是就把last也置為新節點 // 否則把原首節點的prev指標置為新節點 if (f == null) last = newNode; else f.prev = newNode; // 元素個數加1 size++; // 修改次數加1,說明這是一個支援fail-fast的集合 modCount++; } // 從佇列尾新增元素 void linkLast(E e) { // 佇列尾節點 final Node<E> l = last; // 建立新節點,新節點的prev是尾節點 final Node<E> newNode = new Node<>(l, e, null); // 讓新節點成為新的尾節點 last = newNode; // 判斷是不是第一個新增的元素 // 如果是就把first也置為新節點 // 否則把原尾節點的next指標置為新節點 if (l == null) first = newNode; else l.next = newNode; // 元素個數加1 size++; // 修改次數加1 modCount++; } public void addFirst(E e) { linkFirst(e); } public void addLast(E e) { linkLast(e); } // 作為無界佇列,新增元素總是會成功的 public boolean offerFirst(E e) { addFirst(e); return true; } public boolean offerLast(E e) { addLast(e); return true; }
典型的雙鏈表在首尾新增元素的方法,程式碼比較簡單,這裡不作詳細描述了。
上面是作為雙端佇列來看,它的新增元素分為首尾新增元素,那麼,作為List呢?
作為List,是要支援在中間新增元素的,主要是通過下面這個方法實現的。
// 在節點succ之前新增元素 void linkBefore(E e, Node<E> succ) { // succ是待新增節點的後繼節點 // 找到待新增節點的前置節點 final Node<E> pred = succ.prev; // 在其前置節點和後繼節點之間建立一個新節點 final Node<E> newNode = new Node<>(pred, e, succ); // 修改後繼節點的前置指標指向新節點 succ.prev = newNode; // 判斷前置節點是否為空 // 如果為空,說明是第一個新增的元素,修改first指標 // 否則修改前置節點的next為新節點 if (pred == null) first = newNode; else pred.next = newNode; // 修改元素個數 size++; // 修改次數加1 modCount++; } // 尋找index位置的節點 Node<E> node(int index) { // 因為是雙鏈表 // 所以根據index是在前半段還是後半段決定從前遍歷還是從後遍歷 // 這樣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位置處新增元素 public void add(int index, E element) { // 判斷是否越界 checkPositionIndex(index); // 如果index是在佇列尾節點之後的一個位置 // 把新節點直接新增到尾節點之後 // 否則呼叫linkBefore()方法在中間新增節點 if (index == size) linkLast(element); else linkBefore(element, node(index)); }
在中間新增元素的方法也很簡單,典型的雙鏈表在中間新增元素的方法。
新增元素的三種方式大致如下圖所示:
在佇列首尾新增元素很高效,時間複雜度為O(1)。
在中間新增元素比較低效,首先要先找到插入位置的節點,再修改前後節點的指標,時間複雜度為O(n)。
刪除元素
作為雙端佇列,刪除元素也有兩種方式,一種是佇列首刪除元素,一種是佇列尾刪除元素。
作為List,又要支援中間刪除元素,所以刪除元素一個有三個方法,分別如下。
// 刪除首節點 private E unlinkFirst(Node<E> f) { // 首節點的元素值 final E element = f.item; // 首節點的next指標 final Node<E> next = f.next; // 新增首節點的內容,協助GC f.item = null; f.next = null; // help GC // 把首節點的next作為新的首節點 first = next; // 如果只有一個元素,刪除了,把last也置為空 // 否則把next的前置指標置為空 if (next == null) last = null; else next.prev = null; // 元素個數減1 size--; // 修改次數加1 modCount++; // 返回刪除的元素 return element; } // 刪除尾節點 private E unlinkLast(Node<E> l) { // 尾節點的元素值 final E element = l.item; // 尾節點的前置指標 final Node<E> prev = l.prev; // 清空尾節點的內容,協助GC l.item = null; l.prev = null; // help GC // 讓前置節點成為新的尾節點 last = prev; // 如果只有一個元素,刪除了把first置為空 // 否則把前置節點的next置為空 if (prev == null) first = null; else prev.next = null; // 元素個數減1 size--; // 修改次數加1 modCount++; // 返回刪除的元素 return element; } // 刪除指定節點x E unlink(Node<E> x) { // x的元素值 final E element = x.item; // x的前置節點 final Node<E> next = x.next; // x的後置節點 final Node<E> prev = x.prev; // 如果前置節點為空 // 說明是首節點,讓first指向x的後置節點 // 否則修改前置節點的next為x的後置節點 if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } // 如果後置節點為空 // 說明是尾節點,讓last指向x的前置節點 // 否則修改後置節點的prev為x的前置節點 if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } // 清空x的元素值,協助GC x.item = null; // 元素個數減1 size--; // 修改次數加1 modCount++; // 返回刪除的元素 return element; } // remove的時候如果沒有元素丟擲異常 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } // remove的時候如果沒有元素丟擲異常 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } // poll的時候如果沒有元素返回null public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } // poll的時候如果沒有元素返回null public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); } // 刪除中間節點 public E remove(int index) { // 檢查是否越界 checkElementIndex(index); // 刪除指定index位置的節點 return unlink(node(index)); }
刪除元素的三種方法都是典型的雙鏈表刪除元素的方法,大致流程如下圖所示。
在佇列首尾刪除元素很高效,時間複雜度為O(1)。
在中間刪除元素比較低效,首先要找到刪除位置的節點,再修改前後指標,時間複雜度為O(n)。
棧
前面我們說了,LinkedList是雙端佇列,還記得雙端佇列可以作為棧使用嗎?
public void push(E e) { addFirst(e); } public E pop() { return removeFirst(); }
棧的特性是LIFO(Last In First Out),所以作為棧使用也很簡單,新增刪除元素都只操作佇列首節點即可。
總結
(1)LinkedList是一個以雙鏈表實現的List;
(2)LinkedList還是一個雙端佇列,具有佇列、雙端佇列、棧的特性;
(3)LinkedList在佇列首尾新增、刪除元素非常高效,時間複雜度為O(1);
(4)LinkedList在中間新增、刪除元素比較低效,時間複雜度為O(n);
(5)LinkedList不支援隨機訪問,所以訪問非佇列首尾的元素比較低效;
(6)LinkedList在功能上等於ArrayList + ArrayDeque;
彩蛋
java集合部分的原始碼分析全部完結,整個專題以ArrayList開頭,以LinkedList結尾,我覺得非常合適,因為ArrayList代表了List的典型實現,LInkedList代表了Deque的典型實現,同時LinkedList也實現了List,通過這兩個類一首一尾正好可以把整個集合貫穿起來。
還記得我們一共分析了哪些類嗎?
下一章,筆者將對整個java集合做一個總結,並提出一些閱讀原始碼過程中的問題,敬請期待^^
歡迎關注我的公眾號“彤哥讀原始碼”,檢視更多原始碼系列文章, 與彤哥一起暢遊原始碼的海洋。