当前位置： 首页 > news >正文

c# 数据结构 链表篇 有关单链表的一切

news 2025/4/17 22:36:40

        本人能力有限,本文仅作学习交流与参考,如有不足还请斧正

目录

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 的代码改的 核心在于:

  1. 尾节点的 nextNode 指向头节点（形成环）
  2. 遍历 / 搜索时通过头节点判断终止条件（避免死循环）
  3. 维护头尾指针的环结构一致性

        你要是问都循环了 还区分头尾节点有必要吗?

        有的兄弟,有的 这样头尾插都是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);}
}

 

 

 


http://www.mrgr.cn/news/97620.html

相关文章：

  • 力扣hot100_回溯(2)_python版本
  • Wideband Sparse Reconstruction for Scanning Radar论文阅读
  • 【Pandas】pandas DataFrame infer_objects
  • AnimateCC基础教学:随机抽取花名册,不能重复
  • nginx如何实现负载均衡？
  • Python 快速搭建一个小型的小行星轨道预测模型 Demo
  • 数字电子技术基础（四十）——使用Digital软件和Multisim软件模拟显示译码器
  • C++隐式转换的机制、风险与消除方法
  • Model Context Protocol（MCP）介绍
  • 机器学习 Day09 线性回归
  • 0基础 | 硬件 | LM386芯片
  • MySQL基础 [六] - 内置函数+复合查询+表的内连和外连
  • 解决MPU6050 驱动发现读取不出来姿态角度数据
  • Rust 是如何层层防错的
  • ⭐算法OJ⭐数据流的中位数【最小堆】Find Median from Data Stream
  • 《Operating System Concepts》阅读笔记：p587-p596
  • GEO, TCGA 等将被禁用？！这40个公开数据库可能要小心使用了
  • 算法刷题记录——LeetCode篇(2.7) [第161~170题](持续更新)
  • Linux下的进程管理（附加详细实验案例）
  • Android学习总结之网络篇（HTTP请求流程）