链表如何在迭代中更快？使用 iter 和 next 还是使用 getitem？

Question

我基本上是在尝试使用以下链表来模拟 python 列表的一些特征：

class List:

    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def append(self, value):
        node = Node(value)
        if not self.head:
            self.head = self.tail = node
        else:
            tail = self.tail
            tail.next = node
            self.tail = node
        self.length += 1

    def __len__(self):
        return self.length

    def __getitem__(self, i):
        if i >= len(self):
            raise IndexError("Index out of range.")
        elif i < len(self):
            index = 0
            current = self.head
            while index <= i:
                if index == i:
                    return current
                current = current.next
                index += 1

    def __contains__(self, value):
        for node in self:
            if value == node.value:
                return True
        return False

class Node:

    def __init__(self, value, n=None):
        self.next = n
        self.value = value

所以我需要使这个链表尽可能高效，特别是在遍历它的一个大实例时。有什么方法可以改进我的 getitem 实现或替代使用 iter 和 next 来最大化性能不使用任何一种python的内置数据结构，例如列表或元组？如果有人能想出任何代码示例，我将不胜感激。

Answer 1

定义__iter__: return 一个保持对当前节点的引用的迭代器。然后它可以得到O(1)中的下一个节点。 __getitem__遍历到O(n)中请求的节点。

Answer 2

这会稍微更有效率，因为它摆脱了一些变量赋值和比较。

def __getitem__(self, i):
    if i >= len(self):
        raise IndexError("Index out of range.")

    current = self.head
    for _ in xrange(i):
        current = current.next

    return current

但是，链表上的随机访问总是至少 O(n)。如果您不是在寻找随机访问而是纯粹的迭代，__iter__ 是可行的方法，因为使用 __len__ 和 __getitem__ 的组合进行迭代将是 O(n^2)，这是太可怕了。你可以这样做：

def __iter__(self):
    current = self.head

    while current:
        yield current
        current = current.next

您不必提供任何 __next__ 或 next 方法。 yield从一个方法中调用就足够了。

Answer 3

定义一个__iter__方法：

def __iter__(self):
    current = self.head
    while current:
        yield current
        current = current.next

链表如何在迭代中更快？使用 iter 和 next 还是使用 getitem？

How would a linked list be faster in iteration? with iter and next or with getitem?

python

performance

linked-list

链表如何在迭代中更快？使用 __iter__ 和 __next__ 还是使用 __getitem__？

How would a linked list be faster in iteration? with __iter__ and __next__ or with __getitem__?

python

performance

linked-list

链表如何在迭代中更快？使用 iter 和 next 还是使用 getitem？

How would a linked list be faster in iteration? with iter and next or with getitem?