数组（Array）： 是一种线性数据结构，其数据占据连续且空余（back to back & free）的内存位置。
数组分为静态数组和动态数组：
静态（static）：每个item占据相同宽度的内存位置。其支持的语言比如Java。
动态（dynamic）：每个item占据的内存位置要比所需的多，通常是所需的两倍。其支持的语言比如Python。
python实现：直接用list实现，例如：a=[1, 2, 3, 4]。
时间复杂度（Time Complexity）：
initialize（初始化操作）：O(N)
indexing（索引操作）：O(1)
traverse（遍历操作）：O(N)
copy（拷贝操作）：O(N)
insert（插入操作）：O(N)
append（增加操作）：O(1)
pop（去除操作）：从尾部去除item的pop()方法为O(1)，从开头或中间去除item的方法为O(N)，例如pop(0)
之前说过，python采用的是动态数组，因此其append操作和pop操作无需先复制整个数组，再找连续且空余的内存位置进行储存，只要其先前占据的内存空间未满，那么这两个操作的时间复杂度就是O(1)。
数据结构---数组（Data Structure Array Python）
原文：https://www.cnblogs.com/HuZihu/p/14454781.html