线性结构
本节我们从最简单和常用的线性结构开始，并结合 Python 语言本身内置的数据结构和其底层实现方式来讲解。 虽然本质上数据结构的思想是语言无关的，但是了解 Python 的实现方式有助于你避免一些坑
数组 array
数组是最常用到的一种线性结构，其实 python 内置了一个 array 模块，但是大部人甚至从来没用过它。 Python 的 array 是内存连续、存储的都是同一数据类型的结构，而且只能存数值和字符。
我建议你课下看下 array 的文档：https://docs.python.org/2/library/array.html
最常用的还是接下来要说的 list， 本节最后我们会用 list 来实现一个固定长度、并且支持所有 Python 数据类型的数组 Array.
| 操作 | 平均时间复杂度 |
|---|---|
| list[index] | O(1) |
| list.append | O(1) |
| list.insert | O(n) |
| list.pop(index) | O(1) |
| list.remove | O(n) |
用 list 实现 Array ADT
因为在别的语言中，array是定长的，因此我们在此，通过List来实现一个定长的数组
class Array():
def __init__(self, size):
self.__size = size
self.__item = [None] * size
def __getitem__(self, index):
return self.__item[index]
def __setitem__(self, key, value):
self.__item[key] = value
def __len__(self):
return self.__size
def clear(self, value=None):
for i in range(len(self.__size)):
self.__item[i] = value
def __iter__(self):
for v in self.__item:
yield v
if __name__ == '__main__':
a = Array(10)
a[0] = 10
a[2] = 20
print(len(a))
print(a.__len__())
练习：
- 完成容量内容扩展
- 完在删除功能