How to Create a Circular LinkedList

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

Indeed; if there are no nodes, then there can be no next/previous pointers:

root
 |
 v
None

If there is one node, it links backwards and forwards to itself:

    root
     |
     v
+-> Node <-+
|   next---+
+---prev

If there are two nodes:

      root
       |
       v
  +-> Node   +-> Node <--+
  |   next---+   next--+ |
+-|---prev <-----prev  | |
| +--------------------+ |
+------------------------+