C# 算法之链表、双向链表以及正向反向遍历实现

郑小超.

发布于 2022-03-24 08:34:45

4560

发布于 2022-03-24 08:34:45

文章被收录于专栏：GreenLeaves GreenLeavesGreenLeaves

1、简介

链表是一种非常基础的数据结构之一,我们在日常开发种都会接触到或者是接触到相同类型的链表数据结构.所以本文会使用C#算法来实现一个简单的链表数据结构,并实现其中几个简单的api以供使用.

2、概述

链表是一种递归的数据结构,他或者为null,或者是指向像一个节点的(node)的引用,该节点含有一个泛型的元素(当然可以是非泛型的,但是为了充分利用C#的优势,切让链表更具有灵活性,这里使用泛型)和指向另一个链表的引用.

3、实战单向链表

如下图,因为下一个节点对象没有保持上个节点的引用,所以这种链表称之为单向链表

实现代码如下,这边我使用了迭代器模式,方便节点的单向遍历,因为没有使用MS提供的标准的迭代器接口,所以无法使用foreach遍历.

    /// <summary>
    /// C#链表实现
    /// </summary>
    public class LinkedList
    {
        static void Main(string[] args)
        {
            //生成对应的Node节点
            var nodeFirst = new Node<string>();
            var nodeSecond = new Node<string>();
            var nodeThird = new Node<string>();

            //构造节点内容
            nodeFirst.Item = "one";
            nodeSecond.Item = "two";
            nodeThird.Item = "three";

            //链接节点
            nodeFirst.NodeItem = nodeSecond;
            nodeSecond.NodeItem = nodeThird;
            //注:这里nodeThird的NodeItem指向null

            var nodeEnumerator = nodeFirst.GetEnumerator();
            while (nodeEnumerator.MoveNext())
            {
                Console.Write($"当前节点元素内容:{nodeEnumerator.CurrentItem}");
                //这里如果当前节点的下一个节点不为空,则让当前节点变为下一个节点
                if (nodeEnumerator.SetNext())
                    Console.WriteLine($"下一个节点内容:{nodeEnumerator.CurrentNode.Item}");
                else
                    Console.WriteLine($"链表遍历结束,下一个节点内容为null");
            }
            Console.ReadKey();
            
        }


        /// <summary>
        /// 节点对象,使用迭代器模式,实现链表的遍历
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public class Node<T> : ILinkedListEnumerable<T>
        {
            public T Item { get; set; }

            public Node<T> NodeItem { get; set; }

            public ILinedListEnumerator<T> GetEnumerator()
            {
                return new NodeEnumerator<T>(this);
            }
        }

        private class NodeEnumerator<T> : ILinedListEnumerator<T>
        {
            public Node<T> CurrentNode { get; set; }

            public NodeEnumerator(Node<T> node)
            {
                CurrentNode = node;
            }

            public T CurrentItem => CurrentNode.Item;

            public bool MoveNext()
            {
                if (CurrentNode!=null)
                    return true;
                return false;
            }

            public bool SetNext()
            {
                if (CurrentNode.NodeItem != null)
                {
                    CurrentNode = CurrentNode.NodeItem;
                    return true;
                }
                else {
                    CurrentNode = null;
                    return false;
                }
               
            }

            /// <summary>
            /// 当迭代器内部存在非托管资源时,用于释放资源
            /// </summary>
            public void Dispose()
            {
                throw new NotImplementedException();
            }
        }

        /// <summary>
        /// 链表迭代器接口约束
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public interface ILinkedListEnumerable<T>
        {
            ILinedListEnumerator<T> GetEnumerator();
        }

        /// <summary>
        /// 链表单个迭代器
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public interface ILinedListEnumerator<T> : IDisposable
        {
            /// <summary>
            /// 当前迭代器元素
            /// </summary>
            Node<T> CurrentNode { get; }

            /// <summary>
            /// 当前迭代器元素内容
            /// </summary>
            T CurrentItem { get; }

            /// <summary>
            /// 是否可以进行下一步遍历操作
            /// </summary>
            /// <returns></returns>
            bool MoveNext();

            /// <summary>
            /// 遍历完当前链表元素,使其指向下一个元素
            /// </summary>
            bool SetNext();
        }
    }

4、实战双向链表

双向链表的应用场景很多,比如Redis的List就是使用双向链表实现的.这种形式的链表更加的灵活.

修改代码如下:

    /// <summary>
    /// C#链表实现
    /// </summary>
    public class LinkedList
    {
        static void Main(string[] args)
        {
            //生成对应的Node节点
            var nodeFirst = new Node<string>();
            var nodeSecond = new Node<string>();
            var nodeThird = new Node<string>();

            //构造节点内容
            nodeFirst.Item = "one";
            nodeSecond.Item = "two";
            nodeThird.Item = "three";

            //链接节点
            nodeFirst.NextNode = nodeSecond;
            nodeSecond.NextNode = nodeThird;
            //注:这里nodeThird的NextNode指向null

            var nodeEnumerator = nodeFirst.GetEnumerator();
            while (nodeEnumerator.MoveNext())
            {
                //输出当前节点的内容
                Console.Write($"当前节点元素内容:{nodeEnumerator.CurrentItem}     ");

                //输出上一个节点的内容
                Console.Write($"上一个节点元素内容:{nodeEnumerator.PreviousNode?.Item??"没有上一个节点"}     ");

                //这里如果当前节点的下一个节点不为空,则让当前节点变为下一个节点
                if (nodeEnumerator.SetNext())
                    Console.WriteLine($"下一个节点内容:{nodeEnumerator.CurrentNode.Item}");
                else
                    Console.WriteLine($"链表遍历结束,下一个节点内容为null");
            }
            Console.ReadKey();
            
        }


        /// <summary>
        /// 节点对象,使用迭代器模式,实现链表的遍历
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public class Node<T> : ILinkedListEnumerable<T>
        {
            public T Item { get; set; }

            public Node<T> NextNode { get; set; }

            public ILinedListEnumerator<T> GetEnumerator()
            {
                return new NodeEnumerator<T>(this);
            }
        }

        private class NodeEnumerator<T> : ILinedListEnumerator<T>
        {
            public Node<T> PreviousNode { get; set; }

            public Node<T> CurrentNode { get; set; }

            public NodeEnumerator(Node<T> node)
            {
                CurrentNode = node;
            }

            public T CurrentItem => CurrentNode.Item;

            public bool MoveNext()
            {
                if (CurrentNode!=null)
                    return true;
                return false;
            }

            public bool SetNext()
            {
                if (CurrentNode.NextNode != null)
                {
                    PreviousNode = CurrentNode;
                    CurrentNode = CurrentNode.NextNode;
                    return true;
                }
                else {
                    CurrentNode = null;
                    return false;
                }
               
            }

            /// <summary>
            /// 当迭代器内部存在非托管资源时,用于释放资源
            /// </summary>
            public void Dispose()
            {
                throw new NotImplementedException();
            }
        }

        /// <summary>
        /// 链表迭代器接口约束
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public interface ILinkedListEnumerable<T>
        {
            ILinedListEnumerator<T> GetEnumerator();
        }

        /// <summary>
        /// 链表单个迭代器
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public interface ILinedListEnumerator<T> : IDisposable
        {
            /// <summary>
            /// 上一个迭代器元素
            /// </summary>
            Node<T> PreviousNode { get; }

            /// <summary>
            /// 当前迭代器元素
            /// </summary>
            Node<T> CurrentNode { get; }

            /// <summary>
            /// 当前迭代器元素内容
            /// </summary>
            T CurrentItem { get; }

            /// <summary>
            /// 是否可以进行下一步遍历操作
            /// </summary>
            /// <returns></returns>
            bool MoveNext();

            /// <summary>
            /// 遍历完当前链表元素,使其指向下一个元素
            /// </summary>
            bool SetNext();
        }
    }

5、通过双向链表实现反向遍历

如果没有实现链表的双向功能,实现反向遍历的功能是不可能,实际上Redis的List是实现了这个功能的,所以这里我也实现下,tip:目前为止,所以的遍历都是先进先出的,类似于队列,所以如果实现了反向遍历,从而该双向链表同时也支持了先进后出的功能,类似于栈,为了分离正向和反向这个遍历过程,所以我实现了两个迭代器,分别为正向迭代器和反向迭代器.

代码如下:

    /// <summary>
    /// C#链表实现
    /// </summary>
    public class LinkedList
    {
        static void Main(string[] args)
        {

            //生成对应的Node节点
            var nodeFirst = new Node<string>();
            var nodeSecond = new Node<string>();
            var nodeThird = new Node<string>();

            //构造节点内容
            nodeFirst.Item = "one";
            nodeSecond.Item = "two";
            nodeThird.Item = "three";

            //链接节点
            nodeFirst.NextNode = nodeSecond;
            nodeSecond.NextNode = nodeThird;
            nodeSecond.PreviousNode = nodeFirst;
            nodeThird.PreviousNode = nodeSecond;
            //注:这里nodeThird的NextNode指向null

            var nodeEnumerator = nodeThird.GetNodeReverseEnumerator();
            while (nodeEnumerator.MoveNext())
            {
                //输出当前节点的内容
                Console.Write($"当前节点元素内容:{nodeEnumerator.CurrentItem}     ");

                //输出上一个节点的内容
                Console.Write($"上一个节点元素内容:{nodeEnumerator.PreviousNode?.Item ?? "没有上一个节点"}     ");

                //这里如果当前节点的下一个节点不为空,则让当前节点变为下一个节点
                if (nodeEnumerator.SetNext())
                    Console.WriteLine($"下一个节点内容:{nodeEnumerator?.CurrentNode.Item}");
                else
                    Console.WriteLine($"链表遍历结束,下一个节点内容为null");

                

            }
            Console.ReadKey();
        }


        /// <summary>
        /// 节点对象,使用迭代器模式,实现链表的遍历
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public class Node<T> : ILinkedListEnumerable<T>
        {

            public T Item { get; set; }

            public Node<T> PreviousNode { get; set; }

            public Node<T> NextNode { get; set; }

            /// <summary>
            /// 获取正向迭代器
            /// </summary>
            /// <returns></returns>
            public ILinedListEnumerator<T> GetEnumerator()
            {
                return new NodeEnumerator<T>(this);
            }

            /// <summary>
            /// 获取反向迭代器
            /// </summary>
            /// <returns></returns>
            public ILinedListEnumerator<T> GetNodeReverseEnumerator()
            {
                return new NodeReverseEnumerator<T>(this);
            }
        }

        /// <summary>
        /// 正向迭代器
        /// </summary>
        /// <typeparam name="T"></typeparam>
        private class NodeEnumerator<T> : ILinedListEnumerator<T>
        {
            public Node<T> PreviousNode { get; set; }

            public Node<T> CurrentNode { get; set; }

            public NodeEnumerator(Node<T> node)
            {
                CurrentNode = node;
            }

            public T CurrentItem => CurrentNode.Item;

            public bool MoveNext()
            {
                if (PreviousNode != null)
                    return true;
                return false;
            }

            public bool SetNext()
            {
                if (CurrentNode.PreviousNode != null)
                {
                    PreviousNode = CurrentNode;
                    CurrentNode = CurrentNode.PreviousNode;
                    return true;
                }
                else {
                    CurrentNode = null;
                    return false;
                }
               
            }

            /// <summary>
            /// 当迭代器内部存在非托管资源时,用于释放资源
            /// </summary>
            public void Dispose()
            {
                throw new NotImplementedException();
            }
        }

        /// <summary>
        /// 反向迭代器
        /// </summary>
        private class NodeReverseEnumerator<T>: ILinedListEnumerator<T>
        {
            public Node<T> PreviousNode { get; set; }

            public Node<T> CurrentNode { get; set; }

            public NodeReverseEnumerator(Node<T> node)
            {
                CurrentNode = node;
            }

            public T CurrentItem => CurrentNode.Item;

            public bool MoveNext()
            {
                if (CurrentNode != null)
                    return true;
                return false;
            }

            public bool SetNext()
            {
                if (CurrentNode.PreviousNode != null)
                {
                    PreviousNode = CurrentNode;
                    CurrentNode = CurrentNode.PreviousNode;
                    return true;
                }
                else
                {
                    CurrentNode = null;
                    return false;
                }

            }

            /// <summary>
            /// 当迭代器内部存在非托管资源时,用于释放资源
            /// </summary>
            public void Dispose()
            {
                throw new NotImplementedException();
            }
        }

        /// <summary>
        /// 链表迭代器接口约束
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public interface ILinkedListEnumerable<T>
        {
            /// <summary>
            /// 正向迭代器
            /// </summary>
            /// <returns></returns>
            ILinedListEnumerator<T> GetEnumerator();

            /// <summary>
            /// 反向迭代器
            /// </summary>
            /// <returns></returns>
            ILinedListEnumerator<T> GetNodeReverseEnumerator();
        }

        /// <summary>
        /// 链表单个迭代器
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public interface ILinedListEnumerator<T> : IDisposable
        {
            /// <summary>
            /// 上一个迭代器元素
            /// </summary>
            Node<T> PreviousNode { get; }

            /// <summary>
            /// 当前迭代器元素
            /// </summary>
            Node<T> CurrentNode { get; }

            /// <summary>
            /// 当前迭代器元素内容
            /// </summary>
            T CurrentItem { get; }

            /// <summary>
            /// 是否可以进行下一步遍历操作
            /// </summary>
            /// <returns></returns>
            bool MoveNext();

            /// <summary>
            /// 遍历完当前链表元素,使其指向下一个元素
            /// </summary>
            bool SetNext();
        }
    }