简介

在这个专题中,我们将通过精简的文字和典型案例,盘点Python常用的数据结构。

对于Python初学者来说,只需掌握list、tuple、set、dict等基本数据结构,做到灵活运用即可。然而,随着学习的深入,遇到的实际场景会变得复杂,此时了解Python内置的更强大数据结构,如deque、heapq、Counter、OrderedDict、defaultdict、ChainMap,将能让你写出更高效的代码。

学习数据结构的三个阶段：

1. 掌握基本用法：使用这些数据结构解决一些基本问题。
2. 应用场景选择：知道在何种场景下选用哪种数据结构。
3. 深入理解实现：了解内置数据结构的源码实现,并将其与《算法和数据结构》的知识联系起来,提升编程能力。

下面我们将根据这三个阶段,详细介绍Python中10种最常用的数据结构：

1. List

基本用法

废话不多说,之前已有专题详述了list的使用【添加文章链接】。

使用场景

list适用于需要频繁查询和修改元素的场景,但不擅长频繁插入和删除元素的场景。

实现原理

list对应线性表数据结构,初始状态下无需指定长度。当插入元素超过初始长度时,会动态扩容。删除操作,尤其是在列表开头删除元素,时间复杂度为O(n)。

2. Tuple

元组是一种不可变的列表,一旦创建就不能修改。

基本用法

元组常用于打包和解包,例如函数有多个返回值时,可以打包为一个元组,赋值时解包。

t = 1, 2, 3 type(t) # 输出：<class 'tuple'>

使用场景

如果确定对象不会被修改,可以使用元组。相比于list,tuple更节省内存。

from sys import getsizeof
getsizeof(list())# 输出：72 getsizeof(tuple())# 输出：56

3. Set

基本用法

set是一种不含重复元素的数据结构,常用于列表去重。

a = [3, 2, 5, 2, 5, 3] set(a) # 输出：{2, 3, 5}

set还支持交集、并集、差集等操作。

a = {2, 3, 5}
b = {3, 4, 6, 2}
a.intersection(b)# 求交集 # 输出：{2, 3}

使用场景

适用于缓存不重复的元素值,同时允许高效的增删元素操作。

实现原理

set通过将值哈希为索引来获取数据,因此增删查操作效率很高。

4. Dict

基本用法

dict是Python中最常用的数据结构之一,支持通过dict函数、{}写法和字典生成式创建,增删查操作效率高。

d = {'a': 1,'b': 2}# {}创建字典 # 列表生成式 d = {a: bfora, binzip(['a','b'], [1, 2])}
d # 输出：{'a': 1, 'b': 2}

使用场景

字典适用于查询频繁的场景,时间复杂度为O(1)。例如,LeetCode第一题求两数之和时就会用到dict的O(1)查询时间复杂度。不过dict占用的内存较多,需注意内存限制。

getsizeof(dict())# 输出：248

实现原理

字典是一种哈希表,保存键值对。

以上4种数据结构相对较为基础,接下来介绍6种更高级的数据结构。

5. Deque

基本用法

deque（双端队列）基于list优化了两端的增删操作。

from collections import deque
d = deque([3, 2, 4, 0])
d.popleft()# 左侧移除元素，O(1)时间复杂度 # 输出：3 d.appendleft(3)# 左侧添加元素，O(1)时间复杂度 d # 输出：deque([3, 2, 4, 0])

使用场景

适合频繁在列表两端操作的场景,但牺牲了空间复杂度。

getsizeof(deque())# 输出：640 getsizeof(list())# 输出：72

实现原理

c实现deque使用默认长度64的数组,每次从左侧移除一个元素,leftindex加1,如果超过64则释放内存块,再重新申请64长度的数组,并使用双端链表block管理内存块。

6. Counter

基本用法

Counter继承于dict,用于统计元素个数的数据结构。

from collections import Counter
c = Counter([1, 3, 2, 3, 4, 2, 2])
c # 输出：Counter({1: 1, 3: 2, 2: 3, 4: 1}) # 统计最常见的项 c.most_common(1) # 输出：[(2, 3)]

使用场景

适用于统计元素出现频次的场景。

实现原理

Counter基于dict实现,将元素存储于keys,出现次数为values。

7. OrderedDict

基本用法

OrderedDict继承于dict,确保keys按照顺序取出。

from collections import OrderedDict
od = OrderedDict({'c': 3,'a': 1,'b': 2}) fork, vinod.items(): print(k, v) # 输出： # c 3 # a 1 # b 2

使用场景

适用于需要确保字典keys有序的场景。

实现原理

OrderedDict内部维护一个双向链表self.__root,确保keys的顺序,同时通过self.__map字典在O(1)时间内删除键值对。

8. Heapq

基本用法

heapq是基于list优化的堆队列,特点是最小元素总在根节点。

import heapq
a = [3, 1, 4, 5, 2, 1]
heapq.heapify(a)# 建堆后就地排序 a[0]# a[0]一定是最小元素 # 输出：1 heapq.nlargest(3, a)# a的前3个最大元素 # 输出： [5, 4, 3] heapq.nsmallest(3, a)# a的前3个最小元素 # 输出： [1, 1, 2]

使用场景

适用于统计list中前几个最小（大）元素的场景。

实现原理

堆是一种二叉树,父节点的值小于或大于所有孩子节点的值,原理与堆排序相似。

9. Defaultdict

基本用法

defaultdict是一种带有默认工厂的dict。

from collections import defaultdict
d = defaultdict(list)# 创建字典值默认为list的字典 words = ['book','nice','great','book'] fori, wordinenumerate(words):
d[word].append(i)

省去一层if逻辑判断,代码更加清晰。

使用场景

适用于键的值必须指定一个默认值的场景,如键的值为list、set、dict等。

实现原理

调用工厂函数提供缺失的键的值。

10. ChainMap

基本用法

ChainMap用于将多个dict合并为一个大dict,且支持同步更改。

from collections import ChainMap
d1 = {'a': 1,'c': 3,'b': 2}
d2 = {'d': 1,'e': 5}
dm = ChainMap(d1, d2)
dm # 输出：ChainMap({'a': 1, 'c': 3, 'b': 2}, {'d': 1, 'e': 5})

修改键值对时,原小dict也会改变。

dm.maps[0]['d'] = 20
dm # 输出：ChainMap({'a': 1, 'c': 3, 'b':