數據結構與演算法系列——鏈表詳解
上次我們簡單的對比了一下數組和鏈表的區別和各自的優缺點，今天我們來詳細看一下鏈表這個結構。
鏈表的結構五花八門，我們幾天主要看一下三種最常用的鏈表結構：單鏈表、雙向鏈表和循環列表。- 單鏈表
我們首先來看一下最簡單、最常用的單鏈表。前邊我們已經知道鏈表是通過指針將一些分散的內存塊連接到一起。其中，我們把每個內存塊叫做鏈表的一個結點。為了將每個結點連接到一起，每個結點不僅存儲數據，而且還需要記錄下一個結點的地址。我們把這個記錄下一個結點的指針稱為後繼指針next。我們通過下邊示意圖來更形象的瞭解一下。
從圖中我們可以看到，單鏈表是單方向順序的一個線性表。其中有兩個結點比較特殊，分別是第一個和最後一個結點。我們通常把第一個結點叫做頭結點，最後一個結點叫做尾結點，頭結點用來記錄鏈表的基地址，這樣我們就可以遍歷得到整個結點，尾結點是最後一個結點，它的指針指向一個空地址NULL，這樣我們通過判斷後繼指針next是不是NULL來確定某個結點是不是尾結點。
前邊我們在數組和鏈表中已經詳細介紹了鏈表的插入和刪除，在這裡我們不做過多的描述，而是通過示意圖的方式更清楚的瞭解。針對鏈表的插入和刪除操作，我們只需要考慮相鄰結點的指針改變，所以對應的時間複雜度為O(1)。
- 雙向鏈表
單鏈表只有一個指針，每個結點都只有一個後繼指針next指向下一個結點的地址。而雙向鏈表，顧名思義，它有兩個方向，所以每個結點不僅有一個指向下一個結點的後繼指針next，還有一個指向前一個結點的前驅結點prev。同樣我們通過示意圖來看一下。
從圖中我們看到，與單鏈表相比，雙向鏈表的每個結點還需要存儲指向前一個結點的指針，所以，同樣多的數據，雙向鏈表比單鏈表需要更多的存儲空間。兩個指針雖然比較浪費空間，但是雙向鏈表可以雙向遍歷，靈活性更高。
雙向鏈表在刪除、插入結點上更加高效，前邊我們講過單鏈表的刪除和插入操作的時間複雜度為O(1)，但是雙向鏈表的為什麼會更高效呢，因為單鏈表的分析只是理論上得到的，但是實際情況中是不準確的，是需要前提條件的。下面我們分析一下實際情況中的操作。我們先來看插入操作，實際情況中的插入操作可以分為這兩種情況：- 在值等於某個指定值的結點前或者後插入結點
- 在給定指針後邊插入結點
對於第一種情況，不管是單鏈表還是雙向鏈表，都需要從頭一個一個遍歷直到找到特定值的結點，然後執行插入操作雖然插入的時間複雜度為O(1)，但是遍歷的時間複雜度為O(n)，所以在值等於某個指定值的結點前或者後插入結點的時間複雜度為O(n)。
對於第二種情況，我們通過給定指針可以直到插入結點的位置，但是我們需要直到給定指針的前驅結點，如果是單鏈表，我們依然需要通過從頭開始遍歷找到前驅結點，需要的時間複雜度為O(n)，但是對於雙向鏈表就簡單多了，我們只需要通過前驅結點的指針就能得到前驅結點，需要的時間複雜度為O(1)。同理，參照我們上邊插入操作的分析，刪除結點雙向鏈表同樣比單鏈表靈活得多。還有就是在有序鏈表中，雙向鏈表的按值查詢也比單鏈表也快一些，因為我們可以記錄上次查找的位置x，然後通過比較查詢值x的大小來決定向前還是向後，可以比單鏈表節省時間。通過上邊單鏈表和雙向鏈表的比較，我們有學習了靈位一個非常重要的知識點，那就是用空間換時間的思想，當內存空間充足時，如果我們對執行效率有更高的要求，可以用犧牲內存而換取效率的辦法，也就是選擇空間複雜度相對比較高，但是時間複雜度低的演算法或者數據結構（實際應用中，緩存就是利用空間換時間的思想）。相反，如果內存比較緊張，我們就可以用時間換空間的演算法或數據結構。- 循環鏈表
循環鏈表一種特殊的單鏈表，與單鏈表唯一的區別就是，循環鏈表的最後一個結點的指針指向頭結點而不是指向空地址。如下示意圖所示。
和單鏈表相比，循環列表的優點就是從鏈尾到鏈頭比較方便。比如需要處理的數據具有環形結構特點時，用循環列表就非常合適。雖然單鏈表也可以實現，但是循環鏈表的代碼要簡潔的多。
鏈表的應用
我們已經學習了三種簡單且最常見的鏈表，那麼鏈表在實際的應用中是怎麼用的呢？一個經典的鏈表使用場景就是LRU緩存淘汰法。
緩存的大小有限，但緩存的空間被用滿的時候，我們該把哪些數據清除出去呢？LRU緩存淘汰法就是其中的一種策略，把最近最少用的數據清除出去。
那用鏈表怎麼實現這個演算法呢，下邊我們來看一下基於單鏈表的Java實現。package linked.singlelist;
import java.util.Scanner;
/**
* 基於單鏈表LRU演算法（java）
*
*/
public class LRUBaseLinkedList<T> {
/**
* 頭結點
*/
private SNode<T> headNode;
/**
* 鏈表長度
*/
private Integer length;
/**
* 鏈表容量
*/
private Integer capacity;
public LRUBaseLinkedList(Integer capacity) {
this.headNode = new SNode<>();
this.capacity = capacity;
this.length = 0;
}
public void add(T data) {
SNode preNode = findPreNode(data);
// 鏈表中存在，刪除原數據，再插入到鏈表的頭部
if (preNode != null) {
deleteElemOptim(preNode);
intsertElemAtBegin(data);
} else {
if (length >= this.capacity) {
//刪除尾結點
deleteElemAtEnd();
}
intsertElemAtBegin(data);
}
}
/**
* 刪除preNode結點下一個元素
*
* @param preNode
*/
private void deleteElemOptim(SNode preNode) {
SNode temp = preNode.getNext();
preNode.setNext(temp.getNext());
temp = null;
length--;
}
/**
* 鏈表頭部插入結點
*
* @param data
*/
private void intsertElemAtBegin(T data) {
SNode next = headNode.getNext();
headNode.setNext(new SNode(data, next));
length++;
}
/**
* 獲取查找到元素的前一個結點
*
* @param data
* @return
*/
private SNode findPreNode(T data) {
SNode node = headNode;
while (node.getNext() != null) {
if (data.equals(node.getNext().getElement())) {
return node;
}
node = node.getNext();
}
return null;
}
/**
* 刪除尾結點
*/
private void deleteElemAtEnd() {
SNode ptr = headNode;
// 空鏈表直接返回
if (ptr.getNext() == null) {
return;
}
// 倒數第二個結點
while (ptr.getNext().getNext() != null) {
ptr = ptr.getNext();
}
SNode tmp = ptr.getNext();
ptr.setNext(null);
tmp = null;
length--;
}
private void printAll() {
SNode node = headNode.getNext();
while (node != null) {
System.out.print(node.getElement() + ",");
node = node.getNext();
}
System.out.println();
}
public class SNode<T> {
private T element;
private SNode next;
public SNode(T element) {
this.element = element;
}
public SNode(T element, SNode next) {
this.element = element;
this.next = next;
}
public SNode() {
this.next = null;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public SNode getNext() {
return next;
}
public void setNext(SNode next) {
this.next = next;
}
}
public static void main(String[] args) {
LRUBaseLinkedList list = new LRUBaseLinkedList();
Scanner sc = new Scanner(System.in);
while (true) {
list.add(sc.nextInt());
list.printAll();
}
}
}
歡迎關注公眾號：「努力給自己看」
推薦閱讀：
