Python数据结构详解:列表与双端队列

off999 2025-09-01 11:18 69 浏览 0 评论

列表：Python的"万能容器"

在Python的世界里，列表（List）就像是一个功能强大的"万能容器"，能够容纳各种类型的数据。它的灵活性和易用性使其成为Python程序员最常用的数据结构之一。

列表的基础操作

创建一个列表非常简单，只需用方括号将元素括起来，元素之间用逗号分隔：

// python
fruits = ['apple', 'banana', 'cherry']
numbers = [1, 2, 3, 4, 5]
mixed = [1, 'hello', 3.14, True]

列表支持多种基本操作，包括索引访问、切片、添加元素、删除元素等：

// python
# 索引访问
print(fruits[0]) # 输出: apple
# 切片操作
print(numbers[1:4]) # 输出: [2, 3, 4]
# 添加元素
fruits.append('orange')
print(fruits) # 输出: ['apple', 'banana', 'cherry', 'orange']
# 删除元素
del numbers[2]
print(numbers) # 输出: [1, 2, 4, 5]

列表的内部实现

Python列表的内部实现是一个动态数组，这意味着它会根据需要自动调整大小。当列表中的元素数量超过当前容量时，Python会分配一个更大的内存空间，并将所有元素复制到新的空间中。

连排座位示意图

这种实现方式使得列表在随机访问（通过索引访问元素）时非常高效，时间复杂度为O(1)。然而，在列表的开头或中间插入或删除元素时，效率较低，因为需要移动大量元素，时间复杂度为O(n)。

列表的高级用法

列表还支持许多高级操作，如列表推导式、排序、反转等：

// python
# 列表推导式
squares = [x**2 for x in range(10)]
print(squares) # 输出: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
# 排序
numbers = [3, 1, 4, 1, 5, 9, 2, 6]
numbers.sort()
print(numbers) # 输出: [1, 1, 2, 3, 4, 5, 6, 9]
# 反转
numbers.reverse()
print(numbers) # 输出: [9, 6, 5, 4, 3, 2, 1, 1]

双端队列：高效的双向操作容器

虽然列表在许多情况下都很有用，但在需要频繁在两端进行操作时，双端队列（deque）是一个更好的选择。deque是"double-ended queue"的缩写，它支持在队列的两端高效地添加和删除元素。

deque的基本操作

要使用deque，需要从collections模块中导入：

// python
from collections import deque
# 创建deque
dq = deque(['a', 'b', 'c'])
# 在右端添加元素
dq.append('d')
print(dq) # 输出: deque(['a', 'b', 'c', 'd'])
# 在左端添加元素
dq.appendleft('z')
print(dq) # 输出: deque(['z', 'a', 'b', 'c', 'd'])
# 在右端删除元素
dq.pop()
print(dq) # 输出: deque(['z', 'a', 'b', 'c'])
# 在左端删除元素
dq.popleft()
print(dq) # 输出: deque(['a', 'b', 'c'])

deque的内部实现

与列表的动态数组实现不同，deque通常使用双向链表或类似的数据结构实现。这种结构使得在两端添加和删除元素的操作都非常高效，时间复杂度为O(1)。

双向火车示意图

想象一列可以在两端都连接和分离车厢的火车，这就是deque的工作方式。无论你想在前端还是后端添加元素，都可以在常数时间内完成。

deque的高级特性

deque还提供了一些有用的高级特性：

// python
# 限制deque的大小
dq = deque(maxlen=3)
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4) # 当超过maxlen时，最左边的元素会被自动移除
print(dq) # 输出: deque([2, 3, 4], maxlen=3)
# 旋转操作
dq = deque([1, 2, 3, 4, 5])
dq.rotate(2) # 向右旋转2步
print(dq) # 输出: deque([4, 5, 1, 2, 3])
dq.rotate(-1) # 向左旋转1步
print(dq) # 输出: deque([5, 1, 2, 3, 4])

deque的应用场景

deque在许多场景中都非常有用：

实现队列和栈 ：deque可以同时作为队列（FIFO）和栈（LIFO）使用。
滑动窗口 ：利用deque的maxlen特性，可以轻松实现滑动窗口算法。
缓存：可以用deque实现一个简单的缓存系统，当缓存满时自动移除最旧的元素。

列表与deque的性能对比

为了更直观地了解列表和deque在不同操作上的性能差异，我们来做一些简单的性能测试。

测试代码

// python
import timeit
from collections import deque
# 测试列表和deque在两端添加元素的性能
def test_append():
list_time = timeit.timeit('lst.append(0)', 'lst = []', number=1000000)
deque_time = timeit.timeit('dq.append(0)', 'from collections import deque; dq = deque()', number=1000000)
print(f"Append to end: List={list_time:.4f}s, Deque={deque_time:.4f}s")
def test_appendleft():
list_time = timeit.timeit('lst.insert(0, 0)', 'lst = []', number=100000) # 列表左端添加操作较慢，减少测试次数
deque_time = timeit.timeit('dq.appendleft(0)', 'from collections import deque; dq = deque()', number=1000000)
print(f"Append to front: List={list_time:.4f}s, Deque={deque_time:.4f}s")
def test_pop():
list_time = timeit.timeit('lst.pop()', 'lst = list(range(1000000))', number=1000000)
deque_time = timeit.timeit('dq.pop()', 'from collections import deque; dq = deque(range(1000000))', number=1000000)
print(f"Pop from end: List={list_time:.4f}s, Deque={deque_time:.4f}s")
def test_popleft():
list_time = timeit.timeit('lst.pop(0)', 'lst = list(range(100000))', number=100000) # 列表左端删除操作较慢，减少测试次数
deque_time = timeit.timeit('dq.popleft()', 'from collections import deque; dq = deque(range(1000000))', number=1000000)
print(f"Pop from front: List={list_time:.4f}s, Deque={deque_time:.4f}s")
test_append()
test_appendleft()
test_pop()
test_popleft()

测试结果分析

典型的测试结果可能如下（具体数值会因硬件和软件环境而异）：

Append to end: List=0.0523s, Deque=0.0641s
Append to front: List=10.2345s, Deque=0.0782s
Pop from end: List=0.0567s, Deque=0.0612s
Pop from front: List=8.9123s, Deque=0.0654s

从结果中可以看出：

1.在末尾添加和删除元素：列表和deque的性能相近，列表甚至略快一些。

2.在开头添加和删除元素：deque的性能远远优于列表，差距可达两个数量级。

这是因为列表在开头操作时需要移动大量元素，而deque可以直接在两端进行操作，不需要移动其他元素。