排序雙鏈表Python

我無法理解和實現雙鏈表。我可以掌握鏈接列表的大部分概念。這是我的代碼到目前爲止（在Python中）排序雙鏈表Python

*這是一個純粹的學術活動。我通常會使用列表和字典。

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])

來源

2011-01-06 Dude

我想你最好先設置一個元素的鏈接列表，然後使用插入算法找到插入其他元素的正確位置。如果你想保持簡單，最初。 – 2011-01-06 02:38:00

你的問題是什麼？ – 2011-01-06 07:08:52

你的循環改爲

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作爲屬性不是問題，因爲它限定了名稱，因此不會出現陰影。儘管如此，它會在一些語法熒光筆中搞亂。

來源

2011-01-06 03:13:28 aaronasterling

排序雙鏈表Python

回答

相關問題