排序的双链表Python [英] Sorted Doubly Linked List Python

问题描述

我在理解和实现双重链接列表时遇到了麻烦.我可以掌握链表的大多数概念.到目前为止，这是我的代码(在Python中)

I'm having trouble understanding and implementing a Doubly Linked List. I can grasp most of the concepts of a Linked List. Here is my code so far (in Python)

*这是纯粹的学术练习.我通常会使用列表和字典.

*This is a purely academic exercise. I would normally use list and 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])

推荐答案

将循环更改为

for element in sequence:
    prev_node = cur_node
    cur_node = DoublyNode(element, None, prev_node)
    prev_node.next = cur_node

由于在调用 DoublyNode(element，cur_node，prev_node)之前，行 prev_node = cur_node ，您最终将前一个元素和下一个元素都设置为上一个元素，因此您最终得到一个链表，该链表只有两个指向上一个元素的链接.因此，您也可以仅将 None 作为 next 参数 ¹ 传递，然后在循环的下一遍手动对其进行初始化.这样做的好处是，在列表的最后一个元素上将其保留为 None .

Because the line prev_node = cur_node precedes the call DoublyNode(element, cur_node, prev_node), you end up setting both the previous and next elements to the previous element so you are ending up with a linked list that just has two links to the previous element. So you might as well just pass None as the next parameter¹ and then initialize it manually on the next pass of the loop. This has the advantage of leaving it as None on the last element of the list.

1在构造函数中使用名称 next 作为参数将对内置函数 next 进行阴影化，该函数将推进迭代器.您可以使用名称 next _ 来规范.将 next 用作属性不是问题，因为这样可以限定名称，从而不会产生阴影.但是，它将在某些语法突出显示中混乱.

1 Using the name next as a parameter in the constructor will shadow the builtin function next which advances an iterator. You could use the name next_ which is the canonical thing to do. Using next as an attribute isn't a problem because that qualifies the name so that no shadowing will occur. It will mess up in some syntax highlighters though.

这篇关于排序的双链表Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！