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

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
606
文章
12
评论
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值,和双向链表没有很大区别。

历史上的今天
二月
14
马谦马谦马谦
  • 本文由 发表于 2020年2月14日16:53:58
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/doubly-circular-linked-list.html
redis源码分析:链表实现 Redis

redis源码分析:链表实现

一、链表定义 链表在redis中的使用十分广泛,例如列表的底层实现之一就是链表,包括发布、订阅等等功能都是有用到链表的。redis中链表在adlist.h和adlist.c中实现,只用了300+行代码...
匿名

发表评论

匿名网友 填写信息

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