转:双向链表dblinklist
2024-10-18 17:34:53
数据结构C#版笔记--双向链表(DbLinkList)
这是数据结构C#版笔记--线性表(Data Structure)之单链表(LinkList)的继续,对于双向链接,节点上除了Next属性外,还要有Prev属性用来指向前一个节点,DbNode定义如下:
双链表的插入操作要稍微复杂一点,示意图如下:
同样对于删除操作,也要额外处理prev指向
完整实现DbLinkList<T>:
测试代码片段:
当然从上面的测试代码中,似乎并不能看出双链表的优点,双链表的好处在于,如果需要在链表中,需要通过某个节点得到它的前驱节点时,双链表直接用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>,在了解双链表的原理后,建议大家直接系统内置的链表。
作者:菩提树下的杨过
出处:http://yjmyzz.cnblogs.com
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
出处:http://yjmyzz.cnblogs.com
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
最新文章
- Winform进程、线程
- webform LinQ
- 【SQL Server】SQL Server基础之存储过程
- Java_java动态编译整个项目,解决jar包找不到问题
- JAVA递归算法
- flash 和 第三方程序交互
- Codeforces Round #130 (Div. 2) C - Police Station 最短路+dp
- Servlet课程0426(十)Servlet如何删除cookie
- (转)IOS开发之——绘图(CGContext)
- ECSTORE 关于前台页面DIALOG的调用
- Windows坐标系
- window.open 使用方法总结
- Android System Property 解析
- 为什么说Java程序员到了必须掌握Spring Boot的时候?
- vue使用v-if v-show页面闪烁,div闪现的解决方法
- win7 下安装使用 nginx 出现500错误
- oracle查看和替换含不可见字符(空白)
- Oracle 大小写转换函数
- NSTimer、performSelector 函数没有被调用的原因
- 【Java】数组使用