1. 数据结构的操作
作为一种包含元素的数据结构，需要提供一些“标准”操作:
- 创建和销毁
- 判断是否空,如果容量有限，还需判断是否满
- 向结构中加入元素或从中删除
- 访问结构里的元素
不同的编程语言可能影响需要实现的操作:
由于python能自动回收不用的对象，因此不需要销毁结构的操作
2. 从支持操作类型的角度看，数据结构可分为两类：
- 不变数据结构，如python中的tuple和frozenset
- 变动数据结构，如python中的list，dict，set
3. python的list
list是一种线性结构，可看作线性表的一种实现:
- 基于下标（位置）的元素访问和更新操作，复杂性为O(1)
- 允许任意加入元素，而且维持表对象标识不变（id()）
list实现约束和解决方案:
- 要求O(1)的元素访问并维持元素的顺序，只能采用连续表技术，元素保存在一块连续存储区
- 要能容纳任意多个元素，必须在元素个数将要超出存储区容量时换一块更大的存储区。要想在替换存储时id不变，只能采用分离式实现
list里元素越多，换一次存储区的代价也越高:
- 要想平均结果较好，随着表长度增加，换存储区的频率应降低
- 一种可能做法：每次换存储区，容量加倍
一次高开销操作后，保证有很多次低开销操作，称为分期付款式的常量复杂性
python中list采用上述设计，因此lst.insert(len(lst)， x)比一般位置加入的效率高.等价写法lst.append(x)，若合适就应优先使用。