Come creare una lista di contatti circolare

Question

So come creare le classi Link e LinearLinkedList, ma non riesco proprio a capire come modificarli in una lista circolare creata. Ho già letto la risposta a questa domanda: Help with Circular Linked List in Python. Tuttavia, non capisco come se la testa sia None, allora come può un oggetto di tipo None avere un attributo "next"? Non riesco proprio ad afferrare il concetto. Se qualcuno può indicarmi la funzione init di un esempio CircularLinkedList e una semplice spiegazione su come funziona, penso che sarei in grado di comprenderlo. Grazie per qualsiasi aiuto

Modifica: Ho solo bisogno dell'elenco per essere inoltrato. Se questo è il caso, la logica dietro di esso deve essere drasticamente cambiata?

Answer 1

Spesso in un elenco circolare collegato, si dispone di un collegamento speciale che non contiene dati significativi. Invece, è una "sentinella" che ti permette di sapere dov'è l'inizio (e la fine) della lista. Questo link esiste anche quando la lista è vuota, quindi i tuoi algoritmi funzioneranno su tutti gli elenchi, senza molti casi speciali che necessitano di codice speciale.

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

Il passaggio cruciale è che la testina non è None. Solo i dati del nodo Link della testata sono None e puntano su se stesso tramite l'attributo next. Come menzionato nella risposta a cui ci si collegava, sarebbe simile al seguente:

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

Answer 3

Infatti; se non ci sono i nodi, quindi non ci può essere nessun prossimi puntatori precedenti /:

root 
| 
v 
None 

Se c'è un nodo, collega avanti e indietro a se stessa:

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

Se ci sono due nodi:

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