c# 數據結構 鏈表篇 有關雙向鏈表的一切

? ? ? ? 本人能力有限,如有不足還請斧正

目錄

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指向頭節點(非循環時頭節點prevnull
頭節點(H) <-> 數據節點1 <-> 數據節點2 <-> ... <-> 尾節點(T)〔T.prev=H,H.next=數據節點1〕頻繁進行插入 / 刪除操作的場景(如鏈表初始化、邊界操作更便捷)
(本文演示一)不帶頭節點雙向鏈表- 直接以第一個數據節點作為頭節點,頭節點prevnull
- 尾節點nextnull
數據節點1 <-> 數據節點2 <-> ... <-> 尾節點(T)〔T.next=null,數據節點1.prev=null〕內存資源敏感場景(節省頭節點空間)
是否循環非循環雙向鏈表- 頭節點prevnull,尾節點nextnull
- 鏈表頭尾不相連
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
}

?

?

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/75938.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/75938.shtml
英文地址,請注明出處:http://en.pswp.cn/web/75938.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Numba 從零基礎到實戰:解鎖 Python 性能新境界

Numba 從零基礎到實戰&#xff1a;解鎖 Python 性能新境界 一、引言 在 Python 的世界里&#xff0c;性能一直是一個備受關注的話題。Python 以其簡潔易讀的語法和豐富的庫生態&#xff0c;深受開發者喜愛&#xff0c;但在處理一些計算密集型任務時&#xff0c;其執行速度往往…

單位門戶網站被攻擊后的安全防護策略

政府網站安全現狀與挑戰 近年來&#xff0c;隨著數字化進程的加速&#xff0c;政府門戶網站已成為政務公開和服務公眾的重要窗口。然而&#xff0c;網絡安全形勢卻日益嚴峻。國家互聯網應急中心的數據顯示&#xff0c;政府網站已成為黑客攻擊的重點目標&#xff0c;被篡改和被…

Spring Boot 項目三種打印日志的方法詳解。Logger,log,logger 解讀。

目錄 一. 打印日志的常見三種方法&#xff1f; 1.1 手動創建 Logger 對象&#xff08;基于SLF4J API&#xff09; 1.2 使用 Lombok 插件的 Slf4j 注解 1.3 使用 Spring 的 Log 接口&#xff08;使用頻率較低&#xff09; 二. 常見的 Logger&#xff0c;logger&#xff0c;…

NI的LABVIEW工具安裝及卸載步驟說明

一.介紹 最近接到個轉交的項目&#xff0c;項目主要作為上位機工具開發&#xff0c;在對接下位機時&#xff0c;有用到NI的labview工具。labview軟件是由美國國家儀器&#xff08;NI&#xff09;公司研制開發的一種程序開發環境&#xff0c;主要用于汽車測試、數據采集、芯片測…

cmd 終端輸出亂碼問題 |Visual Studio 控制臺輸出中文亂碼解決

在網上下載&#xff0c;或者移植別人的代碼到自己的電腦&#xff0c;使用VS運行后&#xff0c;控制臺輸出中文可能出現亂碼。這是因為源代碼的編碼格式和控制臺的編碼格式不一致。 文章目錄 查看源代碼文件編碼格式查看輸出控制臺編碼格式修改編碼格式修改終端代碼頁 補充總結 …

A009-基于pytest的網易云自動化測試

題 目 :基于pytest的網易云自動化測試 主要內容 綜合應用所學的軟件測試理論和方法,實現網易云的功能自動化測試。 (1)自動化測試介紹; (2)自動化功能測試框架介紹; (3)設計功能測試用例 (4)書寫自動化測試腳本; (5)測試評價與結論。 任務要求 (1)能…

LVGL Video控件和Radiobtn控件詳解

LVGL Video控件和Radiobtn控件詳解 一、 Video控件詳解1. 概述2. 創建和初始化3. 基本屬性設置4. 視頻控制5. 回調函數6. 高級功能7. 注意事項 二、Radiobtn控件詳解1. 概述2. 創建和初始化3. 屬性設置4. 狀態控制5. 組管理6. 事件處理7. 樣式設置8. 注意事項 三、效果展示四、…

AbortController:讓異步操作隨時說停就停

AbortController&#xff1a;讓異步操作隨時說停就停 一、什么是 AbortController&#xff1f; AbortController 是 JavaScript 在瀏覽器和部分 Node.js 環境中提供的全局類&#xff0c;用來中止正在進行或待完成的異步操作&#xff08;如 fetch() 請求、事件監聽、可寫流、數…

機器學習 從入門到精通 day_04

