Python3数据结构04 - 单向循环链表
Synopsis: 链表结构的实现中还有一种循环链表的形式，它的尾节点不指向空，而是指向头节点，形成一个循环，本文将介绍单链表的循环链表形式
代码已上传到 https://github.com/wangy8961/python3-algorithms ，欢迎star
1. 单向循环链表
单链表的一个变形是单向循环链表（Singly circular linked list），链表中最后一个节点的next指针域不再为None，而是指向链表的头节点
2. Python实现
接下来我们使用Python 3来构建单向循环链表数据结构，首先需要定义一个节点类：
class Node: '''单向循环链表的节点''' def __init__(self, value): self.value = value # 节点的信息域 self.next = None # 节点的指针域 def __repr__(self): return 'Node({!r})'.format(self.value)
然后定义单向循环链表类：
class SinglyCircularLinkedList: def __init__(self, node=None): '''创建一个单向循环链表对象时，如果不传入头节点，则创建空链表''' self.__head = node if node: node.next = node # 如果创建非空链表，它的 next 要指向头节点，即指向它自身
2.1 判断是否空链表
只需要判断单链表的__head属性是否为None即可，如果是None表示没有头节点，则是空链表
2.2 求链表的长度
定义一个游标cur，用来表示遍历到的当前节点，初始时等于链表的头节点（即cur = self.__head）。count变量用于统计已遍历了多少个节点，初始时等于0。当cur移动到尾节点时，cur.next == self.__head，此时需要退出while循环
该方法最后返回count即可
def length(self): '''求链表的长度''' if self.is_empty(): return 0 # 空链表直接返回0 cur = self.__head # 游标，用来表示当前节点 count = 0 # 用来统计已遍历的节点数目 while True: count += 1 if cur.next == self.__head: # 遍历到尾节点时，cur.next == self.__head，需要退出循环 break cur = cur.next # 向后移动游标 return count
2.3 遍历链表
逻辑跟求长度一样，注意，这里使用生成器语法，将每个节点的值产出供客户代码使用
def travel(self): '''遍历整个链表''' if self.is_empty(): return cur = self.__head # 游标，用来表示当前节点 while True
未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构04 - 单向循环链表
分享
相关推荐
作者
发表评论
专题系列
热门文章
0 条评论
评论者的用户名
评论时间暂时还没有评论.