数据结构C#版笔记--双向链表(DbLinkList)

这是数据结构C#版笔记--线性表(Data Structure)之单链表(LinkList)的继续,对于双向链接,节点上除了Next属性外,还要有Prev属性用来指向前一个节点,DbNode定义如下:

namespace 线性表
{
    public class DbNode<T>
    {
        private T data;
        private DbNode<T> prev;
        private DbNode<T> next;


        public DbNode(T data, DbNode<T> next,DbNode<T> prev)
        {
            this.data = data;
            this.next = next;
            this.prev = prev;
        }

        public DbNode(T data, DbNode<T> next) 
        {
            this.data = data;
            this.next = next;
            this.prev = null;
        }

        public DbNode(DbNode<T> next) 
        {
            this.data = default(T);
            this.next = next;
            this.prev = null;
        }

        public DbNode(T data) 
        {
            this.data = data;
            this.next = null;
            this.prev = null;
        }

        public DbNode() 
        {
            data = default(T);
            next = null;
            prev = null;
        }

        public T Data 
        {
            set { this.data = value; }
            get { return this.data; }
        }

        public DbNode<T> Prev 
        {
            get { return prev; }
            set { prev = value; }
        }

        public DbNode<T> Next 
        {
            get { return next; }
            set { next = value; }
        }


    }
}

双链表的插入操作要稍微复杂一点,示意图如下:

同样对于删除操作,也要额外处理prev指向

完整实现DbLinkList<T>:

using System;
using System.Text;

namespace 线性表
{
    public class DbLinkList<T> : IListDS<T>
    {
        private DbNode<T> head;

        public DbNode<T> Head
        {
            get { return head; }
            set { head = value; }
        }

        public DbLinkList()
        {
            head = null;
        }

        /// <summary>
        /// 类索引器
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T this[int index] 
        {
            get 
            {
                return this.GetItemAt(index);
            }
        }

        /// <summary>
        /// 返回单链表的长度
        /// </summary>
        /// <returns></returns>
        public int Count()
        {
            DbNode<T> p = head;
            int len = 0;
            while (p != null)
            {
                len++;
                p = p.Next;
            }
            return len;
        }

        /// <summary>
        /// 清空
        /// </summary>
        public void Clear()
        {
            head = null;
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return head == null;
        }

        /// <summary>
        /// 在最后附加元素
        /// </summary>
        /// <param name="item"></param>
        public void Append(T item)
        {
            DbNode<T> d = new DbNode<T>(item);
            DbNode<T> n = new DbNode<T>();

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

            n = head;
            while (n.Next != null)
            {
                n = n.Next;
            }
            n.Next = d;
            d.Prev = n;
        }

        //前插
        public void InsertBefore(T item, int i)
        {
            if (IsEmpty() || i < 0)
            {
                Console.WriteLine("List is empty or Position is error!");
                return;
            }

            //在最开头插入
            if (i == 0)
            {
                DbNode<T> q = new DbNode<T>(item);
                q.Next = head;//把"头"改成第二个元素
                head.Prev = q;
                head = q;//把自己设置为"头"
                return;
            }

            DbNode<T> n = head;
            DbNode<T> d = new DbNode<T>();
            int j = 0;

            //找到位置i的前一个元素d
            while (n.Next != null && j < i)
            {
                d = n;
                n = n.Next;
                j++;
            }

            if (n.Next == null) //说明是在最后节点插入(即追加)
            {
                DbNode<T> q = new DbNode<T>(item);
                n.Next = q;
                q.Prev = n;
                q.Next = null;
            }
            else
            {
                if (j == i)
                {
                    DbNode<T> q = new DbNode<T>(item);
                    d.Next = q;
                    q.Prev = d;
                    q.Next = n;
                    n.Prev = q;
                }
            }
        }

        /// <summary>
        /// 在位置i后插入元素item
        /// </summary>
        /// <param name="item"></param>
        /// <param name="i"></param>
        public void InsertAfter(T item, int i)
        {
            if (IsEmpty() || i < 0)
            {
                Console.WriteLine("List is empty or Position is error!");
                return;
            }

            if (i == 0)
            {
                DbNode<T> q = new DbNode<T>(item);
                q.Next = head.Next;
                head.Next.Prev = q;
                head.Next = q;
                q.Prev = head;
                return;
            }

            DbNode<T> p = head;
            int j = 0;

            while (p != null && j < i)
            {
                p = p.Next;
                j++;
            }
            if (j == i)
            {
                DbNode<T> q = new DbNode<T>(item);
                q.Next = p.Next;
                if (p.Next != null)
                {
                    p.Next.Prev = q;
                }
                p.Next = q;
                q.Prev = p;
            }
            else             
            {
                Console.WriteLine("Position is error!");
            }
        }

