python - 链表总是比 python 列表慢吗？

Question

我正在研究使用算法和数据结构解决问题并遇到这个问题:设计并实现一个实验，将 Python 列表的性能与作为链表实现的列表进行比较。

下面是我的链表实现。

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next = None

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

    def set_data(self, new_data):
        self.data = new_data

    def set_next(self, new_next):
        self.next = new_next


class UnOrderedList(object):
    def __init__(self):
        self.N = 0
        self.head = None

    def size(self):
        return self.N

    def is_empty(self):
        return self.N == 0

    def add(self, data):
        self.N += 1
        temp = Node(data)
        temp.set_next(self.head)
        self.head = temp

    def search(self, data):
        current = self.head
        found = False
        while current and not found:
            if current.get_data() == data:
                found = True
            current = current.get_next()
        return found

    def remove(self, item):
        current = self.head
        previous = None
        while current.get_data() != item:
            previous = current
            current = current.get_next()
        if not previous:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())
        self.N -= 1

测试删除方法:

for i in range(1000, 100000001, 100000):
    list1 = list(range(i))
    list2 = UnOrderedList()
    for a in range(i):
        list2.add(a)

    a = random.randrange(0, i)

    start_time1 = time.time()
    list1.remove(a)
    end_time1 = time.time()

    start_time2 = time.time()
    list2.remove(a)
    end_time2 = time.time()

    print("List time: {0}. Linked List time: {1}".format(end_time1-start_time1, end_time2-start_time2))

对于我的测试，我用 python 列表的类似方法测试链表的方法，并且链表总是很短。所以我在互联网上阅读了一些内容，发现虽然 python 列表在索引/搜索方面更好，但链表应该在添加或删除方面胜过它。

所以我的问题又是，链表总是比列表慢还是我做错了什么？

Answer 1

其他答案跳过了一个非常重要的细节，只有当指向要删除的节点的指针作为参数而不是节点的值提供时，链表才会在 remove() 方法中优于数组。

否则，您将不得不搜索整个列表，这与从基于索引的列表中删除元素具有相同的 O(n) 复杂度。

但这里还有另一个不太重要的因素在起作用。 Python 列表实际上是用 C 实现的。一个纯 Python 程序不太可能打败 C 对应程序，特别是当它由专家编写和优化多年时。