python - 双向链接哨兵列表中的 __next__ 和 __iter__ 方法

Question

我现在正在研究一个双向链表类，我的 next 和 iter 方法遇到了麻烦。这是我类(class)的一个项目，我已经提交了该项目，现在只想了解如何实际修复它以使其有用。

我希望我的代码做的是设置一个当前指针，从 header 开始，然后继续前进，直到被指示终止或到达预告片。我想访问每个节点存储的值。节点类是主链表类的子类。这是我的代码。当我调用我的方法(发布我的附加方法)时，我的问题出现了；无法识别当前指针。关于如何解决这个问题有什么想法吗？

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']。这几乎就是我们希望看到的。我们现在需要做的就是跳过标题元素。我们只需从标题后面的元素开始即可做到这一点:

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

然后就可以了。

<小时/>

这就是让您的代码运行所需的全部内容。 但是，我通常建议不要采用这种方法。您将迭代状态存储在列表中，这是非常脆弱的。您确实应该尽可能将此状态设置为本地状态。

特别是，链表不需要同时是可枚举和枚举器。实现 __iter__ 执行前者，实现 __next__ 执行后者。可枚举的意思是“你可以迭代这个东西”，而枚举器是正在执行迭代并且具有迭代状态的东西。

尝试将迭代状态移出链表，使其仅可枚举而不是枚举器。为此，请添加一个 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完全)