next 和 iter 双向链表中的方法

Question

我现在正在处理一个双向链表 class，我运行在使用 next 和 iter 方法时遇到了麻烦。这是我的 class 的一个项目，我已经上交了，现在只想了解如何实际修复它以使其有用。

我想要我的代码做的是设置一个当前指针，从 header 开始，然后继续前进直到指示终止或到达预告片。我想访问存储在每个节点的值。节点class是主链表class的子class。这是我的代码。当我调用我的方法（发布我的追加方法）时，我的问题出现了；无法识别当前指针。关于如何解决此问题的任何想法？

class Linked_List:

    class __Node:
        def __init__(self, val):
          self.val = val
          self.size = 0

    def __init__(self):
        self.header = Linked_List.__Node('header')
        self.trailer = Linked_List.__Node('trailer')
        self.header.next = self.trailer
        self.trailer.prev = self.header
        self.size = 0
        self.current = self.header
        self.current.next = self.trailer

    def __iter__(self):
        self.current = self.header
        return self


    def __next__(self):
        if self.current == self.trailer:
            raise StopIteration
        result = self.Linked_List.__Node[self.current]
        self.current = self.current.next
        return result

    def append(self, val):
        new_node = Linked_List.__Node(val)

        if self.header.next is self.trailer:
            self.header.next = new_node
            self.trailer.prev = new_node
            self.current = self.header
        else:
            while self.current is not self.trailer:
                self.current = self.current.next
            self.current.next = new_node
            new_node.next = self.trailer
            new_node.prev = self.current
        self.size += 1

我是 python（和一般编码）的新手，所以任何建议都会很棒。

Answer 1

您的代码有多个问题，这些问题在您尝试使用它时会变得很明显。让我们假设下面的代码来测试它：

l = Linked_List()
l.append('foo')
l.append('bar')
l.append('baz')

print([x.val for x in l])

AttributeError: '__Node' object has no attribute 'next'

第一个问题：您的 __Node 类型没有 next 和 prev 的字段：

class __Node:
    def __init__(self, val):
      self.val = val
      self.size = 0
      self.prev = None
      self.next = None

AttributeError: 'NoneType' object has no attribute 'next'

第二个问题：next 并不总是为附加节点填充。在append中的一个路径中，您没有设置新节点的next和prev：

def append(self, val):
    new_node = Linked_List.__Node(val)

    if self.header.next is self.trailer:
        # set the attributes on new_node
        new_node.prev = self.header
        new_node.next = self.trailer

        self.header.next = new_node
        self.trailer.prev = new_node
        self.current = self.header
    # …

AttributeError: 'Linked_List' object has no attribute 'Linked_List'

第三个问题：不知道您在 __next__ 中试图做什么。您应该直接访问 self.current 那里：

def __next__(self):
    if self.current == self.trailer:
        raise StopIteration
    result = self.current
    self.current = self.current.next
    return result

一旦我们修复了所有这些问题，我们就有了一个可以成功运行的代码。但是我们只得到如下输出：['header', 'foo']。当然，这不是我们想要的。

发生这种情况的原因是因为项目的实际顺序如下：

header
foo
trailer
baz
trailer

（是的，有一个递归）很显然，append 毕竟没有正常工作。如果您只追加两个元素，您可以看到该元素被添加到尾部元素之后。这意味着 self.current 确实命中了附加循环中的尾部元素：

while self.current is not self.trailer:
    self.current = self.current.next

如果你看一下，发生这种情况是有道理的：首先更新 self.current，然后进行检查以最终取消循环。那时self.current就是self.trailer。所以我们应该检查 self.current.next 而不是：

while self.current.next is not self.trailer:
    self.current = self.current.next

修复后，我们将得到以下输出：['header', 'foo', 'bar', 'baz']。这几乎就是我们希望看到的。我们现在需要做的就是也跳过 header 元素。我们通过简单地从 header:

之后的元素开始来做到这一点

def __iter__(self):
    self.current = self.header.next
    return self

然后就可以了。

这就是获取代码所需的一切运行。但是，我通常会反对这种方法。您将迭代状态存储在列表中，这是非常脆弱的。你真的应该尽可能地让这个州成为本地人。

特别是，链表不需要既是可枚举又是枚举器。实施 __iter__ 是前者，实施 __next__ 是后者。 Enumerable 的意思是“你可以迭代这个东西”，而枚举器是执行迭代并具有迭代状态的东西。

尝试将迭代状态从移到链表中，使其仅可枚举而不是枚举器。为此，请添加一个 LinkedListEnumerator 类型，该类型引用您的列表并跟踪当前元素：

class LinkedListEnumerator:
    def __init__ (self, lst):
        self.lst = lst
        self.current = lst.header.next

    def __iter__ (self):
        return self

    def __next__ (self):
        if self.current == self.lst.trailer:
            raise StopIteration
        result = self.current
        self.current = self.current.next
        return result

然后您可以删除链表中的 __next__ 方法，并用以下内容替换 __iter__ 方法：

def __iter__(self):
    return LinkedListEnumerator(self)

然后你的链表中就没有状态了。（此时，你也应该在append中使current成为local变量，并完全摆脱self.current）

next 和 iter 双向链表中的方法

next and iter methods in doubly linked sentinel list

python

python-3.x

doubly-linked-list

__next__ 和 __iter__ 双向链表中的方法

__next__ and __iter__ methods in doubly linked sentinel list

python

python-3.x

doubly-linked-list

next 和 iter 双向链表中的方法

next and iter methods in doubly linked sentinel list