數據結構之鏈表(Linked list)
說明：如果仔細閱讀完全文後，可能感覺有些不統一，這裡先說明下原因。
鏈表尾引用不統一：在介紹單鏈表時，只有一個鏈表首部的引用(head) 指向第一個節點。你看到後面關於雙鏈表及循環列表時，除了指向第一個節點的引用 還有指向最後一個節點（尾部）的引用。
這樣做主要是，鏈表設計可能包含尾部的引用，也可能不包含，在最後關於時間複雜度的對比也做了區分。個人也傾向添加尾部引用，但為了完整性 以及 更好的對比理解有無尾部引用的差異，所以在單鏈表 是沒有尾部引用設計 來實現。單鏈表 總結的比較詳細，每個關鍵操作 都有程式碼及示意圖。
命名不統一： 是單鏈表時 首部引用使用的head，而雙鏈表直接使用的JDK源碼中的程式碼介紹（沒做任何改動） first和last。那時單鏈表已經弄好了，程式碼及示意圖改起來比較麻煩，而且個人更喜歡head的命名。
這些完全不會影響理解的。
鏈表概述
鏈表(Linked list)也是一種線性數據結構，通過每個節點中的指針(引用)依次連接 形成的順序存儲。
單鏈表(Singly linked list)
單鏈表中每個元素(鏈表中稱為節點，node)包含兩部分:數據部分 和 一個指向下一個節點的引用。最後一個節點指向為null。
鏈表的入口點稱為head，它是第一個節點的引用。如果鏈表為空 則head指向為null。
示意圖：
雙鏈表(Doubly linked list)
雙鏈表中每個節點包含3個部分：數據部分 和兩個引用，一個指向下個節點(next) 另一個指向前一個節點(previous)。
示意圖：
循環鏈表(Circular linked list)
最後一個節點引用 指向 第一個節點(或者head)。
單鏈表和雙鏈表都可以形成循環鏈表，如下示意圖(上面一個是單循環鏈表，後面一個是雙循環鏈表)：
鏈表操作
單鏈表操作
節點定義：定義節點中的數據項 和 下一個節點引用。
//E->anyType object private static class Node<E> { //數據項 private E data; //指向next節點的引用 private Node<E> next; //構造 public Node(E data, Node<E> next) { this.data = data; this.next = next; } }
head定義：指向第一個節點(即鏈表首部)的引用，初始化為null
private Node<E> head = null;
插入
-
插入鏈表首部
創建一個節點，節點的next指向head的引用，然後讓head指向新建的節點即可。
若head為null，即當前鏈表為空，即向鏈表中插入新建的節點, 節點的next指向null。
public void addFirst(E item) { head = new Node<E>(item, head); }
變化如下示意圖
-
插入目標節點的前面
目標節點數據為key，在目標節點前插入新的節點(數據為toInsert)。
具體過程看下面程式碼及注釋。
public void insertBefore(E key, E toInsert) { //若head為null，即鏈表為空，不存在目標節點 直接返回 if(head == null) return; //若head指向的鏈表第一個節點 就是目標節點，即要把新建節點插入鏈表首部 if(head.data.equals(key)) { addFirst(toInsert); return; } Node<E> prev = null; Node<E> curr = head; //curr定義了 指向當前節點，prev指向當前節點的上個節點。一直順序查找，若找到目標節點(數據為key)，則curr指向目標節點，prev指向了目標節點的上個節點。 while(curr != null && !curr.data.equals(key)) { prev = curr; curr = curr.next; } //若curr不為空，即找到目標節點，在curr和prev之間插入了新節點（數據為toInsert）。若curr為null，即沒找到。 if(curr != null) prev.next = new Node<E>(toInsert, curr); }
示意圖如下（鏈表不為空 且 目標節點不是第一個節點）：
-
插入某個節點後面
相比上面(插入某節點的前面)比較容易，只需一個指向當前節點的臨時變數即可。查找到目標節點後，即在之後插入新節點即可。
public void insertAfter(E key, E toInsert) { Node<E> curr = head; //查找目標節點，找到即curr指向目標節點 while(curr != null && !curr.data.equals(key)) { curr = curr.next; } //curr不為null，即找到目標節點。在之後插入即可。 if(curr != null) curr.next = new Node<E>(toInsert, curr.next); }
示意圖：
-
插入鏈表尾部
若head為null，則鏈表為空。插入鏈表首部即可。
若不為空，使用臨時變數tmp從head依次往後遍歷，當tmp的next為null時即鏈表尾部，插入到後面即可。
public void addLast(E item) { if(head == null) { addFirst(item); } else { Node<E> tmp = head; while(tmp.next != null) tmp = tmp.next; tmp.next = new Node<E>(item, null); } }
刪除
有點類似插入。
下面以刪除某指定數據的節點為例。
public void remove(E key) { //head為null，即鏈表為空 if(head == null) throw new RuntimeException("linkedlist is null, cannot delete"); //鏈表第一個節點即目標節點，改變head指向下個節點就可以了。 if(head.data.equals(key)) { head = head.next; return; } Node<E> prev = null; Node<E> curr = head; //查找，若找到即curr指向目標節點，prev指向目標節點的上個節點 while(curr != null && !curr.data.equals(key)) { prev = curr; curr = curr.next; } //curr為null，即沒找到 if(curr == null) throw new RuntimeException("cannot find your node, cannot delete"); //curr不為null,刪除目標節點（即改變prev的next 指向curr的next即可） prev.next = curr.next; }
示意圖：
註：上述插入或刪除操作中，都有查找或遍歷的過程。因此查找或遍歷不單獨列出。
雙鏈表操作
在Java中實現的LinkedList類是一個雙鏈表，因此直接使用了JDK源碼說明（只在程式碼中添加了注釋，沒做任何修改）。
下面是節點及這兩個引用的程式碼:類中定義了兩個引用，分別指向鏈表的首部和尾部，
transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first;//指向首部(第一個節點) /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ 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; } }
插入到鏈表首部
具體看下面的程式碼注釋和示意圖。
/** * Links e as first element. */ private void linkFirst(E e) { //f指向first指向的節點。即f和first同時指向第一個節點。f在方法中標誌 鏈表插入前的第一個節點 final Node<E> f = first; //創建新的節點，節點的prev指向null,next指向f(即鏈表插入前第一個節點) final Node<E> newNode = new Node<>(null, e, f); //first指向新節點(鏈表首部已改變) first = newNode; if (f == null) //若f為null，即插入前鏈表是空的，插入到新節點既是開始節點也是結束節點，所以last也指向了它 last = newNode; else //如果f不為空，則讓f(插入前的第一個節點)的prev指向新節點就完成了。 f.prev = newNode; size++; modCount++; }
示意圖：
這個是f指向不為空的情況示意圖。
若f為null,則沒有節點指向新建節點，同時新建節點的next指向的是null, 尾部引用last也會指向新建節點。
詳細點就是：
第一步—紅色：final Node<E> f = first；
第二步—橙色： final Node<E> newNode = new Node<>(null, e, f);
第三步—綠色：first = newNode;
第四步—深藍： f.prev = newNode;
插入到某個元素前面
這裡是目標節點已經找到了後的操作。查找目標節點可以參考單鏈表中的程式碼。
下面程式碼：用e新建節點，插入到succ節點之前。
/** * Inserts element e before non-null Node succ. */ void linkBefore(E e, Node<E> succ) { // assert succ != null; //這裡把succ稱為目標節點。succ在這裡是已經查找到並存在的，查找過程可參考單鏈表中相關程式碼。 //用pred指向 目標節點succ的上個節點。 final Node<E> pred = succ.prev; //新建節點，prev指向pred 即新建節點的prev指向目標節點的上個節點，next指向目標節點 final Node<E> newNode = new Node<>(pred, e, succ); //目標節點的prev指向 新建節點 succ.prev = newNode; if (pred == null) //若pred為null 是目標節點上個節點為null，即鏈表插入前只有一個節點，所以first會指向新建節點。 first = newNode; else //若pred不為null,目標節點的上個節點的next指向新節點 pred.next = newNode; size++; modCount++; }
插入到鏈表尾部
因為有兩個引用first、last分別指向鏈表首部和鏈表尾部。這樣尾部操作就變得和首部操作一樣容易，不需要找到鏈表尾部才能插入。看完上面這個應該很簡單，不做解釋了。
/** * Links e as last element. */ 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++; }
刪除
源碼中，首先查找到數據與o相同的第一個節點，在通過unlink刪除該節點，並返回狀態。
查找那考慮了o是否為null，很嚴謹。o==null?get(i)==null:o.equals(get(i))。jdk文檔很多地方說明都可以看到，如果null去執行equals，就會出現Null pointer access：的異常了，值得注意。
/** * Removes the first occurrence of the specified element from this list, * if it is present. If this list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * {@code i} such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns {@code true} if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return {@code true} if this list contained the specified element */ public boolean remove(Object o) { //這裡就是區分o是否為null，找到第一個指定element的節點，通過unlink刪除。 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; } /** * Unlinks non-null node x. */ 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) { //prev為null 即x是首部(第一個節點)，first指向next即可 first = next; } else { //prev不為null，x與prev之間關聯即斷開。prev的next指向next了，x的prev為null prev.next = next; x.prev = null; } //同prev處理類似，斷開x與next聯繫 if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
示意圖是prev和next都不為null的情況：
橙色—>prev.next = next; x.prev = null;
紅色—> next.prev = prev; x.next = null;
最後x.item E也被置為null,size–。x被刪除。
循環鏈表
循環鏈表的最後一個節點有指向第一個節點的引用。
僅已單循環鏈表為例。
下面是幾個操作示例，可以看下程式碼和注釋，不做詳細說明了。看過上面應該很容易理解。
private Node<E> head = null; private Node<E> tail = null; private class Node<E> { E value; Node<E> next; public Node(E value) { this.value = value; } } //往尾部(即tail節點之後)添加節點 public void addNode(E value) { Node<E> newNode = new Node<>(value); if (head == null) { //head為null，即鏈表為空，head指向新建節點。 head = newNode; } else { tail.next = newNode; } //tail指向新節點，即新節點相當於鏈表的尾部 tail = newNode; //tail.next即新節點next指向head，形成環 tail.next = head; } //查找，鏈表中是否包含數據為searchValue的節點 public boolean containsNode(E searchValue) { Node<E> currentNode = head; if (head == null) { return false; } else { //以head開始依次向後查找，直到碰到的仍是head停止。找到返回 do { if (currentNode.value == searchValue) { return true; } currentNode = currentNode.next; } while (currentNode != head); return false; } } //刪除查找到的第一個數據為valueToDelete的節點 public void deleteNode(E valueToDelete) { Node<E> currentNode = head; if (head != null) { if (currentNode.value == valueToDelete) { //head節點且值為valueToDelete head = head.next; tail.next = head; } else { //以head開始依次向後查找，直到碰到的仍是head停止。找到刪除 do { Node<E> next = currentNode.next; if (next.value == valueToDelete) { currentNode.next = next.next; break; } currentNode = currentNode.next; } while (currentNode != head); } } }
鏈表與數組比較
簡單做了個表格
|
鏈表
|
數組
|
|
動態分配：需要時才分配記憶體
|
固定分配：大小固定，new時即分配所有記憶體
|
|
分散存儲：記憶體中不連續存儲
|
連續存儲：記憶體中連續存儲
|
|
總量限制：由於分散存儲，受記憶體總量限制
|
使用限制：由於連續存儲，若無合適連續控制項即無法完成分配，且容易形成記憶體碎片
|
|
插入/刪除方便：改變節點中指向next的或者prev的引用即可
|
插入/刪除代價大：需創建新數組並移動元素
|
|
有記憶體浪費：節點中需額外存儲next或prev的資訊
|
無記憶體浪費：數組元素只存放數據
|
|
順序訪問：在某個節點沿某一方向只能逐一訪問
|
隨機訪問：可以直接計算得到某一元素的地址
|
鏈表的一些操作複雜度
|
操作
|
鏈表
|
數組
|
|
訪問(訪問第N個元素)
|
O(n)
|
O(1)
|
|
插入到首部
|
O(1)
|
O(n)
|
|
插入到尾部
|
有尾部引用tail:O(1)
無尾部引用O(n)
|
O(n)
|
|
插入到中部
|
查找時間+O(1)~=O(n)
|
O(n) |
|
查找
|
O(n)
|
O(n) |
| 刪除 |
類似插入，看刪除位置或者鏈表的設計
|
O(n)
|
