Geek Answers Handbook

How to create a circular LinkedList

I know how to create Link and LinearLinkedList classes, but I just can’t figure out for me how to change them in creating roundlinkedlist. I already read the answer to this question: Help with a circular list in Python . However, I do not understand how if the head is None, then how can a None-type object have the following attribute? I just can't understand the concept. If someone can show me the init function of the CircularLinkedList sample and a simple explanation of how this works, I think I can figure it out. Thanks for any help.

Edit: I only need a list that needs to be moved forward. If so, will its logical necessity change?

+5
source share
3 answers

Often in a circular linked list you have a special link that does not contain meaningful data. Instead, it is a “sentinel,” letting you know where the list starts (and ends). This link will exist even if the list is empty, so your algorithms will work in all lists without special cases requiring 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 return False
+5
source

Indeed, if there are no nodes, then the following / previous pointers cannot be:

 root | v None

If there is one node, it links back and forth to itself:

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

If there are two nodes:

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

The most important step here is that the head is not None . Only the data of the Link node head is None , and it points to itself through its next attribute. As mentioned in the answer you contacted, it looks something like this:

 def __init__(self): self.head = Link(None, None) self.head.next = self.head
0
source

More articles:


All Articles