是链表还是数组?我四处寻找,只发现人们在猜测。我的 C 知识还不够好,无法查看源代码。
最佳答案
实际上,C 代码非常简单。扩展一个宏,剪掉一些不相关的注释,基本结构在listobject.h
,它将列表定义为:
typedef struct {
PyObject_HEAD
Py_ssize_t ob_size;
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
*/
Py_ssize_t allocated;
} PyListObject;
PyObject_HEAD
包含一个引用计数和一个类型标识符。所以,它是一个过度分配的向量/数组。数组满时调整大小的代码在 listobject.c
中。 .它实际上并没有使数组加倍,而是通过分配来增长
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;
每次到容量,其中 newsize
是请求的大小(不一定是 allocated + 1
因为您可以 extend
任意数字元素而不是 append
逐一添加)。
另见Python FAQ .
关于python - Python 的 List 是如何实现的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3917574/