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

发布于：2025-04-09 ⋅ 阅读:(32) ⋅ 点赞:(0)

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

目录

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;
            else
                currentNode.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));//true

linke.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));//true

linke.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;
            else
                currentNode.nextNode = currentNode.nextNode.nextNode;
        }
    }

    #endregion

    #region Search
    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;
    }

    #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;
        else
            tailNode = 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;
            }else
            currentNode = currentNode.nextNode;
        }
    }
    #endregion

    #region Search
    public 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;
            }
            else
                currentNode = 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));// true

linke.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 Search
    public 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);
    }
}

 

 

 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布