Python中的双向链表

Question

原来是由于超过了时间限制而出现了错误，但我已经引发了StopIteration异常...

我认为在迭代部分做错了什么，但很难找到错误。测试输出一直在运行，甚至打印出了None值。这是怎么回事？

class LinkedListIterator:
    def __init__(self, head):
        self.__current = head.get_next()

    def __iter__(self):
        return self

    def __next__(self):
        if self.__current == None:
            raise StopIteration
        else:
            item = self.__current.get_data()
            self.__current = self.__current.get_next()
            return item

这是我用来运行程序的输入:

my_list = LinkedListDLL()
my_list.add_to_head(1)
print("Contents:", end=" ")
for node in my_list:
    print(node, end=" ")
print()

- Wan

---

你的节点类是如何定义的？ - blhsing

请更新您的问题，附上 NodeDLL 类的类定义，以便正确缩进。 - blhsing

你能像你为 LinkedListIterator 所做的那样，将你的代码复制粘贴为文本吗？这样我们就可以轻松地运行并自己尝试它，而不是将其作为图片发布。 - blhsing

抱歉，我的第一次使用这个网站，出了点小问题。 - Wan

没问题。你能提供导致该错误的输入吗？ - blhsing

Answer 1

这段代码旨在在到达列表头部时停止迭代。

    if self.__current == None:
        raise StopIteration

然而，您使用一个与None不同的NodeDLL对象来表示头部。您可以保留对头部的引用并根据此引用进行检查。

class LinkedListIterator:
    def __init__(self, head):
        self._head = head
        self._current = head.get_next()

    def __iter__(self):
        return self

    def __next__(self):
        if self._current is self._head:
            raise StopIteration
        else:
            item = self._current.get_data()
            self._current = self._current.get_next()
            return item

- Janne Karila

Answer 2

你想要实现的是一个使用双向链表实现的MutableSequence API。

在Python中，你应该依赖于collections.abc，它可以指导你完成所有必需方法的实现。

例如，一个链表实际上是从MutableSequence继承的类。

from collections.abc import MutableSequence

class LinkedList(MutableSequence):
    pass

ll = LinkedList()

在实例化一个含有尚未编写的抽象方法的类时，你会收到一个 TypeError，它将指导你需要实现哪些方法。

TypeError: Can't instantiate abstract class LinkedList with abstract methods __delitem__, __getitem__, __len__, __setitem__, insert

特别注意，list 或 linked-list 不是一个迭代器，它是一个可迭代对象。这意味着 __iter__ 方法不应该返回 self 并依赖于 __next__，而是应该返回基于链接列表内容的全新迭代器。

换句话说，你只能通过迭代器遍历一次，但可以通过可迭代对象多次遍历。

完整实现

事实证明，我有一个按照这种方式实现的双向链接列表的完整实现。你可以看一下。

from collections.abc import MutableSequence

class LinkedList(MutableSequence):
    class _Node:
        def __init__(self, value, _next=None, _last=None):
            self.value, self._next, self._last = value, _next, _last

        def __str__(self):
            return f'Node({self.value})'

    def __init__(self, iterable=()):
        self.start = None
        self.last = None

        empty = object()
        iterable = iter(iterable)
        first = next(iterable, empty)

        if first is empty:
            return

        current = self._Node(first)
        self.start, self.last = current, current

        for value in iterable:
            new_node = self._Node(value, _last=self.last)
            self.last._next = new_node
            self.last = new_node


    def __len__(self):
        if self.start is None:
            return 0
        else:
            return sum(1 for _ in self)

    def __iter_nodes(self):
        current = self.start

        while current is not None:
            yield current
            current = current._next

    def __reversed_iter_nodes(self):
        current = self.last

        while current is not None:
            yield current
            current = current._last

    def __iter__(self):
        for node in self.__iter_nodes():
            yield node.value

    def __reversed__(self):
        for node in self.__reversed_iter_nodes():
            yield node.value

    def __get_node(self, index):
        if index >= 0:
            for item in self.__iter_nodes():
                if index == 0:
                    return item
                index -= 1
        else:
            for item in self.__reversed_iter_nodes():
                if index == 0:
                    return item
                index += 1
        raise IndexError

    def __getitem__(self, index):
        if index >= 0:
            for item in self:
                if index == 0:
                    return item.value
                index -= 1
        else:
            for item in reversed(self):
                if index == 0:
                    return item.value
                index += 1
        raise IndexError

    def __setitem__(self, key, value):
        self[key].value = value

    def __delitem__(self, key):
        node = self[key]
        if node._last:
            node._last._next = node._next
        if node._next:
            node._next._last = node._last

    def insert(self, index, value):
        if index > len(self):
            self.last = self._Node(value, _last=self.last)
        else:
            where = self.__get_node(index)
            _last = where._last
            new_node = self._Node(value, _next=where, _last=_last)
            if _last:
                _last._next = new_node
            else:
                self.start = new_node

            where._last = new_node

例子

ll = LinkedList(range(1, 5))
print(*ll)

print(*reversed(ll))

ll.insert(2, 'foo')
print(*ll)

输出

1 2 3 4
4 3 2 1
1 2 foo 3 4

- Olivier Melançon