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

Question

Python wiki page on time complexity说删除一个项目需要 O(n) 时间。 description of the deque class in the documentation of the collections module表示“list objects [...] 会导致 pop(0) 和 insert(0, v) 的 O(n) 内存移动成本> 改变底层数据表示的大小和位置的操作”。

为什么列表需要 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)，只要它大于“内存启动计时器”，就可以通过递减此“数据启动计时器”来加快速度。

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

只要知道您的操作是什么，以及选择哪种数据结构即可。