数据结构----双向链表的简约实现方式

原创 lronelove 随笔 浅谈数据结构 99阅读 2018-09-03 23:13:57 举报

作为一名程序员,编程中很痛苦的一件事情就是看一大段没有注释,而且多层嵌套,多层循环的代码,有时候暗自骂一句‘哈麻批’。
在之前一篇文章中,数据结构----双向链表里面,就有很多临界条件判断,而且有多层循环,我讨厌这样的代码。所以,我写完之后也在思考,是否有更好的实现方式。今天偶尔有空,实现了一下,把140行垃圾代码,精简到70行。我们来看下实现过程。

1.结点的结构

结点的结构还是没变,key值存储数据,prev指向前驱结点,next指向后继结点。
如图1:


代码如下:

2.链表的结构

链表的结构也大致和之前一样,只不过初始化的时候,头部结点head和尾部结点提前定义,而且不会变化。这样做的好处是,我们无需判断很多边界问题,所以代码量会减少很多。
代码如下:

在这里,head的key和tai的key使用了Symbol,保证了它们的key值不会与之后加入的结点的key值相同。初始化的时候,head的next指向tail,tail的prev指向head.

3.push方法

这个方法相对好实现,只需要在tail结点之前,加上一个结点就可以了。
代码如下:

添加完成之后链表的结构如图:

4.insert(data, pos)把key为data的结点插入在第pos + 1个结点之前(不包括首尾结点)
代码如下:

我们在之前创建的链表里面插入了now到第一个位置(除开头部结点),把must插入到jack后面,最后,我们希望jack能永远❤️rose.
大家可以点击代码右上角的运行,看下打印的链表结构。
这段代码的实现,比之前的实现要容易看很多,没有很多临界条件判断,也简约了很多。简约的代码就是一种美。

5.remove(data),移除为key的data的结点

我们需要从head结点开始循环,直到找到key为data的结点,改变此结点前驱结点与后继结点的关系,并返回key,找不到返回-1.
代码如下:

泰坦尼克号沉了,jack无法永远爱rose了。。。

好了,说了这么多该洗洗睡了,晚安。

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复