Python3数据结构04 - 单向循环链表

  • 原创
  • Madman
  • /
  • /
  • 0
  • 1373 次阅读

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表示没有头节点,则是空链表

def is_empty(self):
    '''判断是否为空链表'''
    return self.__head is 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:
        yield cur.value  # 生成当前节点的值
        if cur.next == self.__head:
                                
                            
  • horsonzhu
  • hexiaominitao
  • dima1901065l
  • haoyu36
  • gitwangliang
  • xiyao
  • John
  • __
  • nnlxin
  • 十一
  • JacobHZ
  • luciferlg
未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构04 - 单向循环链表

分享

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答,请按如下方式联系我

0 条评论

暂时还没有评论.