1. 決策樹-分類 1.1 概念 1. 決策節點 通過條件判斷而進行分支選擇的節點。如&#xff1a;將某個樣本中的屬性值(特征值)與決策節點上的值進行比較&#xff0c;從而判斷它的流向。 2. 葉子節點 沒有子節點的節點&#xff0c;表示最終的決策結果。 3. 決策樹的…

C++ Primer (第五版)-第十三章 拷貝控制

文章目錄 概述13.1拷貝、賦值與銷毀合成拷貝構造函數拷貝初始化參數和返回值拷貝初始化的限制編譯器可以繞過拷貝構造函數拷貝運算符析構函數三/五原則使用default阻止拷貝合成的拷貝控制成員可能是刪除的 private拷貝控制拷貝控制和資源管理行為像值的類類值拷貝賦值運算符定義…

Vue el-from的el-form-item v-for循環表單如何校驗rules(一)

實際業務需求場景&#xff1a; 新增或編輯頁面&#xff08;基礎信息表單&#xff0c;一個數據列表的表單&#xff09;&#xff0c;數據列表里面的表單數是動態添加的。數據可新增、可刪除&#xff0c;在表單保存前&#xff0c;常常需要做表單必填項的校驗&#xff0c;校驗通過以…

測試100問:http和https的區別是什么?

哈嘍&#xff0c;大家好&#xff0c;我是十二&#xff0c;今天給大家分享的問題是&#xff1a;http和https的區別是什么&#xff1f; 首先我們要知道 HTTP 協議傳播的數據都是未加密的&#xff0c;也就是明文的&#xff0c;因此呢使用 http協議傳輸一些隱私信息也就非常不安全&…

YOLOv3超詳細解讀(三):源碼解析:數據處理模塊

一、概述 YOLOv3&#xff08;You Only Look Once v3&#xff09;是一種高效的目標檢測算法&#xff0c;其數據處理模塊是訓練和推理流程的核心部分。本文將深入分析Ultralytics團隊基于PyTorch實現的YOLOv3源碼中的數據處理模塊&#xff0c;重點探討數據加載、預處理和數據增強…

每日算法(雙指針算法)(Day 1)

雙指針算法 1.算法題目&#xff08;移動零&#xff09;2.講解算法原理3.編寫代碼 1.算法題目&#xff08;移動零&#xff09; 2.講解算法原理 數組劃分&#xff0c;數組分塊&#xff08;快排里面最核心的一步&#xff09;只需把0改為tmp 雙指針算法&#xff1a;利用數組下標來…

2025藍橋杯python A組省賽 題解

真捐款去了&#xff0c;好長時間沒練了&#xff0c;感覺腦子和手都不轉悠了。 B F BF BF 賽時都寫假了&#xff0c; G G G 也只寫了爆搜。 題解其實隊友都寫好了&#xff0c;我就粘一下自己的代碼&#xff0c;稍微提點個人的理解水一篇題解 隊友題解 2025藍橋杯C A組省賽 題…

測試基礎筆記第四天(html)

提示&#xff1a;文章寫完后&#xff0c;目錄可以自動生成&#xff0c;如何生成可參考右邊的幫助文檔 文章目錄 html介紹1. 介紹2.骨架標簽3.常用標簽標題標簽段落標簽超鏈接標簽圖片標簽換行和空格標簽布局標簽input標簽&#xff08;變形金剛&#xff09;form標簽列表標簽 htm…

10 穴 汽車連接器的15個設計特點

汽車行業嚴重依賴卓越的電氣系統來確保功能和可靠性。這些系統的關鍵組件是 10 腔連接器&#xff0c;它為布線和信號傳輸提供解決方案。制造商和工程師必須仔細評估這些連接器的設計特性&#xff0c;以優化性能和安全性。 本博客研究了汽車 10 腔連接器的 15 個設計特征&#…

Summary

一、數據結構 1.1 哈希 主要是HashMap和HashSet&#xff1b;其中HashSet底層是一個HashMap屬性。 // 獲取HashMap元素,HashSet均不支持 map.keySet (); // Set<k> map.values (; // Collection<V> map.entrySet();//Set<Map.Entry<K,V>> for (Map.E…

【Leetcode-Hot100】最小覆蓋子串

題目 解答 想到使用雙指針哈希表來實現&#xff0c;雙指針的left和right控制實現可滿足字符串。 class Solution(object):def minWindow(self, s, t):""":type s: str:type t: str:rtype: str"""len_s, len_t len(s), len(t)hash_map {}for…

Flutter 播放利器:`media_kit` 的詳細介紹與使用指南

在 Flutter 項目中實現音視頻播放&#xff0c;開發者過去主要依賴如 video_player、just_audio 等第三方庫&#xff0c;但這些庫或多或少存在一些局限性&#xff0c;比如平臺兼容性差、定制能力不足、播放格式有限等問題。 而 media_kit 是近年崛起的一款全平臺音視頻播放解決…