排序双链表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

回答

相关问题