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

? ? ? ? 本人能力有限,本文僅作學習交流與參考,如有不足還請斧正

0.單鏈表好處

0.5.單鏈表分類

1.無虛擬頭節點情況

圖示:

代碼:

頭插/尾插

刪除

搜索

遍歷全部

測試代碼:

全部代碼

2.有尾指針情況

尾插

全部代碼

3.有虛擬頭節點情況

全部代碼

4.循環單鏈表

幾個特別說明的點

增加時更新環結構

刪除時刪的頭節點

非刪頭節點注意遍歷終止條件

全部代碼

0.單鏈表好處

優點	說明 / 場景
動態內存分配	節點按需創建，無需預先指定固定大小，避免數組的空間浪費或溢出（如數據量不確定時）
高效增刪操作	插入 / 刪除只需修改指針（平均?O(1)?時間復雜度），尤其適合頻繁增刪場景（如棧、隊列）
內存分散存儲	節點可存儲在非連續內存中，適應碎片化內存，利用零散空間（對比數組需連續內存）
靈活動態長度	長度可隨時增減，無需擴容 / 縮容（如動態緩沖區、鏈表隊列）
實現簡單輕量	節點結構簡單（數據 + 指針），代碼易理解，適合入門學習及快速實現基礎數據結構
適合鏈式場景	支持鏈表特有操作（反轉、合并、判環等），常用于哈希表拉鏈法、操作系統進程調度等

0.5.單鏈表分類

分類維度	類型	核心特點	典型場景 / 優勢
頭節點	無頭節點	頭指針直接指向第一個數據節點，需處理頭節點邊界條件	簡單場景，代碼稍繁瑣
	有頭節點	頭節點為虛擬節點，簡化插入 / 刪除操作	通用場景，代碼更簡潔
循環	非循環	尾節點?`next`?為?`null`，遍歷有終點	大多數基礎場景
	循環	尾節點?`next`?指向頭節點，形成環	循環遍歷、約瑟夫環等問題
輔助指針	無尾指針	尾插需遍歷鏈表（\(O(n)\)）	尾插操作較少的場景
	帶尾指針	尾插直接通過尾指針操作（\(O(1)\)）	頻繁尾插的場景

? ? ? ? 下無特殊說明皆為非循環單鏈表?

1.無虛擬頭節點情況

??????????????????????????????????請注意 無頭節點的意思是沒有虛擬頭節點

????????????????????????而下所說的headNdoe代表的是實際數據第一個節點??? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ??單鏈表 = 實際數據頭節點 + （節點 1 + 節點 2 + … + 節點 n）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 其中，每個節點的定義為：??????節點 = 數據 + 指向下一個節點的指針

圖示:

注意因為寫c#的時候使用指針需要注意下列問題:

所以指向下一個節點的指針定義為Node類也就是Node本身

代碼:

class Node { public int value;public Node nextNode;public Node(int value, Node nextNode) {this.value = value;this.nextNode = nextNode;}
}

頭插/尾插

? ? ? ? ? ?頭插的精髓:每一次插入新node的時候就把舊headNode作為nextNode,然后改變head的指向即可
????????

class LinkeList {public Node headNode;public LinkeList() {headNode = null;}//頭插: 新節點的next指向頭節點，然后將頭節點指向新節點public void AddToHead(int value) { //創建一個新節點 并把原來的頭節點放到后面去 這就是頭插法的精髓Node newNode = new Node(value, headNode);//將頭節點指向新節點headNode = newNode;}
}

? ? ? ? 尾插精髓:遍歷到最后一個節點將該節點NextNode指向新Node

????????

public void AddToTail(int value) {//創建一個新節點Node newNode = new Node(value, null);//如果鏈表為空，則直接將新節點作為頭節點if (headNode == null)headNode = newNode;else { //遍歷到最后一個節點Node currentNode = headNode;while (currentNode.nextNode != null){ currentNode = currentNode.nextNode; }currentNode.nextNode = newNode;}
}

刪除

? ? ? ? 按值刪除:單值

? ? ? ? 精髓:刪除不是讓你真刪掉,而是將Node的指針置null 這樣gc的時候就自動回收了

????????找到需要刪除的節點的上一個節點,將其nextNode = 要刪除節點的下一個Node

