什么是数组？
数组是线性表数据结构。用连续的内存空间存储相同类型的数据。
- 线性表：线性表是数据排成一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。
包括：数组，链表、队列、栈。 - 非线性表：数据之间并不是简单的前后关系。
包括：二叉树、堆、图等。 - 连续的内存空间和相同类型的数据：使数组支持“随机访问”。但在数组中删除、插入数据时，需要做大量的数据搬移工作。
数组如何实现随机访问？
C 语言代码： int[] tmp = new int[4]，这个数组在内存中连续放置：
插入操作
- 在数组末尾插入元素，不需要移动数据，时间复杂度为 O(1)。
- 在数组开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n)。
- 假设每个位置插入元素概率相同，平均情况时间复杂度为 (1+2+…n)/n=O(n)。
如果元素无序，可直接换位：
删除操作
- 删除数组末尾数据：则最好情况时间复杂度为 O(1)；
- 删除开头的数据：则最坏情况时间复杂度为 O(n)；
- 平均情况时间复杂度也为 O(n)。
预删除思想：JVM 标记清除垃圾回收算法
改进数组
编程语言封装了数组，比如 Java 的 ArrayList， Python 的 List ，可实现自动扩容，多种数据类型组合。
如果你是底层工程师，需要极致的比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。
class Array:
def __init__(self, capacity) -> None:
self.data = [-1]*capacity
self.count = 0
self.n = capacity
def insert(self, location, value):
if self.n == self.count:
return False
if location < 0 or location > self.count:
return False
for i in range(self.count, location, -1):
self.data[i] = self.data[i-1]
self.data[location] = value
self.count += 1
return True
def find(self, location):
if location < 0 or location >= self.count:
return -1
return self.data[location]
def delete(self, location):
if location < 0 or location >= self.count:
return False
for i in range(location + 1, self.count):
self.data[i-1] = self.data[i]
self.count -= 1
return True
def test_demo():
array = Array(5)
array.insert(0, 1)
array.insert(0, 2)
array.insert(1, 3)
array.insert(2, 4)
array.insert(4, 5)
# 判断插入不成功
assert not array.insert(0, 100)
assert array.find(0) == 2
assert array.find(2) == 4
assert array.find(4) == 5
assert array.find(10) == -1
assert array.count == 5
removed = array.delete(4)
assert removed
assert array.find(4) == -1
removed = array.delete(10)
assert not removed
# 2 3 4 1 5
assert array.data == [2, 3, 4, 1, 5]
if __name__ == '__main__':
test_demo()
python list 源码解析
本篇文章描述了 CPython 中 list 的实现方式。
C 语言用结构体表示 List 对象
C 语言使用结构体实现 list 对象，结构体代码如下。
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item; //指向 list 中的对象
Py_ssize_t allocated; //内存分配的插槽
} PyListObject;
List 初始化
以 I = [] 为例
list 的数量是指 len(l)。分配的槽位数量是指在内存中实际分配的数量。通常情况，内存中分配的数量要大于 list 的数量。这是为了当添加新元素时，避免内存再分配。
Append
当运行l.append(1)时， CPython 将调用app1()：
list_resize() 会故意分配更多的内存，避免被多次调用。分配内存大小增加：0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …
第一次分配了 4 个槽位，I[0] 指向了数字对象 1 。正方形虚线表示未使用过的槽位。追加操作的均摊复杂度为 O(1) 。
均摊时间复杂度是平均时间复杂度的一种，是一种简化的计算方法。
继续追加元素：l.append(2)。调用 list_resize 实现 n + 1 = 2。由于分配了四个空间，不需要分配内存。当再向列表追加两个数字时，l.append(3), l.append(4)，如下图如示：
Insert
在位置 1 插入整型 5 ，即调用 python 的 l.insert(1, 5) 。CPython 会调用 ins1() ：
插入操作需要将剩余元素向右迁移：
上图虚线表示未使用的槽位（slots），分配了 8 个槽位，但 list 的长度只有 5 。 insert 的时间复杂度为 O(n)。
pop
弹出列表的最后一个元素使用 l.pop()，CPython 使用 listpop() 实现这个过程。如果新内存大小少于分配大小的一半， listpop() 将调用 list_resize 减少 list 内存。
Pop 的时间复杂度是 O(1)。
注意，此时槽位 4 仍然指向整型 4 ，但是 list 的大小却是 4 。只有 pop 更多的元素才能调用 list_resize() 减少内存，如果再 pop 一个元素， size - 1 = 4 - 3 = 3， 3 小于分配槽位的一半 8/2 = 4 。所以 list 收缩到 6 个槽位， list 的大小为 3 。虽然槽位 3 和 4 依旧指向整型对象，但是整体大小变成了 3 。
remove
Python 可以用 remove 删除指定元素：l.remove(5)。此时将调用 listremove() 。
CPython 调用 list_ass_slice() 函数对列表进行切分并删除元素。当在位置 1 移除元素 5 时，低偏移（low offset）是 1 ，高偏移（high offset）是 2 ：
remove 时间复杂度是 O(n)。
文章参考：
http://www.laurentluce.com/posts/python-list-implementation/