二重リンクリストをソートしました

Question

二重リンクリストの理解と実装に問題があります。私は、リンクされたリストの概念の大部分を理解することができます。これまでのコードは（Pythonで）

*これは単なる学問的な演習です。私は通常listとdictを使います。ラインprev_node = cur_nodeコールDoublyNode(element, cur_node, prev_node)に先行しているので

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 

にあなたのループを変更

前の要素へのリンクが2つしかありません。だから、Noneをnextパラメータとして渡すだけで、ループの次のパスで手動で初期化することもできます。これには、リストの最後の要素にNoneのままにするという利点があります。

1コンストラクタ内のパラメータとしてnextという名前を使用すると、イテレータを進める組み込み関数nextがシャドウされます。あなたは、標準的なことである名前next_を使用することができます。属性としてnextを使用することは、シャドウイングが発生しないように名前を修飾するため、問題ではありません。しかし、それはいくつかのシンタックスハイライトライターで混乱します。