如何创建循环LinkedList

Question

我知道如何创建Link和LinearLinkedList类,但我不能为我的生活弄清楚如何将它们修改为创建循环链接列表.我已经阅读了这个问题的答案:帮助Python中的循环链接列表.但是,我不明白如果头是None,那么None-type对象如何具有"next"属性？我似乎无法掌握这个概念.如果有人可以向我展示示例CircularLinkedList 的init函数以及关于它如何工作的简单解释,我想我能够理解它.感谢您的帮助

编辑:我只需要向前遍历列表.如果是这样的话,它背后的逻辑是否需要彻底改变？

Answer 1

通常在循环链表中,您有一个不包含有意义数据的特殊链接.相反,它是一个"哨兵",让你知道列表的开头(和结束)在哪里.即使列表为空,此链接也将存在,因此您的算法将适用于所有列表,而不需要特殊代码的特殊情况.

class Link:
    def __init__(self, data, next):
        self.data = data
        self.next = next

class CircularLinkedList:
    def __init__(self):
        self.head = Link(None, None) # this is the sentinel node!
        self.head.next = self.head   # link it to itself

    def add(self, data):             # no special case code needed for an empty list
        self.head.next = Link(data, self.head.next)

    def __contains__(self, data):    # example algorithm, implements the "in" operator
        current = self.head.next
        while current != self.head:
            if current.data == data: # element found
                return True
            current = current.next
        return False