C#数据结构之双向链表(DbLinkList)实例详解
本文实例讲述了C#数据结构之双向链表(DbLinkList)。分享给大家供大家参考,具体如下:
这是继上一篇《C#数据结构之单链表(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>,在了解双链表的原理后,建议大家直接系统内置的链表。
希望本文所述对大家C#程序设计有所帮助。
相关文章
- 我们在使用C#做项目的时候,基本上都需要制作登录界面,那么今天我们就来一步步看看,如果简单的实现登录界面呢,本文给出2个例子,由简入难,希望大家能够喜欢。...2020-06-25
- 这篇文章主要介绍了C# 字段和属性的的相关资料,文中示例代码非常详细,供大家参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧,本文通过图文并茂的形式给大家介绍的非常详细,需要的朋友参考下吧...2021-05-17
- 这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#中new的几种用法,具有很好的参考价值,下面跟着小编一起来看下吧...2020-06-25
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25- 这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
- 这篇文章主要介绍了C#从数据库读取图片并保存的方法,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2021-01-16
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 轻松学习C#的基础入门,了解C#最基本的知识点,C#是一种简洁的,类型安全的一种完全面向对象的开发语言,是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#变量命名规则小结,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-09
- 这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
- 这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法,需要的朋友可以参考下...2020-06-25
- 下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25