Как создать круговой LinkedList

Question

Я знаю, как создавать классы Link и LinearLinkedList, но я просто не могу для жизни понять, как их модифицировать в создаваемый круглосуточный список. Я уже прочитал ответ на этот вопрос: Help with Circular Linked List in Python. Тем не менее, я не понимаю, как если голова равна None, то как может объект None-type иметь следующий атрибут? Я просто не могу понять концепцию. Если кто-то может показать мне init функции образца CircularLinkedList и простое объяснение того, как это работает, я думаю, что смогу его понять. Спасибо за любую помощь

Редактировать: Мне нужен только список, который нужно переместить вперед. Если это так, изменится ли его логика?

Answer 1

Часто в круговом связанном списке имеется специальная ссылка, которая не содержит значимых данных. Вместо этого это «дозор», дающий вам знать, где начинается (и заканчивается) список. Эта ссылка будет существовать, даже если список пуст, поэтому ваши алгоритмы будут работать во всех списках без особых случаев, требующих специального кода.

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

Важным шагом здесь является то, что голова не None. Только данные узла головы Link составляют None, и он указывает на себя через свой атрибут next. Как уже упоминалось в ответе, который вы связали, это выглядит примерно так:

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

Answer 3

Действительно; если нет узлов, то есть не может быть следующей/предыдущей указатели:

root 
| 
v 
None 

Если есть один узел, он связывает назад и вперед к себе:

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

Если есть два узла:

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