? ? ? ? 本人能力有限,如有不足還請斧正
目錄
0.雙向鏈表的好處
1.雙向鏈表的分類
2.不帶頭節點的標準雙向鏈表
節點類:有頭有尾
鏈表類:也可以有頭有尾 也可以只有頭
增
頭插
尾插
刪
查
改
遍歷
全部代碼
3.循環雙向鏈表
節點類
鏈表類
增
頭插
尾插
刪
查
遍歷
全部代碼
?
0.雙向鏈表的好處
優勢維度 | 具體好處 | 說明 / 示例 | 對比單向鏈表的核心差異 |
---|---|---|---|
雙向遍歷能力 | 支持正向(next)和反向(prev)遍歷,可靈活選擇遍歷方向 | - 可從任意節點出發,向前后兩個方向遍歷鏈表 - 例如:實現瀏覽器歷史記錄的 “前進 / 后退” 功能,直接通過 prev/next 指針操作 | 單向鏈表僅能單向遍歷,反向操作需從頭重新遍歷 |
插入 / 刪除效率 | 已知當前節點時,插入 / 刪除操作時間復雜度為 O (1),無需提前獲取前驅節點 | - 插入時,通過當前節點的 prev 指針直接找到前驅,更新前后節點的指針即可 - 刪除時,直接通過 prev 和 next 指針連接前后節點,無需遍歷查找前驅 | 單向鏈表刪除 / 插入節點時,若無前驅節點引用,需 O (n) 時間遍歷查找前驅 |
定位便利性 | 可直接通過節點的 prev 指針反向定位前驅節點,無需額外存儲或遍歷 | - 在鏈表中間節點操作時,無需維護額外變量記錄前驅 - 例如:實現雙向隊列(雙端隊列)的頭尾插入 / 刪除操作,可直接通過指針快速定位 | 單向鏈表需從頭遍歷才能找到前驅節點,定位效率低 |
邊界操作簡化 | 處理頭節點和尾節點的插入 / 刪除時更簡單,無需特殊處理頭指針(若帶頭節點) | - 帶頭節點的雙向鏈表中,頭節點和尾節點的操作與中間節點邏輯一致 - 例如:刪除頭節點時,直接通過頭節點的 next 找到第一個數據節點,更新其 prev 為 null(非循環情況) | 單向鏈表刪除頭節點需單獨處理頭指針,邊界條件易出錯 |
應用場景適配 | 適合需要雙向操作或頻繁前后移動的場景 | - 操作系統進程調度隊列(需快速調整進程優先級,前后移動節點) - LRU 緩存淘汰算法(需快速刪除最近最少使用節點并插入到頭部) | 單向鏈表無法高效支持反向操作,需額外數據結構輔助 |
數據一致性 | 指針操作更安全,減少空指針異常風險(尤其在循環雙向鏈表中) | - 循環雙向鏈表中,頭節點 prev 指向尾節點,尾節點 next 指向頭節點,避免首尾指針為 null 的情況 - 適合對穩定性要求高的場景(如內核數據結構) | 單向鏈表尾節點 next 為 null,反向遍歷時易觸發空指針錯誤 |
算法靈活性 | 支持更復雜的算法邏輯,如雙向搜索、回退操作 | - 在雙向鏈表中實現 “雙指針搜索”(如從頭尾同時向中間遍歷) - 支持撤銷操作(如文本編輯器的撤銷 / 重做,通過雙向指針回退歷史版本) | 單向鏈表需額外棧結構記錄歷史節點,增加空間復雜度 |
1.雙向鏈表的分類
分類標準 | 類型 | 核心特點 | 示意圖(簡化) | 典型應用場景 |
---|---|---|---|---|
是否帶頭節點 | 帶頭節點雙向鏈表 | - 頭部有一個固定的頭節點(不存儲數據),頭節點的next 指向第一個數據節點- 尾節點的 prev 指向頭節點(非循環時頭節點prev 為null ) | 頭節點(H) <-> 數據節點1 <-> 數據節點2 <-> ... <-> 尾節點(T)〔T.prev=H,H.next=數據節點1〕 | 頻繁進行插入 / 刪除操作的場景(如鏈表初始化、邊界操作更便捷) |
(本文演示一) | 不帶頭節點雙向鏈表 | - 直接以第一個數據節點作為頭節點,頭節點prev 為null - 尾節點 next 為null | 數據節點1 <-> 數據節點2 <-> ... <-> 尾節點(T)〔T.next=null,數據節點1.prev=null〕 | 內存資源敏感場景(節省頭節點空間) |
是否循環 | 非循環雙向鏈表 | - 頭節點prev 為null ,尾節點next 為null - 鏈表頭尾不相連 | null <-> 頭節點 <-> ... <-> 尾節點 <-> null | 單向遍歷需求不高,但需雙向操作的場景(如文件系統目錄結構) |
? | 循環雙向鏈表 | - 頭節點prev 指向尾節點,尾節點next 指向頭節點- 形成一個環形結構,可從任意節點出發遍歷整個鏈表 | 頭節點(H) <-> ... <-> 尾節點(T) <-> H | 循環數據處理(如循環緩沖區、操作系統進程調度隊列) |
節點結構擴展 | 標準雙向鏈表(和第一行重復) | - 每個節點包含prev (前驅指針)和next (后繼指針)- 存儲單一數據元素 | 節點: prev <-> data <-> next | 通用雙向操作場景(如瀏覽器歷史記錄的前進 / 后退) |
(本文不做演示) | 雙向鏈表帶附加屬性 | - 節點額外包含其他屬性(如優先級、時間戳等) - 結構上仍保持雙向指針 | 節點: prev <-> data <-> next <-> extra_attr | 復雜數據管理(如任務調度鏈表、帶權重的鏈表) |
2.不帶頭節點的標準雙向鏈表
圖解模型
每一個節點類Node 都有三個元素:前項 數據 后項
注意因為c#不用指針 所以所謂Prev和Next指向的都是節點類Node?
節點類:有頭有尾
public class Node {public int data;public Node prev;public Node next;public Node(int data, Node prev = null, Node next=null) { this.data = data;this.prev = prev;this.next = next;}
}
鏈表類:也可以有頭有尾 也可以只有頭
????????這里你可能會有一些疑問 怎么又出現了一個HeadNode和一個TailNode呢?
????????這是因為鏈表類需要這兩個去抽象的節點以方便管理
public class DoublyLinkedList {public Node headNode;public Node tailNode;public DoublyLinkedList() {headNode = tailNode = null;}
增
頭插
乾坤大挪移
public void HeadAdd(int data) {//如果鏈表為空if (headNode == null) { headNode = tailNode = new Node(data);}//雙向鏈表的特殊性: 修改頭節點時,需要把新節點的前項 后項 都掛上Node newNode = new Node(data, null, headNode);headNode.prev = newNode;//改變鏈表頭headNode = newNode;}
尾插
public void TailAdd(int data) {//如果尾巴為空 說明頭也沒有 所以下面判斷頭尾都可以if (headNode == null){ //if (tailNode ==null)headNode = tailNode = new Node(data);}//雙向鏈表的特殊性: 修改尾節點時,需要把新節點的前項 后項 都掛上Node newNode = new Node(data, tailNode, null);tailNode.next = newNode;//改變鏈表尾tailNode =newNode ;}
刪
無需遍歷找前驅節點 找到Target直接調換其前后指針指向即可
public void DeleteValue(int data){if (headNode == null) return;Node current = headNode;while (current != null){if (current.data == data){//如果匹配到了則可能出現以下情況://1 刪除的是頭節點if (current.prev == null)headNode = current.next;//2.刪除的是尾巴if (current.next == null)tailNode = current.prev;//3.刪除的是中間節點current.prev.next = current.next;current.next.prev = current.prev;return;}current = current.next;}}
查
查詢找到的第一個目標
public bool SearchValue(int data){if (headNode == null) return true;Node current = headNode;while (current != null){if (current.data == data){Console.WriteLine("找到了目標"+data);return true;}current = current.next;}Console.WriteLine("沒有目標" + data);return false;}
改
????????關于改就是查的子集 只需要加一兩行代碼即可 所以不做演示
遍歷
可以雙向遍歷鏈表哦
#region 遍歷打印/// <summary>/// 正向打印鏈表:按順序輸出鏈表中每個節點的數據/// </summary>public void PrintListForward(){// 從鏈表頭節點開始遍歷Node current = headNode;while (current != null){// 輸出當前節點的數據Console.Write(current.data + " ");// 移動到下一個節點current = current.next;}Console.WriteLine();}/// <summary>/// 反向打印鏈表:按逆序輸出鏈表中每個節點的數據/// </summary>public void PrintListBackward(){// 從鏈表尾節點開始遍歷Node current = tailNode;while (current != null){// 輸出當前節點的數據Console.Write(current.data + " ");// 移動到前一個節點current = current.prev;}Console.WriteLine();}
全部代碼
using System;public class Node
{public int data;public Node prev;public Node next;public Node(int data, Node prev = null, Node next = null){this.data = data;this.prev = prev;this.next = next;}
}public class DoublyLinkedList
{public Node headNode;public Node tailNode;public DoublyLinkedList(){headNode = tailNode = null;}#region 增/// <summary>/// 頭插法/// </summary>public void HeadAdd(int data){//如果鏈表為空if (headNode == null){headNode = tailNode = new Node(data);}else{//雙向鏈表的特殊性: 修改頭節點時,需要把新節點的前項 后項 都掛上Node newNode = new Node(data, null, headNode);headNode.prev = newNode;//改變鏈表頭headNode = newNode;}}public void TailAdd(int data){//如果尾巴為空 說明頭也沒有 所以下面判斷頭尾都可以if (headNode == null){//if (tailNode ==null)headNode = tailNode = new Node(data);}else{//雙向鏈表的特殊性: 修改尾節點時,需要把新節點的前項 后項 都掛上Node newNode = new Node(data, tailNode, null);tailNode.next = newNode;//改變鏈表尾tailNode = newNode;}}#endregion#region 刪public void DeleteValue(int data){if (headNode == null) return;Node current = headNode;while (current != null){if (current.data == data){//如果匹配到了則可能出現以下情況://1 刪除的是頭節點if (current.prev == null){headNode = current.next;if (headNode != null){headNode.prev = null;}else{tailNode = null;}}//2.刪除的是尾巴else if (current.next == null){tailNode = current.prev;tailNode.next = null;}//3.刪除的是中間節點else{current.prev.next = current.next;current.next.prev = current.prev;}return;}current = current.next;}}#endregion#region 查詢public bool SearchValue(int data){if (headNode == null) return false;Node current = headNode;while (current != null){if (current.data == data){Console.WriteLine("找到了目標" + data);return true;}current = current.next;}Console.WriteLine("沒有目標" + data);return false;}#endregion#region 遍歷打印/// <summary>/// 正向打印鏈表:按順序輸出鏈表中每個節點的數據/// </summary>public void PrintListForward(){// 從鏈表頭節點開始遍歷Node current = headNode;while (current != null){// 輸出當前節點的數據Console.Write(current.data + " ");// 移動到下一個節點current = current.next;}Console.WriteLine();}/// <summary>/// 反向打印鏈表:按逆序輸出鏈表中每個節點的數據/// </summary>public void PrintListBackward(){// 從鏈表尾節點開始遍歷Node current = tailNode;while (current != null){// 輸出當前節點的數據Console.Write(current.data + " ");// 移動到前一個節點current = current.prev;}Console.WriteLine();}#endregion
}
3.循環雙向鏈表
????????循環鏈表就是將頭節點的前項和尾節點的后項連到同一個節點
? ? ? ? 簡稱:貂蟬在一起了 噗噗
headNode.prev = newNode;tailNode.next = newNode;
節點類
并沒有什么區別
public class Node
{public int data;public Node prev;public Node next;public Node(int data){this.data = data;this.prev = null;this.next = null;}
}
鏈表類
也沒有什么區別
public class DoublyCircularLinkedList
{public Node headNode;public Node tailNode;public DoublyCircularLinkedList(){headNode = tailNode = null;}
增
頭插
只是將頭節點的前項 和 尾節點的后項 連接在了一起
/// <summary>/// 頭插法/// </summary>public void HeadAdd(int data){Node newNode = new Node(data);if (headNode == null){headNode = tailNode = newNode;newNode.next = newNode;newNode.prev = newNode;}else{newNode.next = headNode;newNode.prev = tailNode;headNode.prev = newNode;tailNode.next = newNode;headNode = newNode;}}
尾插
public void TailAdd(int data){Node newNode = new Node(data);if (tailNode == null){headNode = tailNode = newNode;newNode.next = newNode;newNode.prev = newNode;}else{newNode.next = headNode;newNode.prev = tailNode;tailNode.next = newNode;headNode.prev = newNode;tailNode = newNode;}}
刪
public void DeleteValue(int data){if (headNode == null) return;Node current = headNode;do{if (current.data == data){if (current.next == current){headNode = tailNode = null;}else{if (current == headNode){headNode = current.next;}if (current == tailNode){tailNode = current.prev;}current.prev.next = current.next;current.next.prev = current.prev;}return;}current = current.next;} while (current != headNode);}
查
public bool SearchValue(int data){if (headNode == null) return false;Node current = headNode;do{if (current.data == data){Console.WriteLine("找到了目標" + data);return true;}current = current.next;} while (current != headNode);Console.WriteLine("沒有目標" + data);return false;}
遍歷
#region 遍歷打印/// <summary>/// 打印鏈表:按順序輸出鏈表中每個節點的數據/// </summary>public void PrintList(){if (headNode == null) return;Node current = headNode;do{Console.Write(current.data + " ");current = current.next;} while (current != headNode);Console.WriteLine();}#endregion
全部代碼
public class Node
{public int data;public Node prev;public Node next;public Node(int data){this.data = data;this.prev = null;this.next = null;}
}public class DoublyCircularLinkedList
{public Node headNode;public Node tailNode;public DoublyCircularLinkedList(){headNode = tailNode = null;}#region 增/// <summary>/// 頭插法/// </summary>public void HeadAdd(int data){Node newNode = new Node(data);if (headNode == null){headNode = tailNode = newNode;newNode.next = newNode;newNode.prev = newNode;}else{newNode.next = headNode;newNode.prev = tailNode;headNode.prev = newNode;tailNode.next = newNode;headNode = newNode;}}public void TailAdd(int data){Node newNode = new Node(data);if (tailNode == null){headNode = tailNode = newNode;newNode.next = newNode;newNode.prev = newNode;}else{newNode.next = headNode;newNode.prev = tailNode;tailNode.next = newNode;headNode.prev = newNode;tailNode = newNode;}}#endregion#region 刪public void DeleteValue(int data){if (headNode == null) return;Node current = headNode;do{if (current.data == data){if (current.next == current){headNode = tailNode = null;}else{if (current == headNode){headNode = current.next;}if (current == tailNode){tailNode = current.prev;}current.prev.next = current.next;current.next.prev = current.prev;}return;}current = current.next;} while (current != headNode);}#endregion#region 查詢public bool SearchValue(int data){if (headNode == null) return false;Node current = headNode;do{if (current.data == data){Console.WriteLine("找到了目標" + data);return true;}current = current.next;} while (current != headNode);Console.WriteLine("沒有目標" + data);return false;}#endregion#region 遍歷打印/// <summary>/// 打印鏈表:按順序輸出鏈表中每個節點的數據/// </summary>public void PrintList(){if (headNode == null) return;Node current = headNode;do{Console.Write(current.data + " ");current = current.next;} while (current != headNode);Console.WriteLine();}#endregion
}
?
?