        /// <summary>
        /// 删除位置i的元素
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public T RemoveAt(int i)
        {
            if (IsEmpty() || i < 0)
            {
                Console.WriteLine("Link is empty or Position is error!");
                return default(T);
            }

            DbNode<T> q = new DbNode<T>();
            if (i == 0)
            {
                q = head;
                head = head.Next;
                head.Prev = null;
                return q.Data;
            }

            DbNode<T> p = head;
            int j = 0;

            while (p.Next != null && j < i)
            {
                j++;
                q = p;
                p = p.Next;
            }

            if (j == i)
            {
                p.Next.Prev = q;
                q.Next = p.Next;                
                return p.Data;
            }
            else
            {
                Console.WriteLine("The node is not exist!");
                return default(T);
            }
        }

        /// <summary>
        /// 获取指定位置的元素
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public T GetItemAt(int i)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is empty!");
                return default(T);
            }

            DbNode<T> p = new DbNode<T>();
            p = head;

            if (i == 0) 
            { 
                return p.Data; 
            }

            int j = 0;

            while (p.Next != null && j < i)
            {
                j++;
                p = p.Next;
            }

            if (j == i)
            {
                return p.Data;
            }
            else
            {
                Console.WriteLine("The node is not exist!");
                return default(T);
            }
        }

        //按元素值查找索引
        public int IndexOf(T value)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is Empty!");
                return -1;
            }
            DbNode<T> p = new DbNode<T>();
            p = head;
            int i = 0;
            while (!p.Data.Equals(value) && p.Next != null)
            {
                p = p.Next;
                i++;
            }
            return i;
        }

        /// <summary>
        /// 元素反转
        /// </summary>
        public void Reverse()
        {
            DbLinkList<T> result = new DbLinkList<T>();
            DbNode<T> t = this.head;
            result.Head = new DbNode<T>(t.Data);
            t = t.Next;

            //(把当前链接的元素从head开始遍历,逐个插入到另一个空链表中,这样得到的新链表正好元素顺序跟原链表是相反的)
            while (t!=null)
            {                
                result.InsertBefore(t.Data, 0);
                t = t.Next;
            }
            this.head = result.head;//将原链表直接挂到"反转后的链表"上
            result = null;//显式清空原链表的引用,以便让GC能直接回收
        }

        //得到某个指定的节点(为了下面测试从后向前遍历)
        private DbNode<T> GetNodeAt(int i){
            if (IsEmpty())
            {
                Console.WriteLine("List is empty!");
                return null;
            }

            DbNode<T> p = new DbNode<T>();
            p = head;

            if (i == 0)
            {
                return p;
            }

            int j = 0;

            while (p.Next != null && j < i)
            {
                j++;
                p = p.Next;
            }

            if (j == i)
            {
                return p;
            }
            else
            {
                Console.WriteLine("The node is not exist!");
                return null;
            }
        }

        /// <summary>
        /// 测试用prev属性从后面开始遍历
        /// </summary>
        /// <returns></returns>
        public string TestPrevErgodic() 
        {
            DbNode<T> tail = GetNodeAt(Count() - 1);
            StringBuilder sb = new StringBuilder();
            sb.Append(tail.Data.ToString() + ",");
            while (tail.Prev != null)
            {
                sb.Append(tail.Prev.Data.ToString() + ",");
                tail = tail.Prev;
            }
            return sb.ToString().TrimEnd(',');            
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            DbNode<T> n = this.head;
            sb.Append(n.Data.ToString() + ",");
            while (n.Next != null)
            {
                sb.Append(n.Next.Data.ToString() + ",");
                n = n.Next;
            }
            return sb.ToString().TrimEnd(',');

        }
    }
}

