数据结构----双向链表

原创 lronelove 随笔 浅谈数据结构 93阅读 2018-08-31 13:24:24 举报

我们在数据结构--队列的链表实现里面使用了链表结构。每一个结点都有一个next属性,指向下一个结点。当我们查找某个结点'rose'的时候,需要从头开始进行遍历,当结点数量比较少的时候还能接受,但是当结点数量特别大,而你想获取靠近尾部的结点,那就有点愚蠢了。
有没有更好的方法呢?此时双向链表就可以满足我们的需求了。

1.什么是双向链表?

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继(next)和直接前驱(prev)。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

2.单个结点是怎样的呢?

单个结点如图1:

很自然,我们可以构造出这样的结点:

3.双向链表有什么属性和方法呢?

  • head: 指向头部结点
  • tail: 指向尾部结点
  • length: 双向链表的长度
  • push(data):想链表尾部添加一个key为data的结点:
  • insert(data, pos): 在pos + 1 个结点之前插入,key = data的结点
  • remove(data): 删除key = data 的结点,并返回这个结点值
  • isEmpty(): 返回链表是否为空。
  • 等等

4.初始化一个空的双向链表

这个初始化和单向链表是一样的,如下:

head和tail初始化为null,链表长度为0

5.push(key)方法

现在链表里面什么都没有,我们想链表的尾部添加一些结点:

然后,我们创建一个链表,并加上三个结点:

当添加第一个结点jack的时候,链表如下图2:

当添加第二个结点love的时候,链表如下图3:

当添加第三个结点tail的时候,链表如下图4:

在控制台打印出来的结果如下图5:

可以看见,我们从头部head开始,一直查找结点的next属性,可以看到顺序为jack -> love -> rose
我们再从尾部tail开始,一直查找结点的prev属性,可以看到顺序为rose -> love -> jack
可以看见顺序便利和逆序遍历他们都是相爱的。

6.print()方法,顺序打印结点key值

为了更加直观地展示,链表的顺序,我们实现一个print方法,依次打印每个结点的key值。
代码也不难:

我们调用一下这个方法:

控制台结果如下图6:

可以看见结点顺序是jack -> love -> rose,更加直观

7.remove(data),移除掉key = data的结点,并且返回该结点;如果找不到返回-1。
代码如下:

我们尝试调用下这个方法:

先添加三个结点,1秒之后一个个把它们移除,每次移除之后顺序打印出剩下结点的key值。

结果如图7:

第一次移除love,剩下只有jack 和 rose了
第二次移除love,剩下只有jack了
第三次移除链表为空

8.insert(data, pos),链表的插入方法

我们可不只是希望只能在链表的尾部进行添加,我们希望还可以在任何地方进行添加,所以我们想有一个方法insert(data, pos)可以把key为data的结点,插入在第pos + 1个结点之前。
下面是实现方法:

我们去掉用这个方法:

结果如下图8:

9.备注:

1.还有isEmpty()等方法,大家有兴趣可以去实现一下
2.一种功能可能有多种实现方式,说不定我们可以找到更好的方法,来替换掉多层的嵌套,以及大量的判断语句
3.want to see your better code

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

赶紧努力消灭 0 回复