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

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


双向链表

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

双链表特点

  • 创建双链表时无需指定链表的长度。
  • 比起单链表,双链表需要多一个指针用于指向前驱节点,所以需要存储空间比单链表多一点。
  • 双链表的插入和删除需要同时维护 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

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 看图轻松理解数据结构与算法系列(双向链表)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