我在理解和实现双向链表时遇到了困难。我可以掌握链表的大部分概念。到目前为止,这是我的代码(在 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])
最佳答案
将循环更改为
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
参数1 传递,然后在下一次循环时手动初始化它。这样做的好处是在列表的最后一个元素上将其保留为 None
。
1 在构造函数中使用名称 next
作为参数将隐藏内置函数 next
,它推进一个迭代器。您可以使用名称 next_
,这是规范的做法。使用 next
作为属性不是问题,因为它限定了名称,因此不会发生阴影。不过,它会在某些语法高亮器中出现困惑。
关于python - 排序双向链表 Python,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4611254/