C#进阶学习(四)单向链表和双向链表,循环链表(上)单向链表

发布于:2025-04-18 ⋅ 阅读:(46) ⋅ 点赞:(0)

目录

前置知识:

一、链表中的结点类LinkedNode

1、申明字段节点类:

2、申明属性节点类:

二、两种方式实现单向链表

①定框架:

②增加元素的方法:因为是单链表,所以增加元素一定是只能在末尾添加元素,即在头结点后面添加元素

③删除元素的方法:删除链表中第一个符合删除目标值的节点 

④查找节点是否存在,这个就很简单,直接遍历一遍就好了。

 ⑤更新某一个节点的数据

三、测试 

测试接口:

写一个测试函数:

开始测试:

测试结果:


前置知识:

        数据结构:

数据结构:数据元素之间的相互关系
常用的数据结构
数组、链表、栈、队列、树、图,堆,散列表

         线性表:

线性表是一种数据结构是由n个具有相同特性的数据元素的有限序列
例如:数组、链表、栈、队列,ArrayList

        顺序存储:

数组、Stack、Queue、ArrayList->顺序存储
只是 数组、Stack、Queue、ArrayList的组织规则不同而已
顺序存储
用一组地址连续的存储单元依次存储线性表的各个元素,数据元素之间的逻辑关系由存储单元的邻接关系来体现。内存地址连续,一整片的内存

顺序存储链式存储 是数据结构中的两种存储方式  

        链式存储:

单向链表、双向链表、循环链表->链式存储
链式存储(链接存储)
用一组任意的存储单元存储线性表中的各个数据元素,内存地址不连续跳跃式的。

如需了解更多,可看这一篇文章:

线性表的相关知识

  好的,回归主线,今天咱们学习的重点是单向链表以及双向链表,循环链表

一、链表中的结点类LinkedNode

         什么是LinkedNode呢,他有什么作用呢?他其实就是组成链表的基本单位,链表就是一个个的LinkedNode串起来的,只不过串的方式不太一样。下面代码示例中不一定使用的是LinkedNode这个名字,使用的是其他的名字不过没关系,学习而已。例如:

        在单向链表中:每个链表结点有一个指向下一个链表结点的类似于C语言中的指针的东西,就是说明了,当前节点的下一个就是你,二者建立了联系。对于单向链表中,第一个结点,我们称之为头结点,因为他只能向后指,不能朝前看,所以每次寻找某一个元素,需要进行遍历,而且你永远找不到自己的上一个元素是什么。于是有了双向链表

        在双向链表中:每个链表节点存有两个指针,一个是指向当前结点的上一个结点,一个是指向当前结点的下一个结点,其余的和单向链表相同。

        所谓循环链表:就是在单链表中,将最后一个结点的下一个指向第一个结点。

好的,接下来我们实现这个节点类:

     单向链表的节点类:

两种定义方式:

1、申明字段节点类:

/// <summary>
/// 单向链表节点定义(字段版本)
/// </summary>
/// <typeparam name="T">泛型数据类型</typeparam>
public class ListNode_Field<T>
{
    // 节点存储的数据(字段)
    public T data;

    // 指向下一个节点的指针(字段)
    // "?" 表示这是一个可空类型,允许值为 null
    public ListNode_Field<T>? next;

    /// <summary>
    /// 构造函数
    /// </summary>
    /// <param name="val">节点数据</param>
    public ListNode_Field(T val)
    {
        data = val;
        next = null;
    }
}

2、申明属性节点类:

/// <summary>
/// 单向链表节点定义(属性版本)
/// </summary>
/// <typeparam name="T">泛型数据类型</typeparam>
public class SingleListNode<T>
{
    // 节点存储的数据(属性)
    public T Data { get; set; }

    // 指向下一个节点的指针(属性)
    // "?" 表示这是一个可空类型,允许值为 null
    public SingleListNode<T>? Next { get; set; }