测试代码片段:

            Console.WriteLine("-------------------------------------");
            Console.WriteLine("双链表测试开始...");
            DbLinkList<string> dblink = new DbLinkList<string>();
            dblink.Head = new DbNode<string>("x");
            dblink.InsertBefore("w", 0);
            dblink.InsertBefore("v", 0);
            dblink.Append("y");
            dblink.InsertBefore("z", dblink.Count());
            Console.WriteLine(dblink.Count());//5
            Console.WriteLine(dblink.ToString());//v,w,x,y,z
            Console.WriteLine(dblink[1]);//w
            Console.WriteLine(dblink[0]);//v
            Console.WriteLine(dblink[4]);//z
            Console.WriteLine(dblink.IndexOf("z"));//4
            Console.WriteLine(dblink.RemoveAt(2));//x
            Console.WriteLine(dblink.ToString());//v,w,y,z
            dblink.InsertBefore("x", 2);
            Console.WriteLine(dblink.ToString());//v,w,x,y,z
            Console.WriteLine(dblink.GetItemAt(2));//x
            dblink.Reverse();
            Console.WriteLine(dblink.ToString());//z,y,x,w,v
            dblink.InsertAfter("1", 0);
            dblink.InsertAfter("2", 1);
            dblink.InsertAfter("6", 5);
            dblink.InsertAfter("8", 7);
            dblink.InsertAfter("A", 10);//Position is error!
            Console.WriteLine(dblink.ToString()); //z,1,2,y,x,w,6,v,8  

            string _tail = dblink.GetItemAt(dblink.Count()-1);
            Console.WriteLine(_tail);

            Console.WriteLine(dblink.TestPrevErgodic());//8
            Console.ReadKey(); //8,v,6,w,x,y,2,1,z

当然从上面的测试代码中,似乎并不能看出双链表的优点,双链表的好处在于,如果需要在链表中,需要通过某个节点得到它的前驱节点时,双链表直接用prev属性就能找到;而单链表要做到这一点,必须再次从Head节点开始一个一个用Next向下找,这样时间复杂度从O(n)降到O(1),显然更有效率。

注:如果把双链表再做一下改造,让头尾接起来,即Head的Prev属性指向最后一个节点(就叫做Tail吧),同时把Tail节点的Next属性指向Head节点,就形成了所谓的“循环双向链表”

当然,这样的结构可以在链表中再增加一个Tail节点属性,在做元素插入或删除时,可以循环到底以更新尾节点Tail(当然这样会给插入/删除元素带来一些额外的开销),但是却可以给GetItemAt(int i)方法带来优化的空间,比如要查找的元素在前半段时,可以从Head开始用next向后找;反之,如果要找的元素在后半段,则可以从Tail节点用prev属性向前找。

注:.Net中微软已经给出了一个内置的双向链表System.Collections.Generic.LinkedList<T>,在了解双链表的原理后,建议大家直接系统内置的链表。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术博客

编写高质量代码改善C#程序的157个建议[为类型输出格式化字符串、实现浅拷贝和深拷贝、用dynamic来优化反射]

  本文已更新至http://www.cnblogs.com/aehyok/p/3624579.html 。本文主要学习记录以下内容:

10630
来自专栏二进制文集

JSON Java 解析

要使程序可以运行必须引入JSON-lib包——org.json.jar包。综合来看,这个JAR包比较好用。

18620
来自专栏技术之路

Expression 表达式树学习整理

整理了一下表达式树的一些东西,入门足够了 先从ConstantExpression 开始一步一步的来吧  它表示具有常量值的表达式 我们选建一个控制台应用程序 ...

19180
来自专栏跟着阿笨一起玩NET

DataGridView绑定BindingList<T>带数据排序的类

本文章转载:http://yuyingying1986.blog.hexun.com/30905610_d.html

9210
来自专栏yl 成长笔记

c# 委托(Func、Action)

以前自己写委托都用 delegate, 最近看组里的大佬们都用 Func , 以及 Action 来实现, 代码简洁了不少, 但是看得我晕晕乎乎。 花点时间研究...

2.1K30
来自专栏cs

c#知识点2.0 语句

主要说一下我认为比较重要的东西。 foreach循环 格式: foreach(类型 循环变量 in 变量的取值集合) 变量值集合类型必须是一个集合,而循环变...

36360
来自专栏码云1024

C#反射

31330
来自专栏GreenLeaves

C# 自定义类型通过实现IFormattable接口,来输出指定的格式和语言文化的字符串(例:DateTime)

在开发一些国际化的应用时,应用程序需要调用与当前线程不同的语言文化来格式化字符串.

13630
来自专栏大内老A

由for V.S. for each想到的

一直想写一系列如何提高Performance和Scalability的文章,把我的相关经验和所知道的相关的技巧同大家分享。前一阵在园子里有一篇讨论for eac...

19580
来自专栏跟着阿笨一起玩NET

在C#中ParameterizedThreadStart和ThreadStart区别

10310

扫码关注云+社区

领取腾讯云代金券