Python列表、元组、集合、字典的操作及列表与字典时间复杂度的比较
| 列表 | 元组 | 字典 | 集合 | |
|---|---|---|---|---|
| 是否 可变 | 可变 | 不可变 | 可变 | 可变 |
| 是否 有序 | 有序 | 有序 | 可变 | 可变 |
| 元素 是否 重复 | 可重复 | 可重复 | 键不可重复 | 不可重复 |
| 定义 符号 | [] | () | {key:value} | {} |
| 创建 | 1.[]直接创建 2.list() 3.列表解析式 | 1.()直接创建 2.tuple() | 1.{}直接创建 2.dict() | 1.set() (不可以使用{}来创建， 那样是dict而不是set) |
| 删除 | 1.del删除元素或者列表 2.list.remove(value) | 1.del删除元素或元组 | 1.del删除元素或字典 | 1.del删除元素或集合 2.set.remove() 3.set.pop() 4.set.clear() |
| 修改 插入 | 1.append() 2.insert() 3.+ 4.extend() | 不可修改 | 1.dict[key]=value | s.add() |
| 访问 遍历 | 1.索引访问 2.for循环遍历 for i in list for index，i in enumerate（list） | 1.索引访问 2.for循环遍历 | 1.键访问 2.get()访问 3.for key，value in dict.items() for key in dict.keys() for value in dict.values() | for循环遍历 |
| 生成式 | [i*i for i in list1]返回列表 | (i*i for i in list1)返回生成器对象， 通过for和next()访问 | dict={i:j for i,j in zip(list1,list2)} dict={i*2:2 for i in range(1,10)} | 交集&，并集 | ，差集- , ^ 不同时包含于a和b集合的元素 |
| 切片 | 支持切片 | 支持切片 | 不支持切片 | 不支持切片 |
| 索引 | 支持索引 | 支持索引 | 不支持索引 | 不支持索引 |
| +、* 运算 | 支持 | 支持 | 不支持 | 不支持 |
| 其它 | 不能作为字典的键 | 可以作为字典的键 |
概括几点列表、字典、集合某些操作的时间复杂度比较：
1.查找速度快,无论dict有10个元素还是10万个元素，查找速度都一样。而list的查找速度随着元素增加而逐渐下降。
不过dict的查找速度快不是没有代价的，dict的缺点是占用内存大，还会浪费很多内容，list正好相反，占用内存小，但是查找速度慢。
2.字典值可以没有限制地取任何python对象，既可以是标准的对象，也可以是用户定义的，但键不行。不允许同一个键出现两次。
键必须不可变，所以可以用数字，字符串或元组充当，所以用列表就不行。
3.关于列表内部实现是数组（具体实现要看解析器, CPython的实现 ），因此就有数组的特点。超过容量会增加更多的容量，set, get 是O(1)，但del, insert, in的性能是O(n)。具体的看下表，'n’是容器中当前的元素数， 'k’需要操作的元素个数；
关于字典需要了解的是hash函数和哈希桶。一个好的hash函数使到哈希桶中的值只有一个，若多个key hash到了同一个哈希桶中，称之为哈希冲突。查找值时，会先定位到哈希桶中，再遍历hash桶。更详细的信息请点这里。在hash基本没有冲突的情况下get, set, delete, in方面都是O(1)。自己的操作不会超过O(n)；
关于set内部实现是dict的。在in操作上是O(1), 这一点比list要强。
也有list不存在的差运算；
list列表：
dict字典: