看图轻松理解数据结构与算法系列(双向链表)

28,260 阅读3分钟

前言

推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。

双向链表

双向链表属于链表的一种,也叫双链表双向即是说它的链接方向是双向的,它由若干个节点组成,每个节点都包含下一个节点和上一个节点的指针,所以从双向链表的任意节点开始,都能很方便访问他的前驱结点和后继节点。

双链表特点

  • 创建双链表时无需指定链表的长度。
  • 比起单链表,双链表需要多一个指针用于指向前驱节点,所以需要存储空间比单链表多一点。
  • 双链表的插入和删除需要同时维护 next 和 prev 两个指针。
  • 双链表中的元素访问需要通过顺序访问,即要通过遍历的方式来寻找元素。

双链表创建

创建一个空链表,

image

插入链尾

the monster is coming这些单词按顺序分别插入尾部,创建“the”节点,

image

连接起来,

image

创建“monster”节点,

image

再连接起来,

image

以此类推,将剩下的节点全部创建并连接起来。

image

image

创建迭代器

迭代器的 current 指针初始指向head,

image

执行两次 next 操作, current 指针指向索引为2的节点,

image

此时的节点值为,

image

设置 current 指针指向索引为3的节点,

image

插入节点

在索引1后面插入“big”节点。先将 current 指针指向索引为1的节点,创建一个"big"新节点,

image

插入到 current 指向位置,

image

删除节点

将“big”节点删除,移动当前指针 current 到“but”节点位置,

image

执行删除操作,断掉“big”节点与前后两节点的 next 和 prev 指针,然后将“the”节点与“monster”节点关联起来,

image

image

双向循环链表

前面的双向链表的 head 节点和链尾没有连接关系,所以如果要访问最后一个节点的话需要从头开始遍历,直到最后一个节点。在双向链表基础上改进一下,把 header 节点的 prev 指针指向最后一个节点,而最后一个节点的 next 指针指向 header 节点,于是便构成双向循环链表。

image

-------------推荐阅读------------

我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、mysql协议、chatbot)

为什么写《Tomcat内核设计剖析》

我的2017文章汇总——机器学习篇

我的2017文章汇总——Java及中间件

我的2017文章汇总——深度学习篇

我的2017文章汇总——JDK源码篇

我的2017文章汇总——自然语言处理篇

我的2017文章汇总——Java并发篇


跟我交流,向我提问:

欢迎关注: