数据结构之链表(二):双向循环链表

马谦马谦马谦 2020年2月14日16:53:58 发表评论

本篇文章是基于前篇《数据结构之链表(一):单向链表》实现的,和单向链表重复的细节不再描述。

一、双向链表

双向链表和单向链表类似,唯一的区别是链表节点中除了有指向下一个节点的指针以外,还有一个指向上一个节点的指针。

数据结构之链表(二):双向循环链表

节点的定义:

数据结构之链表(二):双向循环链表

链表的定义:

二、插入操作

双链表的插入操作和单链表基本没有差别,就只是多了一个修改prev节点的步骤。

以下是添加节点node2的过程:

数据结构之链表(二):双向循环链表

操作主要有两步:

  1. 修改node2的prev和next指向,分别指向前后节点。
  2. 修改前节点node1的next指针指向node2,修改后节点node2的prev指针指向node2。

插入函数实现:

实现了这个函数之后,单链表中所有的头插、尾插函数都不用修改了,直接调用这个函数就完成了。

其实后面的删除元素也是一样,前面所说的把添加和删除逻辑抽离出来的好处就在这里。

三、删除操作

删除node2节点的操作步骤:

数据结构之链表(二):双向循环链表

过程描述:

  1. 删除node2的prev和next指针指向。
  2. 修改node1的next指针指向node3,修改node3的prev指针指向node1。

删除代码实现:

四、双向循环链表

双向循环链表是在双向链表的基础上增加了循环机制,即链表的尾结点要连接上首节点,链表的首节点要连接上尾结点。循环链表的示意图:

数据结构之链表(二):双向循环链表

《算法导论》中实现双向循环链表的方法是引入一个哨兵节点,这个节点不包含任何数据信息,只作为首尾相连的用途:

数据结构之链表(二):双向循环链表

实际上也就是一个NULL值,和双向链表没有很大区别。

本文共执行62次查询,耗时0.334秒!
历史上的今天
二月
14
马谦马谦马谦

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: