数据结构---数组（Data Structure Array Python）

数组（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)。