    /// <summary>
    /// 构造函数
    /// </summary>
    /// <param name="data">节点数据</param>
    public SingleListNode(T data)
    {
        Data = data;
        Next = null; // 初始化时指针置空
    }
}

         这两种方式任意选择一种进行申明即可,推荐使用属性,因为可以自己处理的手段更多。

二、两种方式实现单向链表

        好的接下来我们实现一个单向链表,因为有了这些基本节点类,所以才会有下面的代码。同样我们会使用属性节点类和字段节点类进行说明。其实都差不多的。

        总的设计思路:

        1、提供一个头结点

        2、利用这个头结点进行增删改查

        接下来我们一一实现:下面是一个利用字段节点声明的单向链表

①定框架:

    public class SingleLinkedList_Field<T>
    {
        //设置一个私有头结点
        private ListNode_Field<T>? head;
    }

②增加元素的方法:因为是单链表,所以增加元素一定是只能在末尾添加元素,即在头结点后面添加元素

        步骤:

(1)先申明一个新的节点

(2)判断头结点是否为空,为空则添加的元素就是头结点元素,反之遍历找到最后一个节点,然后将最后一个结点的next指向当前新创造的节点

/// <summary>
/// 在链表尾部添加新节点
/// </summary>
public void Add(T data)
{
    ListNode_Field<T> newNode = new ListNode_Field<T>(data);

    if (head == null)
    {
        head = newNode;
        return;
    }

    // 遍历链表找到最后一个节点
    ListNode_Field<T> current = head;
    while (current.next != null)
    {
        current = current.next;
    }
    current.next = newNode; // 直接操作字段
}

        当然这个添加元素,你也可以想想怎么在中间插入一个元素,思想是将上一个的next指向插入元素,插入元素的next指向上一个元素的下一个 

③删除元素的方法:删除链表中第一个符合删除目标值的节点 

        步骤:

(1)先看有没有头结点,没有头结点删除个屁啊

(2)然后看删除的是不是头结点,是的话直接将头结点的next指向下一个就好啦

(3)不是头结点的话,就稍微有一点点麻烦,需要先遍历,和Add方法差不多的

/// <summary>
/// 删除第一个匹配的节点
/// </summary>
public bool Remove(T data)
{
    if (head == null) return false;

    // 处理头节点匹配的情况
    if (head.data != null && head.data.Equals(data))
    {
        head = head.next; // 直接操作字段
        return true;
    }

    ListNode_Field<T> current = head;
    while (current.next != null)
    {
        if (current.next.data != null && current.next.data.Equals(data))
        {
            current.next = current.next.next; // 直接操作字段
            return true;
        }
        current = current.next;
    }
    return false;
}

④查找节点是否存在,这个就很简单,直接遍历一遍就好了。

/// <summary>
/// 查找节点是否存在
/// </summary>
public bool Contains(T data)
{
    ListNode_Field<T>? current = head;
    while (current != null)
    {
        if (current.data != null && current.data.Equals(data))
        {
            return true;
        }
        current = current.next;
    }
    return false;
}

 ⑤更新某一个节点的数据

        步骤:

(1)找到该节点

(2)操作该节点的数据

/// <summary>
/// 更新第一个匹配的节点的值
/// </summary>
public bool Update(T oldData, T newData)
{
    ListNode_Field<T>? node = FindNode(oldData);
    if (node == null) return false;
    node.data = newData; // 直接操作字段
    return true;
}

/// <summary>
/// 辅助方法:查找指定数据的节点
/// </summary>
private ListNode_Field<T>? FindNode(T data)
{
    ListNode_Field<T>? current = head;
    while (current != null)
    {
        if (current.data != null && current.data.Equals(data))
        {
            return current;
        }
        current = current.next;
    }
    return null;
}

        好的,那么我们就完成了一个最简单的单向链表的数据结构!

