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

  • 原创
  • Madman
  • /
  • 2018-09-05 14:16
  • /
  • 0
  • 142 次阅读

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:  # 遍历到尾节点时,cur.next == self.__head,需要退出循环
            break
        cur = cur.next  # 向后移动游标

2.4 在尾部添加元素

关键还是如何找到尾节点,最后不要忘记将新增节点的next指向头节点

def append(self, value):
    '''在链表的尾部添加节点。注意:传入的 value 是节点的值'''
    node = Node(value)

    if self.is_empty():  # 如果是空链表
        self.__head = node
        node.next = node
    else:
        cur = self.__head  # 游标,用来表示当前节点
        # 遍历链表,直到找到了尾节点后,退出循环
        while cur.next != self.__head:
            cur = cur.next
        # 此时,cur 表示尾节点
        cur.next = node  # 将它的 next 指向新增节点
        node.next = self.__head  # 再将新增节点的 next 指向头节点

2.5 在头部插入元素

由于新增节点会变成新的头节点,所以需要修改尾节点的next指向

def head_add(self, value):
    '''在链表的头部添加节点,注意:尾节点的 next 要指向新增节点,因为头节点变了'''
    node = Node(value)

    if self.is_empty():  # 如果是空链表
        self.__head = node
        node.next = node
    else:
        # 先遍历链表,找到尾节点
        cur = self.__head  # 游标,用来表示当前节点
        while cur.next != self.__head:  # 退出while循环后,cur指向尾节点
            cur = cur.next

        node.next = self.__head  # 将新增节点的 next 指向原来的头节点
        self.__head = node  # 再将链表的 __head 属性指向新增节点
        cur.next = node  # 最后,将尾节点的 next 指向新的头节点(新增节点)

2.6 在指定位置插入元素

该方法需要传入下标pos和元素的值,为了跟列表等一样,这里规定pos从0开始计数,即头节点的pos为0

在指定位置pos插入元素,我们只需要找到pos - 1所在位置的节点,这里用pre游标来表示它。然后让新添加的节点的next指向pre.next,再让pre.next指向新添加的节点即可,注意,这里和在头部插入元素一样,顺序不能倒置

def insert(self, pos, value):
    '''在指定位置添加节点。 pos 表示节点的下标,为了跟列表等一样,这里规定 pos 从0开始计数,即头节点的 pos 为0'''
    if pos <= 0:  # 暂时不支持负数的下标。如果传入负数或者0,统一在头部插入
        self.head_add(value)
    elif pos > self.length() - 1:  # 如果传入的下标大于链表的长度减去1,默认使用在尾部插入
        self.append(value)
    else:
        pre = self.__head  # 游标,用来表示 pos - 1 位置的节点
        count = 0
        while count < pos - 1:  # 当count = pos - 1时,表示已经找到了 pos - 1 的节点,退出循环
            count += 1
            pre = pre.next  # 向后移动游标
        # 退出循环后,pre 指向 pos - 1 所在的节点
        node = Node(value)
        node.next = pre.next  # 将新增节点的 next 指向 pre 的下一节点
        pre.next = node  # 再将 pre 的 next 重新指向新增的节点即可

2.7 查看元素是否在链表中

逻辑跟遍历链表类似,只有cur表示的当前节点不是尾节点时,才向后移动游标

def search(self, value):
    '''查找指定的元素值是否在链表中,也适合空链表的情况'''
    if self.is_empty():  # 如果是空链表
        return False

    cur = self.__head
    while True:
        # 如果找到值,直接返回
        if cur.value == value:
            return True
        # 如果没找到值,需要先判断是不是尾节点
        if cur.next == self.__head:
            return False  # 如果是尾节点,直接返回
        else:
            cur = cur.next

2.8 在链表中删除指定元素值

跟单链表一样,使用cur游标指示遍历过程中的当前节点,使用pre游标来指示遍历过程中的前驱节点。需要注意要删除的元素是不是头节点或尾节点

def remove(self, value):
    '''在链表中删除指定元素值,跟列表中的 remove() 类似,也是删除第一个遇到的元素'''
    pre = None
    cur = self.__head

    while True:
        # 如果找到值
        if cur.value == value:
            if cur == self.__head:  # 如果是头节点
                if cur.next == self.__head:  # 如果链表只有一个节点,即它不仅是头节点,也是尾节点
                    self.__head = None  # 则变成空链表
                    break
                else:
                    # 注意:由于要修改尾节点的 next 指向,所以需要先找到尾节点
                    tail = self.__head
                    while tail.next != self.__head:  # 退出while循环后,tail指向尾节点
                        tail = tail.next
                    self.__head = cur.next  # 1. 指向新的头节点
                    tail.next = self.__head  # 2. 尾节点的 next 指向新的头节点
            else:  # 如果是 中间节点 或 尾节点
                pre.next = cur.next

        # 如果没找到值,需要先判断是不是尾节点
        if cur.next == self.__head:  # 如果已经遍历到尾节点了
            break
        else:
            pre = cur  # 先让 pre 指向当前节点
            cur = cur.next  # 再让 cur 向后移动

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构04 - 单向循环链表

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录