我在理解和实现双重链接列表时遇到了困难。我能掌握链表的大部分概念。以下是我目前为止的代码(用Python编写)
*这是纯粹的学术练习。我通常使用list和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])
将循环改为
因为第
prev_node = cur_node
行在调用DoublyNode(element, cur_node, prev_node)
之前,所以您最终将上一个元素和下一个元素都设置为上一个元素,这样您就得到了一个只有两个指向上一个元素的链接的链表。所以您也可以只传递None
作为next
参数1,然后在下一次循环中手动初始化它。这样做的好处是在列表的最后一个元素上保留为None
。在1在构造函数中使用名称
next
作为参数将隐藏内置函数next
,该函数推进迭代器。您可以使用名称next_
,这是规范的做法。使用next
作为属性不是问题,因为这样可以限定名称,这样就不会出现阴影。不过,它会在一些语法高亮中出错。在相关问题 更多 >
编程相关推荐