重温数据结构系列随笔:单链表(c#模拟实现)

上一节我们讲述了数据结构的基本概念,这一节让我们来讨论下单链表的概念和实现

我从书中简单摘录下单链表概念

简单而言单链表的是通过许多节点构成,每个节点包含2个重要元素:该节点数据(数据域)和指向下个节点的地址(指针域)

这样说太枯燥了,让我们直接用c# 来一步步实现

既然一个节点是由(数据域)和(指针域)构成,那我们简单DIY一个LinkNode类

     /// <summary>
     /// 单链表的节点
     /// </summary>
    public  class LinkNode
    {
//节点数据域
        public object LinkNodeData { get; set; }
        //自己节点的地址
        public Guid SelfAddress { get; set; }
        //下个节点的地址指针(存储位置)
        public Guid NextAddress { get; set; }
    }

继续来了解概念了,既然节点准备好了,那我们要了解节点是怎么通过指针域连接在一起的,看图

图中节点就是一个小矩形,数据域是姓名,指针域就是那个箭头所表示的指向它的后继,头节点h->zhao->Qian->....Wang

这样连接起来就是一个完整的单链表,头结点的数据域可以是任何信息,尾节点的地址域是空(他没有后继节点了)

好,代码中我们只有node 没有LinkTable,那我们就按照上图来建立一个LinkTable类

public class LinkTable
    {
        //定义一个LinkNode集合
        List<LinkNode> list = new List<LinkNode>();


        public LinkTable()
        {


        }


        /// <summary>
        ///  进行单向链表初始化
        /// </summary>
        public void InitialList()
        {


            //添加5个节点拥有唯一的guid作为自身地址,后继节点地址为guid.empty
            for (int i = 0; i < 5; i++)
            {
                list.Add
                    (
                      new LinkNode { LinkNodeData = string.Format("第{0}个节点", i + 1), SelfAddress = Guid.NewGuid(), NextAddress = Guid.Empty }
                    );
            }


s
            var j = 0;
            //将节点的 指针域指向下一个节点的地址
            list.ForEach
                (
                   (linkNode) =>
                   {
                       if (j < list.Count - 1)
                       {
                           linkNode.NextAddress = list.Skip(++j).FirstOrDefault().SelfAddress;
                       }
                   }
                );
          }
    }

LinkTable类包含一个LinkNode集合 和一个初始方法,这个方法是先添加节点数据到集合中,然后将节点的地址域一一连接起来

肯定会有朋友问我,那么你怎么在单链表中插入数据或删除数据呢?

非常棒的问题,看图:

图中可以看出a节点的后继是b节点,a节点的指针域指向b节点,那如果在a节点和b节点中添加一个新的节点那情况又如何?

其实图中已经表达出来了,将a的指针域指向新节点,然后将新节点的指针域指向b节点

马上看代码理解

既然是添加节点那我们在LinkTable类中添加方法就行

/// <summary>
        /// 添加一个新节点
        /// </summary>
        /// <param name="node">节点</param>
        /// <param name="addIndex">在index处添加节点</param>
        public void AddNode(LinkNode node, int addIndex)
        {


            if (this.list == null || node == null)
            {
                // 如果链表为空则初始链表并且添加节点
                this.InitialList();
            }
            if (addIndex < 0 || addIndex > list.Count)
            {
                throw new IndexOutOfRangeException("removeIndex超出范围");
            }
            var listCount = list.Count;
            //注意,得到新插入节点的前一个索引位置
            var prev = addIndex - 1 <= 0 || listCount <= 0 ? 0 : addIndex - 1;
            //注意,得到新插入节点的后一个索引位置
            var after = listCount <= 0 ? 0 :
                addIndex > listCount - 1 ? listCount - 1 : addIndex;
            //插入后前一个节点
            var prevNode = list[prev];
            //插入后后一个节点
            var afterNode = list[after];
            //将前一个节点的指针域指向新节点
            node.NextAddress = afterNode.SelfAddress;
            //将新节点的指针域指向后一个节点
            prevNode.NextAddress = node.SelfAddress;
            //判断是否插入到最后一个位置
            if (addIndex == list.Count)
            {
                node.NextAddress = Guid.Empty;
                list.Add(node);
            }
            else
            {
                // 插入新节点
                list.Insert(addIndex, node);
            }
        }

代码注释能够帮助你了解下添加节点的具体过程,请大家仔细消化下

最后是删除一个节点的情况:

和添加节点正好逆向思维,当我们删除b节点时,我们要将a节点的指针域指向c节点保证我们的单链表不被破坏

删除方法同样写在LinkTable类中

/// <summary>
        /// 通过索引删除
        /// </summary>
        /// <param name="removeIndex"></param>
        /// <returns></returns>
        public void Remove(int removeIndex)
        {
            if (this.list == null)
            {
                // 如果链表为空则初始链表并且添加节点
                this.InitialList();
            }
            if (removeIndex > this.list.Count - 1 || removeIndex < 0)
            {
                throw new IndexOutOfRangeException("removeIndex超出范围");
            }


            var preIndex = removeIndex - 1;
            var afterIndex = removeIndex + 1;
            var preNode = list[preIndex];
            var afterNode = list[afterIndex];


            //将被删除节点前后的指针域进行整理
            preNode.NextAddress = afterNode.SelfAddress;
            //删除该节点
            list.Remove(list[removeIndex]);
        }

ok,这就是单链表的一个简单理解,请大家务必牢记,因为后章的循环列表将更复杂,单链表只是一个链表的基础(以下是完整代码及输出情况)


class Program
    {
        static void Main(string[] args)
        {
 
 
            LinkTable table = new LinkTable();
            //初始化
            table.InitialList();
            //尝试添加一个新节点
            table.AddNode
                (
                  new LinkNode {  LinkNodeData="新节点",NextAddress=Guid.Empty, SelfAddress=Guid.NewGuid()},
                );
             //删除一个节点
             table.Remove(1);


            var i = 0;
            //循环显示
            table.list.ForEach
                (
                 (linkNode) =>
                 {
                     if (i ==table.list.Count - 1)
                     {
                         Console.Write("{0} ->{1}", linkNode.LinkNodeData, "Null");
                     }
                     else
                     {
                         Console.Write("{0} ->", linkNode.LinkNodeData);
                     }
                     i++;
                 }
                );




            Console.ReadLine();
        }


 


    }




         /// <summary>
         /// 单链表的节点
         /// </summary>
        public  class LinkNode
        {
            //节点数据域
            public object LinkNodeData { get; set; }
            //自己节点的地址
            public Guid SelfAddress { get; set; }
            //下个节点的地址指针(存储位置)
            public Guid NextAddress { get; set; }
        }


     /// <summary>
     /// 单链表
     /// </summary>
    public class LinkTable
    {
        //定义一个LinkNode集合
        public List<LinkNode> list = new List<LinkNode>();


        public LinkTable()
        {


        }


        /// <summary>
        ///  进行单向链表初始化
        /// </summary>
        public void InitialList()
        {


            //添加10个节点拥有唯一的guid作为自身地址,后继节点地址为guid.empty
            for (int i = 0; i < 5; i++)
            {
                list.Add
                    (
                      new LinkNode { LinkNodeData = string.Format("第{0}个节点", i + 1), SelfAddress = Guid.NewGuid(), NextAddress = Guid.Empty }
                    );
            }




            var j = 0;
            //将节点的 指针域指向下一个节点的地址
            list.ForEach
                (
                   (linkNode) =>
                   {
                       if (j < list.Count - 1)
                       {
                           linkNode.NextAddress = list.Skip(++j).FirstOrDefault().SelfAddress;
                       }
                   }
                );


        }


        /// <summary>
        /// 添加一个新节点
        /// </summary>
        /// <param name="node">节点</param>
        /// <param name="addIndex">在index处添加节点</param>
        public void AddNode(LinkNode node, int addIndex)
        {


            if (this.list == null || node == null)
            {
                // 如果链表为空则初始链表并且添加节点
                this.InitialList();
            }
            if (addIndex < 0 || addIndex > list.Count)
            {
                throw new IndexOutOfRangeException("removeIndex超出范围");
            }
            var listCount = list.Count;
            //注意,得到新插入节点的前一个索引位置
            var prev = addIndex - 1 <= 0 || listCount <= 0 ? 0 : addIndex - 1;
            //注意,得到新插入节点的后一个索引位置
            var after = listCount <= 0 ? 0 :
                addIndex > listCount - 1 ? listCount - 1 : addIndex;
            //插入后前一个节点
            var prevNode = list[prev];
            //插入后后一个节点
            var afterNode = list[after];
            //将前一个节点的指针域指向新节点
            node.NextAddress = afterNode.SelfAddress;
            //将新节点的指针域指向后一个节点
            prevNode.NextAddress = node.SelfAddress;
            //判断是否插入到最后一个位置
            if (addIndex == list.Count)
            {
                node.NextAddress = Guid.Empty;
                list.Add(node);
            }
            else
            {
                // 插入新节点
                list.Insert(addIndex, node);
            }
        }


        /// <summary>
        /// 通过索引删除
        /// </summary>
        /// <param name="removeIndex"></param>
        /// <returns></returns>
        public void Remove(int removeIndex)
        {
            if (this.list == null)
            {
                // 如果链表为空则初始链表并且添加节点
                this.InitialList();
            }
            if (removeIndex > this.list.Count - 1 || removeIndex < 0)
            {
                throw new IndexOutOfRangeException("removeIndex超出范围");
            }


            var preIndex = removeIndex - 1;
            var afterIndex = removeIndex + 1;
            var preNode = list[preIndex];
            var afterNode = list[afterIndex];


            //将被删除节点前后的指针域进行整理
            preNode.NextAddress = afterNode.SelfAddress;
            //删除该节点
            list.Remove(list[removeIndex]);
        }
    }

输出:

希望大家对单链表有比较深的理解,其实在效率性能上这样的单链表不及数组,因为数组更本没有那么繁琐,

大家在实际项目还是用数组比较好,下章会和大家先补充下c#中的LinkList类和Array类的区别(*数组和链表的区别(很重要)),

然后简单说下循环链表。

本文分享自微信公众号 - 我为Net狂(dotNetCrazy)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-06-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏.NET后端开发

C#委托使用详解(Delegates)

摘要 委托是C#编程一个非常重要的概念,也是一个难点。本文将系统详细讲解委托。 1. 委托是什么? 其实,我一直思考如何讲解委托,才能把委托说得更透彻。说实话,...

37250
来自专栏机器学习算法与Python学习

基于遗传算法(C#编写)的智能组卷系统优化

最近由于项目的需要,基于.Net 4.0框架和WPF开发window的客户端(开发环境为win7 旗舰版;Visual Studio 2013),在功能实现上需...

40880
来自专栏逸鹏说道

2015最新编程语言排行榜出炉:C#继续彪涨

这是一个时间问题,苹果宣布从Objective-C转向Swift不久,Objective-C进入自由落体。本月Objective-C的Tiobe指数最高下跌10...

29150
来自专栏个人随笔

C# 操作 access 数据库

private staticstring connStr = @"Provider= Microsoft.Ace.OLEDB.12.0;...

475130
来自专栏逸鹏说道

GeetTest~下一代验证(附C#案例)

基本介绍 极验验证除了在服务器端提供了广泛的语言支持外,在客户端也提供了多平台的扩展支持。 客户端主要涵盖了如下平台: pcWeb 普通台式电脑,笔记本电脑w...

504110
来自专栏个人随笔

C# 操作 access 数据库

随笔: (1)   命名空间             using System.Data.OleDb; (2)   连接字符串             priv...

33150
来自专栏逸鹏说道

关于是否在C#中加入不可空引用类型的争论

来自微软的Mads Togersen在近期所提出的一条提议,即在C#语言中加入对不可空引用类型的支持在.NET社区中引起了热烈的争论。人们对此提议的反应大相径庭...

27750
来自专栏小樱的经验随笔

【C#学习笔记之一】C#中的关键字

C#中的关键字 关键字是对编译器具有特殊意义的预定义保留标识符。它们不能在程序中用作标识符,除非它们有一个 @ 前缀。例如,@if 是有效的标识符,但 if 不...

50140
来自专栏逸鹏说道

Birdge.NET:将C#代码转换为JavaScript

Birdge.NET 是一个可以将C#代码转换为JavaScript的开源编译器,由 Object.NET于2015年5月推出。它允许开发者使用C#编写平台独立...

34240
来自专栏逸鹏说道

C# 实现发送手机短信

现在很多网站都是短信发送的功能,怎么实现的呢。对于个人站长来说的话,通过使用SMS短信通API接口相对比较划算和简单。那怎么实现呢,步骤如下: 1. 从网上(h...

1.2K40

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励