链表如何在迭代中更快?与__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实现，或者在不使用任何类型的python内置数据结构(如列表或元组(的情况下，使用iter和next来最大限度地提高性能？如果有人能提出任何代码示例，我将不胜感激。

Answer 1

这会稍微高效一些，因为它去掉了一些变量赋值和比较。

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方法。一个方法的CCD_ 8就足够了。

Answer 2

定义__iter__：返回一个迭代器，该迭代器保留对当前节点的引用。然后它可以得到O(1)中的下一个节点。CCD_ 11遍历到CCD_ 12中被请求的节点。

Answer 3

定义__iter__方法：

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