Python 的列表是作为链表还是数组实现的？

Python 列表实现揭晓

它是链表还是数组？

中在 Python 的列表操作领域，底层实现对许多人来说仍然是个谜。猜测比比皆是，但好奇的人却没有得到具体的答案。为了解开这个谜团，我们深入研究 C 代码，揭开 Python 列表结构的真实本质。

指针向量

与猜测相反链表，Python 的列表是建立在类似数组的结构之上的。检查 listobject.h 标头揭示了列表的核心定义：称为 PyListObject 的类型。该结构由三个基本元素组成：

• ob_size: 当前使用的元素数量。
• ob_item: Python 对象数组指针，代表列表项。
• 分配：数组的最大容量。

动态分配和过度分配

数组 ob_item 提供对列表元素的直接访问，类似于 C 中的数组。 ，Python采用过度分配的策略来优化效率。当 ob_item 数组填满时，会分配一个新的更大的数组。新容量使用以下公式计算：

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

其中 newsize 是请求的大小。这个公式确保为将来的插入提供足够的空间，同时避免过多的分配开销。

结论

Python 列表接口的背后是基于向量的实现。每个列表项都由指向对象的指针表示，并且向量本身被动态分配和过度分配以增强性能。这种方式在高效存储和灵活增长之间取得了平衡，实现了Python基本列表数据结构的无缝运行。

以上是Python 的列表是作为链表还是数组实现的？的详细内容。更多信息请关注PHP中文网其他相关文章！