Python 3中类Perl/Ruby数组shift操作的复杂度及O(1)实现方法

Python原生列表的pop(0)操作，时间复杂度是严格O(n)，不存在O(1)的可能。
原因很直接：Python列表是基于连续内存的动态数组实现，删掉头部元素后，必须把剩下的n-1个元素全部往前挪一个位置，才能维持数组的连续存储结构，整体开销随列表长度线性增长。网上的O(1)误判，基本都是把不带参数的pop()（即弹出列表最后一个元素，均摊O(1)）和pop(0)搞混了。

按照需求，只需要平均O(1)、不要求严格最坏情况的话，有两个很实用的实现方式：

直接用标准库的collections.deque #

这是最省事的选择：

• deque是Python内置的双端队列，底层用分块链表存储，从头部弹元素的操作（popleft()）平均时间复杂度就是O(1)，功能和Perl、Ruby里的shift完全对应。
• 标准库的实现经过长期优化，头尾插入、弹出的开销非常低，专门解决这类需要频繁操作列表两端的场景。
• 唯一需要注意的是，deque按索引随机访问的性能比原生列表差，如果你的业务有大量按下标取元素的需求，这个方案会不太适配。

基于原生列表做惰性偏移实现 #

如果要保留列表连续存储、随机访问O(1)的特性，可以靠偏移索引减少元素移动次数，同样能达到平均O(1)的复杂度：

• 内部用原生列表存元素，额外维护一个整数head_offset，记录当前队列的有效起始位置，不用每次做shift都移动列表元素。
• 执行shift的时候，直接读取head_offset位置的元素，把head_offset加1就算完成，单次操作完全不需要移动内存。
• 当无效的头部元素积累到一半的比例时，再一次性把有效元素切片成新列表覆盖原列表，把head_offset重置。这种方式下，每个元素最多只会被移动一次，平摊到所有shift操作上的平均成本就是O(1)。
• 最简代码实现参考：

class ShiftableList:
    def __init__(self, initial_data=None):
        self._items = list(initial_data) if initial_data else []
        self._head = 0

    def shift(self):
        if self._head >= len(self._items):
            raise IndexError("pop from empty queue")
        val = self._items[self._head]
        self._head += 1
        # 定期清理无效的头部元素
        if self._head * 2 > len(self._items):
            self._items = self._items[self._head:]
            self._head = 0
        return val

最后提个避坑点：别用“把元素反向存在列表尾部”的取巧方法——这种模式虽然弹头部元素可以用O(1)的pop()实现，但往队列尾部加元素就变成了O(n)的insert(0, val)，整体复杂度根本没有本质优化。没有特殊定制需求的话，优先选deque就够。

内容的提问来源于stack exchange，提问作者user1134991