How to Create a Circular LinkedList

Question

I know how to create the Link and LinearLinkedList classes, but I just cannot for the life of me figure out how to modify them into a creating circularlinkedlist.

I have already read the answer to this question. However, I do not understand how if the head is None, then how can a None-type object have a next attribute? I just can't seem to grasp the concept.

If someone could show me the __init__ function of a sample CircularLinkedList and a simple explanation as to how it works, I think I would be able to comprehend it.

Thanks for any and all help

Edit: I only need the list to be traversed forwards. If that is the case, will the logic behind it need to be drastically changed?

Answer 1

Often in a circular linked list, you have a special link that doesn't contain meaningful data. Instead, it's a "sentinel" letting you know where the beginning (and end) of the list is. This link will exist even when the list is empty, so your algorithms will work on all lists, without lots of special cases needing special code.

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