Python 带尾单链表

Question

我有一个链表，我想将其实现为队列。我已经发现它有效，但我有一个关于为什么这个特定部分有效的问题。这是代码:

class LinkedQueue:
    class _Node:
        def __init__(self, element, next):
            self._element = element
            self._next = next

    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def enqueue(self, e):
        newest = self._Node(e, None)
        if self.is_empty():
            self._head = newest
        else:
            self._tail._next = newest
        self._tail = newest
        self._size += 1

如果队列为空并且我入队，则入队中的第一个条件为 true 并被触发，并将最新值分配给 self._head。但是，当我添加另一个元素时，会触发 else block ，并且 self._tail._next 被分配为最新的。显然，这改变了 _head 的 _next 变量。但是，当分配第三个元素时，_head 的 _next 变量不会更改。为什么会这样呢？另外，_tail 不应该被最新更改，因此 _next 变量会被新分配的 None 覆盖吗？

代码完全可以工作，并且我理解链表逻辑，但我不明白为什么这个特定代码可以工作。

Answer 1

你问:

self._tail._next is assigned newest. This, apparently, changes the _next variable for _head.

是的，因为当时_tail和_head是同一对象的两个名称。

所以当然分配给 _tail._next与分配给 _head._next 具有完全相同的效果会--怎么可能不，因为_tail和_head引用同一个对象？

让我们看看它们是如何引用同一个对象的!当 if分支执行，你做 self._head = newest ;然后无条件地在if/else之后你做self._tail = newest 。在 Python 中，赋值总是通过引用——赋值(对名称 [*])本身绝不会隐式地进行复制。

(对列表的切片进行赋值是一个非常不同的操作，因此出现了这个迂腐的括号 - 但现在让我们忘记它，因为您不处理对切片的赋值:-) .

However, when assigning a third element, the _next variable for _head is not changed. Why is this so?

因为到那时 _tail 就不再真实了。和_head是同一对象的两个名称:那么它们是不同对象的名称。

那是因为您第二次为 newest 分配了不同的内容 ( self._tail ) - 但没有为 self._head 分配任何新内容，因此仍然引用前一个对象...其中 _tail不再指代。

Also, shouldn't _tail be changed by newest, and as such the _next variable is overridden by the newly assigned None?

self._tail确实重新绑定(bind)(“更改”是一个非常模糊的术语!-)来引用与 newest 相同的对象，所以如果您打印 self._tail._next那时(在 enqueue 方法的最后)您确实会将其视为 None 。但是前一个分配给 self._tail._next影响 _next属性什么self._tail当时引用(self._tail=newest之前!)——对self._tail进行新分配的节点立即成为列表中的倒数第二个。