collections.deque:一旦找到物品，如何有效地移除

Question

我们想在链表中找到一个项目，对该项目执行一些操作，然后将其删除。

from collections import deque
q = deque([(12, 'apples'), (32, 'oranges'), (42, 'pears'), (12, 'peaches')])
john_smith_id = 42
for customer in q:
    id, data = customer
    if id == john_smith_id:
        myfunction(data)  # do something with John Smith's data
        q.remove(customer)
        break

我的问题是关于线路q.remove(customer)。理想情况下应该是O(1)，因为我们已经在链表中找到了客户，但我担心它可能会遍历整个链表。

正确的方法是什么？

Answer 1

它正在重新遍历列表。

如果您想要一个具有这种功能的链表，请不要使用collections.deque。collections.deque是deque类型，而不是链表类型。它在引擎盖下使用了一个展开的链表，但并不支持所有可能的链表功能。按照展开的实现方式，它甚至不能支持您想要的操作-该实现使用64个元素块，并且不支持部分空的中间块，因此如果操作一直延伸到列表的一端，就无法从中间删除元素。

无论如何，对于您的数据结构来说，链表似乎不是一个很好的选择。这看起来更像是一份字典的工作。