So erstellen Sie eine kreisförmige LinkedList

Question

Ich weiß, wie Sie die Link und LinearLinkedList-Klassen erstellen, aber ich kann nicht für das Leben von mir herauszufinden, wie Sie sie in eine Erstellung von Circularlinkedlist ändern. Ich habe die Antwort auf diese Frage bereits gelesen: Help with Circular Linked List in Python. Allerdings verstehe ich nicht, wie wenn der Kopf None ist, wie kann dann ein None-Typ-Objekt ein "next" -Attribut haben? Ich kann das Konzept einfach nicht begreifen. Wenn mir jemand die init Funktion eines Beispiels CircularLinkedList und eine einfache Erklärung, wie es funktioniert, zeigen könnte, würde ich in der Lage sein, es zu verstehen. Danke für jede Hilfe

Edit: Ich brauche nur die Liste nach vorne durchlaufen werden. Wenn dies der Fall ist, wird die Logik dahinter drastisch geändert werden müssen?

Answer 1

Oft in einer kreisförmigen verknüpften Liste haben Sie einen speziellen Link, der keine aussagekräftigen Daten enthält. Stattdessen ist es ein "Sentinel", der Sie darüber informiert, wo der Anfang (und das Ende) der Liste ist. Dieser Link wird auch dann existieren, wenn die Liste leer ist, so dass Ihre Algorithmen auf allen Listen funktionieren, ohne viele Spezialfälle, die speziellen Code benötigen.

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 

Answer 2

Der entscheidende Schritt hier ist, dass der Kopf nicht None ist. Nur die Daten des Knotens des Kopfes Link sind None, und er zeigt sich über sein next Attribut. Wie in der Antwort erwähnt, die Sie verbunden haben, würde das in etwa so aussehen:

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

Answer 3

In der Tat; Wenn es keine Knoten sind, dann kann es keine nächsten/vorherigen Zeiger sein:

root 
| 
v 
None 

Falls es ein Knoten ist, verbindet sie hin und her auf sich selbst:

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

Wenn es zwei Knoten: