为什么 Python 需要 O(n) 时间才能从列表中删除第一个元素？

Question

关于时间复杂度的Python wiki 页面表示删除一个项目需要 O(n) 时间。集合模块的文档中对 deque 类的描述表示“list对象 [...] 会产生 O(n) 内存移动成本pop(0)以及insert(0, v)更改底层数据表示的大小和位置的操作”。

为什么列表需要 O(n) 时间？列表不就是一堆元素或指向元素的指针，在内存中物理上彼此相邻，以及指向列表开始位置的指针吗？list如果是这样，为什么该类型不能有popleft一个类似于 中的方法collections.deque，通过适当增加列表的起始指针来在 O(1) 时间内删除第一个元素？

我并不是想解决任何具体问题。我只是想满足我的好奇心，为什么要这样设计。

编辑：popleft这是我的方法如何工作的图表：

致电之前popleft：

-------------------------------------------------------------------
|    The   |  quick   |  brown   |   fox    |  jumps   |   over   |
-------------------------------------------------------------------
      ^
      pointer to list

致电后popleft：

-------------------------------------------------------------------
|    The   |  quick   |  brown   |   fox    |  jumps   |   over   |
-------------------------------------------------------------------
                 ^
                 pointer to list

在调用 之前popleft，列表的第一个元素是The，第二个元素是quick，等等。调用之后，第一个元素所在的位置现在是未使用的内存（可能为空或被垃圾收集器占用），新的第一个元素是quick，新的第二个元素是brown，等等。不需要移动大量数据，也不需要发生任何需要 O(n) 时间的事情。

Answer 1

指向列表实际位置的指针为了适当地释放内存，必须保留

事实上，remove(0)通过在这种情况下增加第二个指针可以使速度更快。如果一个.add(0, x)之后发生这种情况，只要该“数据启动计时器”大于“内存启动计时器”，就可以通过递减该“数据启动计时器”来加快速度。

但所有其他操作，即对其他索引的插入和删除，仍然会是O(n)，因此不会有太大变化。

只需知道您的操作是什么，从而选择哪种数据结构即可。

Answer 2

Pythonlist实际上是一个数组。deque是一个实链表。这是 Python 使用错误术语的错误（对此我没有解释）。O(n)对于数组来说，插入和删除是正常的（因为后面的元素需要向上或向下移动），这是对O(1)获取和设置速度的权衡。链表在相反的方向上做了类似的权衡：O(1)对于末端的操作，但O(n)对于中间的任何访问。