Python3数据结构03 - 双向链表
Synopsis: 前两篇介绍了顺序表和链表中的单链表，本文将介绍链表的另一种实现：双向链表，它的每个节点和两个指针域，分别指向前驱节点和后继节点。从双向链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点
代码已上传到 https://github.com/wangy8961/python3-algorithms ，欢迎star
1. 双向链表
双向链表（Doubly linked list），又称为双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点。一般我们都构造双向循环链表
2. Python实现
接下来我们使用Python 3来构建双向链表数据结构，首先需要定义一个节点类：
class Node: '''双向链表的节点''' def __init__(self, value): self.value = value # 节点的信息域 self.prev = None # 指针域，指向前驱节点 self.next = None # 指针域，指向后继节点 def __repr__(self): return 'Node({!r})'.format(self.value)
然后定义双向链表类：
class DoublyLinkedList: def __init__(self, node=None): '''创建一个双向链表对象时，如果不传入头节点，则创建空链表''' self.__head = node
2.1 判断是否空链表
只需要判断单链表的__head属性是否为None即可，如果是None表示没有头节点，则是空链表
2.2 求链表的长度
定义一个游标cur，用来表示遍历到的当前节点，初始时等于链表的头节点（即cur = self.__head）。count变量用于统计已遍历了多少个节点，初始时等于0。当cur移动到尾节点时，cur.next == None，此时再将cur往后移动时，需要退出while循环
该方法最后返回count即可
def length(self): '''求链表的长度''' cur = self.__head # 游标，用来表示当前节点 count = 0 # 用来统计已遍历的节点数目 # 1. 如果是空链表，self.__head为None，则cur为None，不会进入循环体，最后返回 count = 0，符合 # 2. 如果不是空链表，当cur移动到尾节点时，cur.next 是None，循环体中的 cur = cur.next 会让 cur = None，继续往后移动时会退出循环 while cur is not None: count += 1 cur = cur.next # 向后移动游标 return count
2.3 遍历链表
逻辑跟求长度一样，注意，这里使用生成器语法，将每个节点的值产出供客户代码使用
分享
相关推荐
作者
发表评论
专题系列
0 条评论
评论者的用户名
评论时间暂时还没有评论.