Python 中的 List 是封装了顺序存储结构还是链表存储结构？
最近在重温大学的数据结构突然想到一个问题，我们平时在使用的 List 到底是封装了顺序存储结构还是单链还是其他的结构，毕竟每一种结构都有其使用场景
另外想请教一下，Python 里面有相关的顺序存储结构或者链的相关库吗，可以方便直接拿来用的
Python 中的 List 是封装了顺序存储结构还是链表存储结构？
Python 的 list 底层实现是动态数组（顺序存储结构），而不是链表。
具体来说，它是一块连续的内存空间，存储的是对象的引用（指针）。当空间不足时，会动态地重新分配一块更大的内存（通常是按比例增长，比如 newsize = (oldsize >> 3) + (oldsize < 9 ? 3 : 6) 这种策略），然后把原有元素复制过去。这使得索引操作 list[i] 是 O(1) 的时间复杂度，但中间插入或删除（尤其是开头）可能涉及大量元素的移动，是 O(n)。
如果你需要一个链表结构，可以看看 collections.deque，它的底层是双向链表，在两端进行插入和删除操作是 O(1)。
总结：list 是动态数组，不是链表。
cpython 就是动态数组，一个 struct，里面有动态数组和类似 size，used 之类的属性。不够了就 realloc。
jython 是用了 arraylist，其实也是动态数组。
自己看看 python list 的实现，还真的不是链表
https://github.com/python/cpython/blob/3.7/Include/listobject.h#L23
至于 append 怎么实现的，基本上就是和 c++的 vector 一样，开个大数组，不够用就再扩容呗
https://github.com/python/cpython/blob/3.7/Objects/listobject.c#L301
扩容因子在这里定义的
https://github.com/python/cpython/blob/3.7/Objects/listobject.c#L59
就是说他的容量递增永远是按照这个序列来
0, 4, 8, 16, 25, 35, 46, 58, 72, 88,
至于这个序列就是从 (newsize >> 3) + (newsize < 9 ? 3 : 6) 算出来的呀
我想错了…白打了这么多字就不删了，给不明白的同学看看
初始化长度为 0，当想要 resize 为 1 的时候，实际 allocated 为 1+0+3=4
resize 为 5，allocated 为 5+0+3=8
resize 为 9，allocated 为 9+1+6=16
resize 为 17，allocated 为 17+2+6=25
动态数组实现的。在 Python 中 list 的操作涉及到 list 长度改变的，在底层（ CPython ）中都会调用 list_resize(PyListObject *self, Py_ssize_t newsize) 这个方法，这个方法也是 list 长度改变的核心算法实现；如果是当前 list 的长度大于了之前申请的内存空间了，那么新的长度通过这个表达式得出 new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)（也就是#14 楼说的那个序列值），然后在动态申请内存；
这里是 list.insert 的实现，我把关键的实现挑出来：
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
Py_ssize_t i, n = Py_SIZE(self);
PyObject *items;
/ 这里重新计算长度 /
if (list_resize(self, n+1) < 0)
return -1;
if (where < 0) {
where += n;
if (where < 0)
where = 0;
}
if (where > n)
where = n;
/ items 可以理解为一个数组，items 这个数组里存放的是 PyObject 这样的结构体（也就是 Python 中的数据） /
items = self->ob_item;
/ where 是要插入的位置 /
for (i = n; --i >= where; )
/ 将要插入位置之后的元素往后移一位 /
items[i+1] = items[i];
Py_INCREF(v);
/ 插入元素 */
items[where] = v;
return 0;
}
这里是通过数组实现的，也就是顺序结构。
