python的list本质是动态数组定义为typedef struct { PyObject_VAR_HEAD PyObject **ob_item; // 指向元素指针数组 Py_ssize_t allocated; // 当前分配的容量 } PyListObject;内部有一块连续的内存内存中存储指向对象的指针它会预留额外空间避免频繁扩容1.什么是动态数组最基础的数组底层是一段连续空间动态数组保留连续内存的特点但在扩容时候是按比例扩容。当空间不够时申请一块更大的连续内存把旧数据复制过去释放旧内存。2.list有哪些特点list的中存储的是指向对象的指针因此可以存储intstr等不同数据类型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)后者需要跳blocklist 连续存储缓存命中率高。deque 分块存储局部性略差。在大量数值遍历场景下list 更快。常用的场景BFS广度优先搜索任务调度消息队列滑动窗口等