附上使用属性申明的单行链表,是一样的:

    /// <summary>
    /// 单向链表实现(属性版本)
    /// </summary>
    /// <typeparam name="T">泛型数据类型</typeparam>
    public class SingleLinkedList_Property<T> : ISingleLinkedList<T>
    {
        // 头节点(私有属性)
        private SingleListNode<T>? head;

        /// <summary>
        /// 在链表尾部添加新节点
        /// </summary>
        /// <param name="data">要添加的数据</param>
        public void Add(T data)
        {
            // 显式声明类型(不使用 var)
            SingleListNode<T> newNode = new SingleListNode<T>(data);

            if (head == null)
            {
                head = newNode; // 链表为空时,新节点作为头节点
                return;
            }

            // 遍历链表找到最后一个节点
            SingleListNode<T> current = head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode; // 将新节点链接到尾部
        }

        /// <summary>
        /// 删除第一个匹配的节点
        /// </summary>
        /// <param name="data">要删除的数据</param>
        /// <returns>是否删除成功</returns>
        public bool Remove(T data)
        {
            if (head == null) return false;

            // 处理头节点匹配的情况
            if (head.Data != null && head.Data.Equals(data))
            {
                head = head.Next; // 头节点指向下一个节点
                return true;
            }

            // 遍历链表查找匹配的节点
            SingleListNode<T> current = head;
            while (current.Next != null)
            {
                if (current.Next.Data != null && current.Next.Data.Equals(data))
                {
                    current.Next = current.Next.Next; // 跳过匹配的节点
                    return true;
                }
                current = current.Next;
            }
            return false;
        }

        /// <summary>
        /// 查找节点是否存在
        /// </summary>
        /// <param name="data">要查找的数据</param>
        /// <returns>是否存在</returns>
        public bool Contains(T data)
        {
            SingleListNode<T>? current = head;
            while (current != null)
            {
                if (current.Data != null && current.Data.Equals(data))
                {
                    return true;
                }
                current = current.Next;
            }
            return false;
        }

        /// <summary>
        /// 更新第一个匹配的节点的值
        /// </summary>
        /// <param name="oldData">旧数据</param>
        /// <param name="newData">新数据</param>
        /// <returns>是否更新成功</returns>
        public bool Update(T oldData, T newData)
        {
            SingleListNode<T>? node = FindNode(oldData);
            if (node == null) return false;
            node.Data = newData; // 直接修改节点的数据
            return true;
        }

        /// <summary>
        /// 辅助方法:查找指定数据的节点
        /// </summary>
        private SingleListNode<T>? FindNode(T data)
        {
            SingleListNode<T>? current = head;
            while (current != null)
            {
                if (current.Data != null && current.Data.Equals(data))
                {
                    return current;
                }
                current = current.Next;
            }
            return null;
        }
    }

三、测试 

        测试部分呢,因为两种都差不多,所以我们使用一个接口,让他们都实现里面的方法,然后统一测试

测试接口:

/// <summary>
/// 统一接口(便于测试不同版本的链表)
/// </summary>
public interface ISingleLinkedList<T>
{
    void Add(T data);
    bool Remove(T data);
    bool Contains(T data);
    bool Update(T oldData, T newData);
}

两个链表只要继承了这个接口就好

写一个测试函数:

static void TestLinkedList<T>(T list) where T : ISingleLinkedList<int>
{
    // 添加节点
    list.Add(1);
    list.Add(2);
    list.Add(3);
    Console.WriteLine("添加 1, 2, 3 后链表内容应为:1 -> 2 -> 3");

    // 测试查找
    Console.WriteLine("查找 2: " + list.Contains(2)); // 应输出 True
    Console.WriteLine("查找 4: " + list.Contains(4)); // 应输出 False

    // 测试删除
    list.Remove(2);
    Console.WriteLine("删除 2 后链表内容应为:1 -> 3");
    Console.WriteLine("查找 2: " + list.Contains(2)); // 应输出 False

    // 测试更新
    list.Update(3, 4);
    Console.WriteLine("更新 3 为 4 后链表内容应为:1 -> 4");
    Console.WriteLine("查找 4: " + list.Contains(4)); // 应输出 True
}

开始测试:

 static void Main(string[] args)
 {
     // 测试属性版本链表
     Console.WriteLine("测试属性版本链表:");
     TestLinkedList(new SingleLinkedList_Property<int>());

     // 测试字段版本链表
     Console.WriteLine("\n测试字段版本链表:");
     TestLinkedList(new SingleLinkedList_Field<int>());
 }