????????

    //按值刪除public void RemoveForValue(int value) {//如果鏈表為空，則直接返回if (headNode == null)return;//如果頭節點就是要刪除的節點，則直接將頭節點指向目標的下一個節點//相當于斷開了原來的頭節點 使其無用if (headNode.value == value) {headNode =headNode.nextNode;return;}//遍歷鏈表 Node currentNode = headNode;while (currentNode!=null&&currentNode.nextNode != null){if (currentNode.nextNode.value != value)currentNode = currentNode.nextNode;elsecurrentNode.nextNode = currentNode.nextNode.nextNode;}}

? ? ? ? 按值刪除:刪除所有匹配到的重復值

 public void RemoveForValue(int value){// 1. 處理頭節點的所有重復值（用while循環替代if）while (headNode != null && headNode.value == value){headNode = headNode.nextNode; // 連續刪除頭節點中的重復值}// 2. 遍歷刪除中間和尾節點的重復值Node currentNode = headNode;while (currentNode != null){// 檢查當前節點的下一個節點是否是目標值（避免漏判尾節點）while (currentNode.nextNode != null && currentNode.nextNode.value == value){currentNode.nextNode = currentNode.nextNode.nextNode; // 刪除下一個節點（重復值）}currentNode = currentNode.nextNode; // 移動到下一個非重復值節點}}

? ? ? ? 按節點刪除略?

? ? ? ? 這個你知道有這么回事就行了一般不會用到因為他在使用的時候需要聲明要刪除的Node 所以從用戶角度來看就不太友好不建議使用

搜索

? ???????按值遍歷

? ? ? ? ????精髓:沒有精髓遍歷按值打印即可

    public bool SerachValue(int value){if (headNode == null) { Console.WriteLine("鏈表為空 無法找到指定值"); return false; }Node currentNode = headNode;while (currentNode != null&& currentNode.nextNode != null){if (currentNode.value == value){Console.WriteLine("包含指定值" + value);return true;}else {currentNode = currentNode.nextNode;}}Console.WriteLine("鏈表內沒有指定值" + value);return false;}

遍歷全部

????????精髓:沒有精髓遍歷按值打印即可

    public void PrintAllValue() {if (headNode == null) return;Node currentNode = headNode;while (currentNode!= null){Console.WriteLine(currentNode.value);currentNode = currentNode.nextNode;}}

測試代碼:

LinkeList linke = new LinkeList();
linke.AddToHead(2);
linke.AddToHead(1);
linke.AddToTail(3);
//1 2 3
linke.RemoveForValue(2);
//1 3
Console.WriteLine(linke.SerachValue(2));//false
Console.WriteLine(linke.SerachValue(1));//truelinke.PrintAllValue(); // 1 3

全部代碼


using System.Buffers;LinkeList linke = new LinkeList();
linke.AddToHead(2);
linke.AddToHead(1);
linke.AddToTail(3);
//1 2 3
linke.RemoveForValue(2);
//1 3
Console.WriteLine(linke.SerachValue(2));//false
Console.WriteLine(linke.SerachValue(1));//truelinke.PrintAllValue(); // 1 3/// <summary>
/// 鏈表節點應該包含 值 和 指針
/// </summary>
class Node { public int value;public Node nextNode;public Node(int value, Node newNode) {this.value = value;this.nextNode = newNode;}
}
class LinkeList {public Node headNode;public LinkeList() {headNode = null;}#region Add//頭插: 新節點的next指向頭節點，然后將頭節點指向新節點public void AddToHead(int value){//創建一個新節點 并把原來的頭節點放到后面去 這就是頭插法的精髓Node newNode = new Node(value, headNode);//將頭節點指向新節點headNode = newNode;}//尾插public void AddToTail(int value){//創建一個新節點Node newNode = new Node(value, null);//如果鏈表為空，則直接將新節點作為頭節點if (headNode == null)headNode = newNode;else{//遍歷到最后一個節點Node currentNode = headNode;while (currentNode.nextNode != null){ currentNode = currentNode.nextNode; }currentNode.nextNode = newNode;}}#endregion#region Remove//按值刪除public void RemoveForValue(int value) {//如果鏈表為空，則直接返回if (headNode == null)return;//如果頭節點就是要刪除的節點，則直接將頭節點指向目標的下一個節點//相當于斷開了原來的頭節點 使其無用if (headNode.value == value) {headNode =headNode.nextNode;return;}//遍歷鏈表 Node currentNode = headNode;while (currentNode!=null&&currentNode.nextNode != null){if (currentNode.nextNode.value != value)currentNode = currentNode.nextNode;elsecurrentNode.nextNode = currentNode.nextNode.nextNode;}}#endregion#region Searchpublic bool SerachValue(int value){if (headNode == null) { Console.WriteLine("鏈表為空 無法找到指定值"); return false; }Node currentNode = headNode;while (currentNode != null&& currentNode.nextNode != null){if (currentNode.value == value){Console.WriteLine("包含指定值" + value);return true;}else {currentNode = currentNode.nextNode;}}Console.WriteLine("鏈表內沒有指定值" + value);return false;}#endregion#region 遍歷打印public void PrintAllValue() {if (headNode == null) return;Node currentNode = headNode;while (currentNode!= null){Console.WriteLine(currentNode.value);currentNode = currentNode.nextNode;}}#endregion
}

2.有尾指針情況

? ? ? ? 這個的特別之處在于尾巴輔助的話尾插不用遍歷到最后尾巴

? ? ? ? 初始化的時候需要注意一下

尾插

class LinkeList
{public Node headNode;public Node tailNode;public LinkeList(){headNode = tailNode = null;}
}

    // 尾插public void AddToTail(int value){Node newNode = new Node(value);if (headNode == null)headNode = tailNode = newNode;tailNode.nextNode = newNode;tailNode = newNode;}

? ? ? ? ?其他的就沒什么了和無虛擬頭節點的代碼和方法幾乎是一樣的

全部代碼


using System.Diagnostics;LinkeList linkeList = new LinkeList();
linkeList.AddToHead(2);
linkeList.AddToHead(1);
linkeList.AddToTail(3);
linkeList.RemoveForValue(3);
linkeList.SerachValue(2);
linkeList.SerachValue(3);
linkeList.PrintAllValue();
class Node
{public int value;public Node nextNode;public Node(int value, Node newNode = null){this.value = value;this.nextNode = newNode;}
}class LinkeList
{public Node headNode;public Node tailNode;public LinkeList(){headNode = tailNode = null;}#region Add// 頭插public void AddToHead(int value){Node newNode = new Node(value,headNode);if (headNode == null) headNode = tailNode = newNode;headNode = newNode;}// 尾插public void AddToTail(int value){Node newNode = new Node(value);if (headNode == null)headNode = tailNode = newNode;if(tailNode!= null)tailNode.nextNode = newNode;elsetailNode = newNode;}#endregion#region Remove// 按值刪除:雙向查找 刪除第一個找到的值public void RemoveForValue(int value){//頭空 直接返回if (headNode == null)return;//只有一個頭if (headNode.value == value){if (headNode.nextNode == null)headNode = tailNode = null;return;}Node currentNode = headNode;while (currentNode!=null && currentNode.nextNode != null){//如果下一個節點的值等于要刪除的值if (currentNode.nextNode.value == value) {//在尾巴上 就更新尾巴if (currentNode.nextNode == tailNode){tailNode = currentNode;}//不在尾巴上 就干掉下一個節點currentNode.nextNode = currentNode.nextNode.nextNode;}elsecurrentNode = currentNode.nextNode;}}#endregion#region Searchpublic bool SerachValue(int value){if (headNode == null)return false;Node currentNode = headNode;while (currentNode != null && currentNode.nextNode != null){//如果下一個節點的值等于要刪除的值if (currentNode.nextNode.value == value){Console.WriteLine("找到了目標值"+value);return true;}elsecurrentNode = currentNode.nextNode;}Console.WriteLine("沒找到了目標值" + value);return false; }#endregion#region 遍歷打印public void PrintAllValue(){Node currentNode = headNode;while (currentNode != null){Console.WriteLine(currentNode.value);currentNode = currentNode.nextNode;}}#endregion
}

3.有虛擬頭節點情況

????????我認為其沒有什么特別的含義只是省去了頭節點為null的判斷我截圖對比一下

左無頭右有頭

全部代碼

using System;
LinkeList linke = new LinkeList();
linke.AddToHead(2);
linke.AddToHead(1);
linke.AddToTail(3);
// 1 2 3
linke.RemoveForValue(2);
// 1 3
Console.WriteLine(linke.SerachValue(2));// false
Console.WriteLine(linke.SerachValue(1));// truelinke.PrintAllValue(); // 1 3
/// <summary>
/// 鏈表節點應該包含 值 和 指針
/// </summary>
class Node
{public int value;public Node nextNode;public Node(int value, Node newNode = null){this.value = value;this.nextNode = newNode;}
}class LinkeList
{// 虛擬頭節點private Node dummyHead;public LinkeList(){// 初始化虛擬頭節點dummyHead = new Node(0);}#region Add// 頭插: 新節點的next指向虛擬頭節點的下一個節點，然后將虛擬頭節點的next指向新節點public void AddToHead(int value){Node newNode = new Node(value, dummyHead.nextNode);dummyHead.nextNode = newNode;}// 尾插public void AddToTail(int value){Node newNode = new Node(value);Node currentNode = dummyHead;while (currentNode.nextNode != null){currentNode = currentNode.nextNode;}currentNode.nextNode = newNode;}#endregion#region Remove// 按值刪除public void RemoveForValue(int value){Node currentNode = dummyHead;while (currentNode != null && currentNode.nextNode != null){if (currentNode.nextNode.value == value){currentNode.nextNode = currentNode.nextNode.nextNode;}else{currentNode = currentNode.nextNode;}}}#endregion#region Searchpublic bool SerachValue(int value){Node currentNode = dummyHead.nextNode;while (currentNode != null){if (currentNode.value == value){Console.WriteLine("包含指定值" + value);return true;}currentNode = currentNode.nextNode;}Console.WriteLine("鏈表內沒有指定值" + value);return false;}#endregion#region 遍歷打印public void PrintAllValue(){Node currentNode = dummyHead.nextNode;while (currentNode != null){Console.WriteLine(currentNode.value);currentNode = currentNode.nextNode;}}#endregion
}

4.循環單鏈表

? ? ? ? 我直接用情況2?的代碼改的核心在于:

尾節點的?nextNode?指向頭節點（形成環）
遍歷 / 搜索時通過頭節點判斷終止條件（避免死循環）
維護頭尾指針的環結構一致性

? ? ? ? 你要是問都循環了還區分頭尾節點有必要嗎?

? ? ? ? 有的兄弟,有的這樣頭尾插都是O1

幾個特別說明的點

增加時更新環結構

   // 尾插法：新節點的next指向頭節點，原尾節點的next指向新節點，更新尾節點public void AddToTail(int value){Node newNode = new Node(value, headNode); // 新節點的next指向頭節點（形成環）if (tailNode == null){// 空鏈表：頭尾節點指向新節點，自環headNode = tailNode = newNode;newNode.nextNode = newNode;}else{tailNode.nextNode = newNode; // 原尾節點連接新節點tailNode = newNode; // 尾節點更新為新節點}}

刪除時刪的頭節點

 public void RemoveForValue(int value){if (headNode == null) return;// 情況1：刪除頭節點if (headNode.value == value){if (headNode == tailNode) // 只有一個節點{headNode = tailNode = null; // 環斷開}else // 多個節點，頭節點后移，尾節點的next指向新頭節點{headNode = headNode.nextNode;tailNode.nextNode = headNode; // 尾節點保持環結構}return;}.................}

非刪頭節點注意遍歷終止條件

 while (previous.nextNode != headNode){if (previous.nextNode.value == value){Node target = previous.nextNode;if (target == tailNode){tailNode = previous;tailNode.nextNode = headNode;}else{previous.nextNode = target.nextNode;}}else{previous = previous.nextNode;}}

全部代碼

class Node
{public int value;public Node nextNode;public Node(int value, Node nextNode = null){this.value = value;this.nextNode = nextNode;}
}class CircularLinkedList
{public Node headNode;public Node tailNode;public CircularLinkedList(){headNode = tailNode = null;}// 頭插法public void AddToHead(int value){Node newNode = new Node(value, headNode);if (headNode == null){headNode = tailNode = newNode;newNode.nextNode = newNode;}else{tailNode.nextNode = newNode;headNode = newNode;}}// 按值刪除節點public void RemoveForValue(int value){if (headNode == null) return;// 處理頭節點是要刪除的值的情況while (headNode != null && headNode.value == value){if (headNode == tailNode){headNode = tailNode = null;return;}headNode = headNode.nextNode;tailNode.nextNode = headNode;}Node previous = headNode;while (previous.nextNode != headNode){if (previous.nextNode.value == value){Node target = previous.nextNode;if (target == tailNode){tailNode = previous;tailNode.nextNode = headNode;}else{previous.nextNode = target.nextNode;}}else{previous = previous.nextNode;}}}// 遍歷打印鏈表public void PrintAllValue(){if (headNode == null) return;Node current = headNode;do{Console.WriteLine(current.value);current = current.nextNode;} while (current != headNode);}
}