1 环境

Python3.7.3

2 List

操作 操作说明 时间复杂度
a = index(value) 索引赋值 O(1)
append(value) 队尾添加 O(1)
pop() 队尾删除 O(1)
pop(index) 根据索引删除某个元素 O(n)
insert(index, value) 根据索引插入某个元素 O(n) iterration
search(in) 列表搜索（其实就是in关键字） O(n)
slice [x:y] 切片, 获取x, y为O(1), 获取x,y 中间的值为O(k) O(k)
del slice [x:y] 删除切片，删除切片后数据需要重新移动/合并 O(n)
reverse 列表反转 O(n)
sort 排序 O(nlogn)

3 Dict

操作 操作说明 时间复杂度
copy 复制 O(n)
get(value) 获取 O(1)
set(value) 修改 O(1)
delete(value) 删除 O(1)
search(value) 字典搜索 O(1)
iterration(value) 字典迭代 O(n)

字典的特性

查找速度快,无论dict有10个元素还是10万个元素，查找速度都一样。而list的查找速度随着元素增加而逐渐下降。
不过dict的查找速度快不是没有代价的，dict的缺点是占用内存大，还会浪费很多内容，list正好相反，占用内存小，但是查找速度慢。
字典值可以没有限制地取任何python对象，既可以是标准的对象，也可以是用户定义的，但键不行。不允许同一个键出现两次。
键必须不可变，所以可以用数字，字符串或元组充当，所以用列表就不行。
dict的第二个特点就是存储的key-value序对是没有顺序的！这和list不一样。