测试结果:

 如果再讲双向链表和循环链表,会显得很杂乱,我们将会在下一篇文章讨论,诸位共勉!

附:本文所有代码

namespace 单向链表
{
    /// <summary>
    /// 单向链表节点定义(属性版本)
    /// </summary>
    /// <typeparam name="T">泛型数据类型</typeparam>
    public class SingleListNode<T>
    {
        // 节点存储的数据(属性)
        public T Data { get; set; }

        // 指向下一个节点的指针(属性)
        // "?" 表示这是一个可空类型,允许值为 null(解决 CS8618 警告)
        public SingleListNode<T>? Next { get; set; }

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="data">节点数据</param>
        public SingleListNode(T data)
        {
            Data = data;
            Next = null; // 初始化时指针置空
        }
    }

    /// <summary>
    /// 单向链表节点定义(字段版本)
    /// </summary>
    /// <typeparam name="T">泛型数据类型</typeparam>
    public class ListNode_Field<T>
    {
        // 节点存储的数据(字段)
        public T data;

        // 指向下一个节点的指针(字段)
        // "?" 表示这是一个可空类型,允许值为 null
        public ListNode_Field<T>? next;

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="val">节点数据</param>
        public ListNode_Field(T val)
        {
            data = val;
            next = null;
        }
    }


    internal class Program
    {
        static void Main(string[] args)
        {
            // 测试属性版本链表
            Console.WriteLine("测试属性版本链表:");
            TestLinkedList(new SingleLinkedList_Property<int>());

            // 测试字段版本链表
            Console.WriteLine("\n测试字段版本链表:");
            TestLinkedList(new SingleLinkedList_Field<int>());
        }
        static void TestLinkedList<T>(T list) where T : ISingleLinkedList<int>
        {
            // 添加节点
            list.Add(1);
            list.Add(2);
            list.Add(3);
            Console.WriteLine("添加 1, 2, 3 后链表内容应为:1 -> 2 -> 3");

            // 测试查找
            Console.WriteLine("查找 2: " + list.Contains(2)); // 应输出 True
            Console.WriteLine("查找 4: " + list.Contains(4)); // 应输出 False

            // 测试删除
            list.Remove(2);
            Console.WriteLine("删除 2 后链表内容应为:1 -> 3");
            Console.WriteLine("查找 2: " + list.Contains(2)); // 应输出 False

            // 测试更新
            list.Update(3, 4);
            Console.WriteLine("更新 3 为 4 后链表内容应为:1 -> 4");
            Console.WriteLine("查找 4: " + list.Contains(4)); // 应输出 True
        }
    }
    /// <summary>
    /// 统一接口(便于测试不同版本的链表)
    /// </summary>
    public interface ISingleLinkedList<T>
    {
        void Add(T data);
        bool Remove(T data);
        bool Contains(T data);
        bool Update(T oldData, T newData);
    }
    /// <summary>
    /// 单向链表实现(属性版本)
    /// </summary>
    /// <typeparam name="T">泛型数据类型</typeparam>
    public class SingleLinkedList_Property<T> : ISingleLinkedList<T>
    {
        // 头节点(私有属性)
        private SingleListNode<T>? head;

        /// <summary>
        /// 在链表尾部添加新节点
        /// </summary>
        /// <param name="data">要添加的数据</param>
        public void Add(T data)
        {
            // 显式声明类型(不使用 var)
            SingleListNode<T> newNode = new SingleListNode<T>(data);

            if (head == null)
            {
                head = newNode; // 链表为空时,新节点作为头节点
                return;
            }

            // 遍历链表找到最后一个节点
            SingleListNode<T> current = head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode; // 将新节点链接到尾部
        }

