Сортированный двойной связанный список Python

Question

У меня возникли проблемы с пониманием и реализацией Doubly Linked List. Я могу понять большинство концепций связанного списка. Вот мой код до сих пор (в Python)

* Это чисто академическое упражнение. Я бы обычно использовал список и dict.

class DoublyNode(object): 
    """A node of the SortedDoublyLL object. 

    DoublyNode(item, next=None, previous=None) -> a new DoublyNode with data as 
    its data, and next and previous as its neighbors.""" 

    def __init__(self, data, next = None, previous = None): 
     """Make a new DoublyNode from item, pointing to next and previous.""" 

     self.data = data 
     self.next = next 
     self.previous = previous 

class SortedDoublyLL(object): 
    """A Sorted Doubly Linked List. 

    SortedDoublyLL() -> new SortedDoublyLL list that is empty 
    SortedDoublyLL(sequence) -> a SortedDoublyLL initialized from sequence's 
    items. 

    """ 

    def __init__(self, sequence = []): 
     """Make a new SortedDoublyLL from the elements of sequence.""" 

     if len(sequence) == 0: 
      self.head = None 
      self.tail = None 
     else: 
      cur_node = None 
      prev_node = None 
      sequence.sort() 
      sequence.reverse() 
      for element in sequence: 
       prev_node = cur_node 
       cur_node = DoublyNode(element, cur_node, prev_node) 

      self.head = cur_node 
      self.tail = DoublyNode(sequence[0]) 

Answer 1

Изменить петлю на

for element in sequence: 
    prev_node = cur_node 
    cur_node = DoublyNode(element, None, prev_node) 
    prev_node.next = cur_node 

Поскольку линия prev_node = cur_node предшествует вызов DoublyNode(element, cur_node, prev_node), вы в конечном итоге установку как предыдущие и последующие элементов к предыдущему элементу, так что вы в конечном итоге с связанным списком который имеет только две ссылки на предыдущий элемент. Поэтому вы можете просто передать None как параметр next , а затем инициализировать его вручную на следующем проходе цикла. Это имеет то преимущество, что оставить его как None на последнем элементе списка.

1 Используя имя next в качестве параметра в конструкторе будет теневая встроенная функция next, которая продвигает итератор. Вы можете использовать имя next_, которое является канонической задачей. Использование next в качестве атрибута не является проблемой, потому что это квалифицирует имя так, чтобы не было затенения. Тем не менее, это испортит некоторые синтаксические выделения.