python - 列出 pop、delitem、delslice、setslice、insert 等的实现

Question

python 方法内部有什么特别的事情可以从列表中删除值或插入到列表的中间吗？它只是删除/插入和转移所有内容吗？或者有什么更有创意的东西可以保持随机访问，而无需所有的转移。我以为我听说插入到列表的前面会导致其余部分被移动，从中间删除也是同样的想法吗？

score 3 · Accepted Answer

它正在改变一切。Python 列表实现为动态数组，需要 O(n) 时间从中间插入或删除。

我试图在文档中找到一个这样说的地方，或者证明任何允许从中间插入和删除 O(1) 的聪明方法都可以扩展到任何地方的 O(1) 插入和删除，但我不能找到任何东西。相反，您会从 Python 源代码中摘录一段，用 C 语言编写。

在 Python 2.7.3 源代码中的 listobject.c 中，插入方法将所有内容移到插入位置的右侧：

items = self->ob_item;
for (i = n; --i >= where; )
    items[i+1] = items[i];

不幸的是，我找不到相应的删除代码。

python - 列出 pop、__delitem__、__delslice__、__setslice__、insert 等的实现