        /// <summary>
        /// 删除第一个匹配的节点
        /// </summary>
        /// <param name="data">要删除的数据</param>
        /// <returns>是否删除成功</returns>
        public bool Remove(T data)
        {
            if (head == null) return false;

            // 处理头节点匹配的情况
            if (head.Data != null && head.Data.Equals(data))
            {
                head = head.Next; // 头节点指向下一个节点
                return true;
            }

            // 遍历链表查找匹配的节点
            SingleListNode<T> current = head;
            while (current.Next != null)
            {
                if (current.Next.Data != null && current.Next.Data.Equals(data))
                {
                    current.Next = current.Next.Next; // 跳过匹配的节点
                    return true;
                }
                current = current.Next;
            }
            return false;
        }

        /// <summary>
        /// 查找节点是否存在
        /// </summary>
        /// <param name="data">要查找的数据</param>
        /// <returns>是否存在</returns>
        public bool Contains(T data)
        {
            SingleListNode<T>? current = head;
            while (current != null)
            {
                if (current.Data != null && current.Data.Equals(data))
                {
                    return true;
                }
                current = current.Next;
            }
            return false;
        }

        /// <summary>
        /// 更新第一个匹配的节点的值
        /// </summary>
        /// <param name="oldData">旧数据</param>
        /// <param name="newData">新数据</param>
        /// <returns>是否更新成功</returns>
        public bool Update(T oldData, T newData)
        {
            SingleListNode<T>? node = FindNode(oldData);
            if (node == null) return false;
            node.Data = newData; // 直接修改节点的数据
            return true;
        }

        /// <summary>
        /// 辅助方法:查找指定数据的节点
        /// </summary>
        private SingleListNode<T>? FindNode(T data)
        {
            SingleListNode<T>? current = head;
            while (current != null)
            {
                if (current.Data != null && current.Data.Equals(data))
                {
                    return current;
                }
                current = current.Next;
            }
            return null;
        }
    }

    /// <summary>
    /// 单向链表实现(字段版本)
    /// </summary>
    /// <typeparam name="T">泛型数据类型</typeparam>
    public class SingleLinkedList_Field<T> :ISingleLinkedList<T>
    {
        // 头节点(私有字段)
        private ListNode_Field<T>? head;

        /// <summary>
        /// 在链表尾部添加新节点
        /// </summary>
        public void Add(T data)
        {
            ListNode_Field<T> newNode = new ListNode_Field<T>(data);

            if (head == null)
            {
                head = newNode;
                return;
            }

            // 遍历链表找到最后一个节点
            ListNode_Field<T> current = head;
            while (current.next != null)
            {
                current = current.next;
            }
            current.next = newNode; // 直接操作字段
        }

        /// <summary>
        /// 删除第一个匹配的节点
        /// </summary>
        public bool Remove(T data)
        {
            if (head == null) return false;

            // 处理头节点匹配的情况
            if (head.data != null && head.data.Equals(data))
            {
                head = head.next; // 直接操作字段
                return true;
            }

            ListNode_Field<T> current = head;
            while (current.next != null)
            {
                if (current.next.data != null && current.next.data.Equals(data))
                {
                    current.next = current.next.next; // 直接操作字段
                    return true;
                }
                current = current.next;
            }
            return false;
        }

        /// <summary>
        /// 查找节点是否存在
        /// </summary>
        public bool Contains(T data)
        {
            ListNode_Field<T>? current = head;
            while (current != null)
            {
                if (current.data != null && current.data.Equals(data))
                {
                    return true;
                }
                current = current.next;
            }
            return false;
        }

        /// <summary>
        /// 更新第一个匹配的节点的值
        /// </summary>
        public bool Update(T oldData, T newData)
        {
            ListNode_Field<T>? node = FindNode(oldData);
            if (node == null) return false;
            node.data = newData; // 直接操作字段
            return true;
        }

        /// <summary>
        /// 辅助方法:查找指定数据的节点
        /// </summary>
        private ListNode_Field<T>? FindNode(T data)
        {
            ListNode_Field<T>? current = head;
            while (current != null)
            {
                if (current.data != null && current.data.Equals(data))
                {
                    return current;
                }
                current = current.next;
            }
            return null;
        }
    }
}