【python】list的底层实现

python的list本质是动态数组

定义为：

typedef struct { PyObject_VAR_HEAD PyObject **ob_item; // 指向元素指针数组 Py_ssize_t allocated; // 当前分配的容量 } PyListObject;

内部有一块连续的内存，内存中存储指向对象的指针，它会预留额外空间，避免频繁扩容

1.什么是动态数组？

最基础的数组，底层是一段连续空间

动态数组，保留连续内存的特点，但在扩容时候是按比例扩容。当空间不够时，申请一块更大的连续内存，把旧数据复制过去，释放旧内存。

2.list有哪些特点？

list的中存储的是指向对象的指针，因此可以存储int，str等不同数据类型

append的时间复杂度是O(1)，因为它会过度分配，当容量不够时，扩容：新容量=原容量*k+常数，扩容的时候，要把旧数据复制到新的位置，长期平均下来是常数级。

访问 list[i]，这是纯数组索引：内存地址 = base + i * sizeof(pointer)，所以时间复杂度 O(1)。其中base是内存的起始位置，point是指向目前存储位置的指针（list存储的是指向对象的指针，所以不用sizeof(object)）

插入 insert(0, x)，因为数组是连续内存，要在开头插入，就需要把后面所有元素整体往后搬一格，时间复杂度 O(n)。这也是为什么做队列不要用 list，要用 collections.deque。deque 是双端队列，底层是分块数组 + 链式结构，适合频繁头尾操作

删除元素pop()，pop（）默认从末尾删，O(1)，pop(0)也是O(n)

python为什么不用链表实现list？链表的插入和删除都很快，但是随机访问很慢，现代cpu依赖缓存，数组时连续内存，cpu可以预读，连边分散内存，缓存命中率低。

为什么list不能无限缩容？不断pop时

3.numpy array和list的差别？

list存的是对象指针，不连续存储数据本体，类型不固定

numpy array连续存储原始数据，数据类型固定，可直接做向量化运算，速度更快（数据挖掘，视觉，机器人算法）

4.deque的特点？

deque的底层是分块数组+链式链接

对于头部操作，appendleft(x)，popleft()，都是O(1)

对于尾部操作，是稳定性的O(1),deque不会整体复制

对于随机访问，list O(1), deque O(n)，后者需要跳block

list 连续存储，缓存命中率高。deque 分块存储，局部性略差。在大量数值遍历场景下，list 更快。

常用的场景：BFS（广度优先搜索），任务调度，消息队列，滑动窗口等