數據結構（4）：鏈表的原理和實現
- 2019 年 10 月 4 日
- 筆記
上、簡單的單端鏈表
完整程式碼向下拉
鏈表是一種常用的數據結構，在插入和移除操作中有著優秀的表現，同為數據結構的數組哭暈，其實數組的訪問效率比鏈表高多了有木有。
我們先看一下鏈表的樣子
有同學可能要說了，這不就是我們生活中的交通工具——火車，沒錯鏈表的結構和下圖簡直就是一個模子刻出來的。(咳咳，忽略這靈魂的畫法)
通過火車示意圖可以觀察到，火車由火車頭和n節車廂組成，每節車廂都與下一節車廂相連，能理解這句話，鏈表你就掌握一半了。
以小學掌握的物品分類知識來對上圖進行面向對象抽象，火車整體可以認為是鏈表，火車又由車廂組成的，同樣可以理解鏈表是由節點組成的，鏈表起到了組合節點的作用。
1、創建節點(車廂)
車廂都有哪些特點呢？車廂能存放物品，車廂與下一節車廂相連。
public class Node { public Object data;//存放的數據 public Node next;//指向下一個節點 public Node(Object value) { this.data = value; } //展示節點數據 public void display() { System.out.print(data+" "); } }2、創建鏈表（將車廂組合）
在現實中我們要想查看整個火車由一個十分暴力的方法，那就是找到火車頭，找到火車頭後沿著每節車廂向後查找就可以完整的查看整輛火車。
public class LinkList { private Node first;//第一個節點 }在程式碼中 Node 類已經聲明了指向下一個節點的屬性，所以只需要找到第一個節點，調用next屬性即可無限向後查找。
3、判斷鏈表是否為空
第一個節點為空即為鏈表為空
public boolean isEmpty() { return first == null; }4、添加數據到鏈表的頭部
添加數據到鏈表頭部，就是將新節點的next指向原來的首節點，再將新節點標記為first即可。
public void addFirst(Object value) { Node newNode = new Node(value);//創建新節點 if (isEmpty()) { first = newNode;//沒有節點時直接標記為首節點 } else { newNode.next = first;//新節點next指向舊的首節點 first = newNode; } }5、移除首節點
並非真正意義上的移除，而是將first指向first.next的記憶體地址，而原來的first會被垃圾回收器回收。
public Node removeFirst() { if (isEmpty()) { return null; } Node tmp = first; first = first.next; return tmp; }6、查看鏈表
由於鏈表中的每個節點都有變數指向下一個節點，所有可以使用循環遞進獲取下一個節點實現遍歷的效果。
public void display() { Node current = first;//先從首節點開始 while (current != null) { current.display();//節點不為空，則列印該節點資訊 current = current.next;//獲取當前節點的下個節點重新放入current中 System.out.println(); } }7、根據值查找鏈表中的節點
需要遍歷節點，將每個節點的值都與要查找的值進行比對，如果值不相等就一直循環，直到最後一個節點為空時表示沒有查到。
public Node find(Object value) { if (isEmpty()) { return null; } Node current = first; while (current.data != value) { if (current.next==null){ return null; } current = current.next; } return current; }8、根據值移除節點
移除時同樣遍歷所有節點，但要保存查到節點的之前節點(previous)，如果查到的節點是第一個節點，直接移除第一個，否則就將前一個節點指向要移除節點的下一個。
public Node remove(Object value){ if (isEmpty()) { return null; } Node current = first; Node previous = first; while (current.data != value) { if (current.next==null){ return null; } previous = current; current = current.next; } if (current==first){ removeFirst(); }else{ previous.next=current.next; } return current; }9、完整程式碼
public class LinkList { private Node first;//第一個節點 public void addFirst(Object value) { Node newNode = new Node(value);//創建新節點 if (isEmpty()) { first = newNode;//沒有節點時直接標記為首節點 } else { newNode.next = first;//新節點next指向舊的首節點 first = newNode; } } public Node removeFirst() { if (isEmpty()) { return null; } Node tmp = first; first = first.next; return tmp; } public void display() { Node current = first;//先從首節點開始 while (current != null) { current.display();//節點不為空，則列印該節點資訊 current = current.next;//獲取當前節點的下個節點重新放入current中 System.out.println(); } } public Node find(Object value) { if (isEmpty()) { return null; } Node current = first; while (current.data != value) { if (current.next==null){ return null; } current = current.next; } return current; } public Node remove(Object value){ if (isEmpty()) { return null; } Node current = first; Node previous = first; while (current.data != value) { if (current.next==null){ return null; } previous = current; current = current.next; } if (current==first){ removeFirst(); }else{ previous.next=current.next; } return current; } public boolean isEmpty() { return first == null; } public static void main(String[] args) { LinkList linkList = new LinkList(); linkList.addFirst("a"); linkList.addFirst("b"); System.out.println("-0---"); linkList.remove("a"); linkList.display(); } public class Node { public Object data;//存放的數據 public Node next;//指向下一個節點 public Node(Object value) { this.data = value; } //展示節點數據 public void display() { System.out.print(data+" "); } } }單端鏈表還是有一些不足，比如我們要操作最後一個節點需要遍歷整個鏈表，下一節咱們實現雙端鏈表，提高操作最後一個節點的效率。
中、操作更簡單的雙端鏈表
上節文章中咱們了解了鏈表的結構及原理，但是還有些美中不足的地方，就是無法快速的訪問鏈表中的最後一個節點。
在這節文章中咱們來解決這個問題，一起來吧。
首先先看如何快速訪問尾節點，其實這個可以通過一個變數指向尾節點，在做插入、刪除時更新尾節點即可。
1、創建節點
節點用於存儲數據和下一個節點相連
public class Node { public Object data;//存放的數據 public Node next;//指向下一個節點 public Node(Object value) { this.data = value; } //展示節點數據 public void display() { System.out.print(data + " "); } }2、創建鏈表
操作節點和指向首尾兩個節點
public class DoubleEndLinkList { private Node first;//第一個節點 private Node last;//最後一個節點 }3、向前添加節點
如果加入的節點是第一個節點，這個節點是首節點同時也是尾節點。如果已經有節點則讓新節點指向原來的首節點，讓首節點指向新節點。
public void addFirst(Object value) { Node newNode = new Node(value); if (isEmpty()) { //如果為空，尾節點指向此節點 last = newNode; } //更替新節點 newNode.next = first; first = newNode; }4、向後添加節點
和向前添加相反，因為鏈表中last始終指向最後一個節點，所以操作last節點。
public void addLast(Object value) { Node newNode = new Node(value); if (isEmpty()) { //如果為空，首節點和尾節點指向此節點 first = newNode; last = newNode; return; } //更替尾節點 last.next = newNode; last = newNode; }5、移除首節點
移除首節點時將首節點的下一個節點標記為首節點即可，直到首節點與尾節點相同時(這時也意味這隻剩一個節點)不再需要輪替，直接將首尾節點設置為null。
public Node removeFirst() { if (isEmpty()) { return null; } Node tmp = first; //僅剩一個節點時 if (first == last) { first = null; last = null; return tmp; } //無論有多少個節點都會輪替到first==last first = first.next; return tmp; }6、完整程式碼
package com.jikedaquan.datastruct; public class DoubleEndLinkList { private Node first;//第一個節點 private Node last;//最後一個節點 public void addFirst(Object value) { Node newNode = new Node(value); if (isEmpty()) { //如果為空，尾節點指向此節點 last = newNode; } //更替新節點 newNode.next = first; first = newNode; } public void addLast(Object value) { Node newNode = new Node(value); if (isEmpty()) { //如果為空，首節點和尾節點指向此節點 first = newNode; last = newNode; return; } //更替尾節點 last.next = newNode; last = newNode; } public Node removeFirst() { if (isEmpty()) { return null; } Node tmp = first; //僅剩一個節點時 if (first == last) { first = null; last = null; return tmp; } //無論有多少個節點都會輪替到first==last first = first.next; return tmp; } public void display() { Node current = first;//先從首節點開始 while (current != null) { current.display();//節點不為空，則列印該節點資訊 current = current.next;//獲取當前節點的下個節點重新放入current中 System.out.println(); } } public boolean isEmpty() { return first == null; } public static void main(String[] args) { DoubleEndLinkList linkList = new DoubleEndLinkList(); linkList.addLast("e"); linkList.addFirst("a"); linkList.addFirst("b"); linkList.removeFirst(); linkList.removeFirst(); linkList.removeFirst(); linkList.display(); System.out.println("-0---"); linkList.addLast("c"); linkList.addFirst("1"); linkList.display(); System.out.println("-0---"); linkList.removeFirst(); linkList.removeFirst(); linkList.addLast(9); linkList.display(); System.out.println("-0---"); linkList.display(); } public class Node { public Object data;//存放的數據 public Node next;//指向下一個節點 public Node(Object value) { this.data = value; } //展示節點數據 public void display() { System.out.print(data + " "); } } }雙端鏈表能同時向首尾添加新元素，用雙端鏈表實現隊列也成為了可能(比用數組實現效率更高)，但是如何快速移除最後一個元素(因為不能快速的追溯之前的元素)成為了一個新難題，請看下一節 雙向鏈表！
下、方便高效的雙向鏈表
單向鏈表每個節點指向下一個節點，而雙向鏈表是指每個節點還指向了前一個節點。這樣做的好處是可以快速的移除最後一個元素。
1、保存數據的節點
節點除了指向下一個節點還要指向前一個節點
public class Node { public Object data;//存放的數據 public Node previous;//指向前一個節點 public Node next;//指向下一個節點 public Node(Object value) { this.data = value; } //展示節點數據 public void display() { System.out.print(data + " "); } }2、創建鏈表指向首元素和尾元素
public class TwoWayLinkList { private Node first; private Node last; }3、向前添加元素
考慮到鏈表為空時，首元素和尾元素均指向新元素。
public void addFirst(Object value) { Node newNode = new Node(value); if (isEmpty()) { last = newNode; first = newNode; return; } //新首元素指向舊首元素 newNode.next = first; //舊首元素的前一個指向新首元素 first.previous = newNode; //更替首元素 first = newNode; }4、向後添加元素
由於是雙向的，所以之前的引用和之後的引用都要更新
public void addLast(Object value) { Node newNode = new Node(value); if (isEmpty()) { first = newNode; last = newNode; return; } //更替尾元素 newNode.previous = last; last.next = newNode; last = newNode; }5、移除首元素
如果過已是最後一個元素，直接將首尾設置為null，其他情況進行輪替。
public Node removeFirst() { Node removeNode = first; //如果當前已是最後一個元素 if (first.next == null) { first = null; last = null; return removeNode; } //首元素指向下一個元素 first = first.next; //將新首元素指向的之前的元素設為null first.previous = null; return removeNode; }6、移除尾元素
和移除首元素類似
public Node removeLast() { Node removeNode = last; if (last.previous == null) { first = null; last = null; return null; } //尾元素指向舊尾元素之前的元素 last = last.previous; //將新尾元素的下一個元素設為null last.next = null; return removeNode; }7、根據值移除節點
從第一個元素開始遍歷，如果值不相同就一直遍歷，沒有元素匹配返回null，有元素相同時將之前的元素指向當前元素的下一個，將當前元素下一個指向前一個。
public Node remove(Object value) { if (isEmpty()){ return null; } Node current = first; while (current.data != value) { if (current.next == null) { return null; } current = current.next; } current.previous.next = current.next; current.next.previous = current.previous; return current; }8、完整程式碼
package com.jikedaquan.datastruct; public class TwoWayLinkList { private Node first; private Node last; public void addFirst(Object value) { Node newNode = new Node(value); if (isEmpty()) { last = newNode; first = newNode; return; } //新首元素指向舊首元素 newNode.next = first; //舊首元素的前一個指向新首元素 first.previous = newNode; //更替首元素 first = newNode; } public void addLast(Object value) { Node newNode = new Node(value); if (isEmpty()) { first = newNode; last = newNode; return; } //更替尾元素 newNode.previous = last; last.next = newNode; last = newNode; } public Node removeFirst() { Node removeNode = first; //如果當前已是最後一個元素 if (first.next == null) { first = null; last = null; return removeNode; } //首元素指向下一個元素 first = first.next; //將新首元素指向的之前的元素設為null first.previous = null; return removeNode; } public Node removeLast() { Node removeNode = last; if (last.previous == null) { first = null; last = null; return null; } //尾元素指向舊尾元素之前的元素 last = last.previous; //將新尾元素的下一個元素設為null last.next = null; return removeNode; } public Node remove(Object value) { if (isEmpty()){ return null; } Node current = first; while (current.data != value) { if (current.next == null) { return null; } current = current.next; } current.previous.next = current.next; current.next.previous = current.previous; return current; } public boolean isEmpty() { return first == null; } public void display() { Node current = first;//先從首節點開始 while (current != null) { current.display();//節點不為空，則列印該節點資訊 current = current.next;//獲取當前節點的下個節點重新放入current中 } System.out.println(); } public static void main(String[] args) { TwoWayLinkList linkList = new TwoWayLinkList(); linkList.addFirst("b"); linkList.addFirst("a"); linkList.display(); System.out.println("======"); while (!linkList.isEmpty()) { linkList.removeFirst(); linkList.display(); } System.out.println("======"); linkList.addLast("c"); linkList.addLast("d"); linkList.display(); System.out.println("======"); while (!linkList.isEmpty()) { linkList.removeLast(); linkList.display(); } System.out.println("======"); linkList.addFirst("e"); linkList.addLast("f"); linkList.addLast("g"); linkList.display(); System.out.println("======"); linkList.remove("f"); System.out.println("======"); linkList.display(); } public class Node { public Object data;//存放的數據 public Node previous;//指向前一個節點 public Node next;//指向下一個節點 public Node(Object value) { this.data = value; } //展示節點數據 public void display() { System.out.print(data + " "); } } } 9、總結
鏈表是節點中通過變數指向前一個節點和下一個節點實現了相連，鏈表在移除節點、首尾添加節點有著優越的性能，時間複雜度O(1)。數組在做同等操作需要O(n)，但在訪問元素上優於鏈表，空間複雜度也小於鏈表，應在不同的場景選用不同的結構。
當然這些數據結構也不需要我們去實現的，java語言中已經有對應的實現。
