排序的双向链表 Python

Question

我在理解和实现双向链表时遇到了困难。我对链表的大部分概念都能理解。以下是我目前的代码（用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])

Answer 1

把你的循环改成这样：

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 参数传进去¹，然后在循环的下一次手动初始化它。这样做的好处是，链表最后一个元素的 next 可以保持为 None。

1 在构造函数中使用 next 作为参数名会遮蔽掉内置的 next 函数，这个函数是用来推进迭代器的。你可以使用 next_ 这个名字，这样是比较标准的做法。把 next 作为属性名使用没有问题，因为这样可以避免遮蔽。不过在某些语法高亮工具中可能会出现问题。