Python 数据结构及其用法综述

一、内置数据结构

1. 数字（Numbers）

特点 不可变类型，用于表示数值数据

主要类型

• int 整数，如 10
• float 浮点数，如 3.14
• bool 布尔值，True 或 False

示例

# 整数
x = 10
# 浮点数
y = 10.5
# 布尔值
flag = True

# 数值运算
sum_val = x + y  # 20.5
product = x * y  # 105.0

常用函数

• abs() 绝对值
• round() 四舍五入
• min() / max() 最小 / 最大值
• pow() 幂运算

2. 字符串（Strings）

特点 不可变序列，用于表示文本数据

创建与访问

# 创建字符串
s1 = 'Hello'
s2 = "World"
s3 = '''多行
字符串'''

# 访问字符
first_char = s1[0]  # 'H'
# 切片
substring = s1[1:4]  # 'ell'

常用操作

# 连接
s = s1 + ' ' + s2  # 'Hello World'

# 重复
repeated = s1 * 3  # 'HelloHelloHello'

# 查找
position = s.find('o')  # 4

# 替换
new_s = s.replace('o', 'x')  # 'Hellx Wxrld'

# 分割
parts = s.split(' ')  # ['Hello', 'World']

# 格式化
formatted = f"{s1}, {s2}!"  # 'Hello, World!'
formatted2 = "{}, {}!".format(s1, s2)  # 'Hello, World!'

常用方法

• upper() / lower() 大小写转换
• strip() 去除空白
• startswith() / endswith() 检查开头 / 结尾
• isalpha() / isdigit() / isalnum() 内容检查

3. 列表（Lists）

特点 可变序列，可存储不同类型的元素

创建与访问

# 创建列表
lst = [1, 'hello', 3.14, True]

# 访问元素
first = lst[0]  # 1
# 负索引（从尾部开始）
last = lst[-1]  # True

# 切片
part = lst[1:3]  # ['hello', 3.14]

常用操作

# 添加元素
lst.append(5)  # [1, 'hello', 3.14, True, 5]
lst.insert(2, 'inserted')  # [1, 'hello', 'inserted', 3.14, True, 5]
lst.extend([6, 7])  # [1, 'hello', 'inserted', 3.14, True, 5, 6, 7]

# 删除元素
lst.remove('inserted')  # 删除指定元素
popped = lst.pop()  # 删除并返回最后一个元素
del lst[0]  # 删除指定位置元素

# 查找
index = lst.index(3.14)  # 查找元素位置

# 排序
nums = [3, 1, 4, 1, 5, 9]
nums.sort()  # [1, 1, 3, 4, 5, 9]
nums.sort(reverse=True)  # [9, 5, 4, 3, 1, 1]
sorted_nums = sorted(nums)  # 不修改原列表

# 列表推导式
squares = [x**2 for x in range(1, 6)]  # [1, 4, 9, 16, 25]
even_squares = [x**2 for x in range(1, 11) if x % 2 == 0]  # [4, 16, 36, 64, 100]

4. 元组（Tuples）

特点 不可变序列，可存储不同类型的元素

创建与访问

# 创建元组
t1 = (1, 'hello', 3.14)
t2 = 1, 'hello', 3.14  # 可省略括号
single_item = (1,)  # 单元素元组需要逗号
empty = ()  # 空元组

# 访问元素
first = t1[0]  # 1
slice_t = t1[1:]  # ('hello', 3.14)

常用操作

# 连接
combined = t1 + (4, 5, 6)  # (1, 'hello', 3.14, 4, 5, 6)

# 重复
repeated = t1 * 2  # (1, 'hello', 3.14, 1, 'hello', 3.14)

# 查找
count = t1.count('hello')  # 计数
index = t1.index(3.14)  # 查找元素位置

# 解包
a, b, c = t1  # a=1, b='hello', c=3.14

5. 字典（Dictionaries）

特点 可变映射类型，键-值对集合，键必须是不可变类型

创建与访问

# 创建字典
d1 = {'name': 'Python', 'version': 3.9, 'is_oop': True}
d2 = dict(name='Python', version=3.9, is_oop=True)
d3 = dict([('name', 'Python'), ('version', 3.9)])

# 访问元素
name = d1['name']  # 'Python'
version = d1.get('version')  # 3.9
# get方法可设置默认值
unknown = d1.get('unknown', 'Not Found')  # 'Not Found'

直接读取和使用 get 方法读取的区别：直接读取的属性如果不存在，代码会报错，无法继续运行。get 方法读取的属性如果不存在，可以手动设置一个预期值，比如上面的 Not Found；如果不设置，则返回 None.

常用操作

# 添加/更新元素
d1['date'] = '2021-01-01'
d1.update({'version': 3.10, 'author': 'Guido'})

# 删除元素
del d1['is_oop']
popped = d1.pop('date')  # 删除并返回
d1.popitem()  # 删除并返回最后添加的元素
d1.clear()  # 清空字典

# 查找
'name' in d2  # True，检查键是否存在

# 字典视图
keys = d2.keys()  # 键视图
values = d2.values()  # 值视图
items = d2.items()  # (键, 值)对视图

# 字典推导式
squares = {x: x**2 for x in range(6)}  # {0:0, 1:1, 2:4, 3:9, 4:16, 5:25}

上述字典视图三个变量，看似和 list 类型很像，但是并不具备 list 类型的能力。如果希望转换成 list，可以使用 list() 函数来转换。

6. 集合（Sets）

特点 可变无序集合，元素不重复，元素必须是不可变类型（不能通过索引访问元素，只能遍历或检查成员）

创建

# 创建集合
s1 = {1, 2, 3, 4, 5}
s2 = set([3, 4, 5, 6, 7])
empty_set = set()  # 空集合（不能用{}，那是空字典）

常用操作

# 添加元素
s1.add(6)  # {1, 2, 3, 4, 5, 6}
s1.update([7, 8, 9])  # {1, 2, 3, 4, 5, 6, 7, 8, 9}

# 删除元素
s1.remove(9)  # 元素不存在会引发错误
s1.discard(10)  # 元素不存在不会引发错误
popped = s1.pop()  # 随机删除并返回一个元素
s1.clear()  # 清空集合

# 集合运算
union = s1 | s2  # 并集，等同于 s1.union(s2)
intersection = s1 & s2  # 交集，等同于 s1.intersection(s2)
difference = s1 - s2  # 差集，等同于 s1.difference(s2)
sym_diff = s1 ^ s2  # 对称差集，等同于 s1.symmetric_difference(s2)

# 集合推导式
even_set = {x for x in range(10) if x % 2 == 0}  # {0, 2, 4, 6, 8}

7. frozenset（冻结集合）

特点 不可变的集合，可作为字典的键或集合的元素

# 创建冻结集合
fs = frozenset([1, 2, 3, 4])

# 可以使用与集合相同的方法，但不能添加或删除元素
union = fs.union({5, 6})  # frozenset({1, 2, 3, 4, 5, 6})

二、Python 标准库中的数据结构

1. 数组（array）

特点 比列表更高效的同类型元素集合，基于 C 语言数组

import array

# 创建数组（'i'表示整数类型）
arr = array.array('i', [1, 2, 3, 4, 5])

# 常用操作类似于列表
arr.append(6)
arr.extend([7, 8, 9])
arr.pop()

2. 双端队列（collections.deque）

特点 两端都可高效添加和删除元素的列表

from collections import deque

# 创建双端队列
dq = deque([1, 2, 3])

# 添加元素
dq.append(4)  # 右侧添加
dq.appendleft(0)  # 左侧添加

# 删除元素
dq.pop()  # 右侧删除
dq.popleft()  # 左侧删除

# 旋转元素
dq.rotate(1)  # 将元素右移1位
dq.rotate(-2)  # 将元素左移2位

3. 命名元组（collections.namedtuple）

特点 带有命名字段的元组，可通过名称访问元素

from collections import namedtuple

# 定义命名元组类型
Point = namedtuple('Point', ['x', 'y'])

# 创建实例
p = Point(11, 22)

# 访问元素
print(p.x)  # 11
print(p[0])  # 11

4. 有序字典（collections.OrderedDict）

特点 保持元素插入顺序的字典（Python 3.7+的普通字典也具有此特性）

from collections import OrderedDict

# 创建有序字典
od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])

# 移动元素到末尾
od.move_to_end('a')

# 弹出首个或最后一个元素
first = od.popitem(last=False)  # 弹出第一个元素

5. 默认字典（collections.defaultdict）

特点 当访问不存在的键时提供默认值的字典

from collections import defaultdict

# 创建默认为整数0的字典
dd_int = defaultdict(int)
dd_int['a'] += 1  # 不存在时会自动创建并设为0，然后加1

# 创建默认为列表的字典
dd_list = defaultdict(list)
dd_list['a'].append(1)  # 不存在时会自动创建空列表，然后添加元素

6. 计数器（collections.Counter）

特点 计数可哈希对象的字典子类

from collections import Counter

# 创建计数器
c = Counter('abracadabra')

# 获取2个显示次数最高的元素
most_common = c.most_common(2)  # [('a', 5), ('b', 2)]

# 更新计数
c.update('aaa')

# 集合操作
c1 = Counter('abc')
c2 = Counter('abcd')
print(c1 + c2)  # 元素相加
print(c1 - c2)  # 元素相减（负值会被忽略）

7. 堆队列（heapq）

特点 基于堆的优先队列实现

import heapq

# 创建堆
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(nums)  # 将列表转换为堆

# 添加元素
heapq.heappush(nums, 7)

# 弹出最小元素
smallest = heapq.heappop(nums)

# 查看最小元素但不移除
peek = nums[0]

# 获取最大/最小的n个元素
largest = heapq.nlargest(3, nums)
smallest = heapq.nsmallest(3, nums)

8. 枚举类型（enum）

特点 用于创建带命名值的枚举类型

from enum import Enum, auto

class Color(Enum):
    RED = 1
    GREEN = 2
    BLUE = auto()  # 自动分配值

# 访问枚举成员
color = Color.RED
print(color.name)  # 'RED'
print(color.value)  # 1

# 迭代所有成员
for color in Color:
    print(color)

9. 队列（queue）

特点 线程安全的 FIFO、LIFO 和优先级队列实现

from queue import Queue, LifoQueue, PriorityQueue

# FIFO队列
q = Queue(maxsize=10)
q.put(1)
item = q.get()

# LIFO队列（栈）
lifo = LifoQueue()
lifo.put(1)
lifo.put(2)
last = lifo.get()  # 2

# 优先级队列
pq = PriorityQueue()
pq.put((2, 'mid priority'))  # (优先级, 数据)
pq.put((1, 'high priority'))
pq.put((3, 'low priority'))
highest = pq.get()  # (1, 'high priority')

三、高级数据结构实现

1. 链表（Linked List）

实现示例

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return

        current = self.head
        while current.next:
            current = current.next
        current.next = Node(data)

    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        return elements

2. 栈（Stack）

基于列表实现

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

3. 树（Tree）

二叉树实现示例

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BinaryTree:
    def __init__(self, root=None):
        self.root = root

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return

        queue = [self.root]
        while queue:
            node = queue.pop(0)
            if not node.left:
                node.left = TreeNode(val)
                return
            elif not node.right:
                node.right = TreeNode(val)
                return
            else:
                queue.append(node.left)
                queue.append(node.right)

    # 前序遍历 (根-左-右)
    def preorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            result.append(node.val)
            self.preorder(node.left, result)
            self.preorder(node.right, result)
        return result

    # 中序遍历 (左-根-右)
    def inorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.inorder(node.left, result)
            result.append(node.val)
            self.inorder(node.right, result)
        return result

    # 后序遍历 (左-右-根)
    def postorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.postorder(node.left, result)
            self.postorder(node.right, result)
            result.append(node.val)
        return result

4. 图（Graph）

邻接表实现示例

class Graph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, from_vertex, to_vertex):
        if from_vertex in self.graph:
            self.graph[from_vertex].append(to_vertex)
        else:
            self.graph[from_vertex] = [to_vertex]

    def get_vertices(self):
        return list(self.graph.keys())

    def get_edges(self):
        edges = []
        for vertex in self.graph:
            for neighbor in self.graph[vertex]:
                edges.append((vertex, neighbor))
        return edges

    # 广度优先搜索
    def bfs(self, start_vertex):
        visited = {vertex: False for vertex in self.graph}
        queue = [start_vertex]
        visited[start_vertex] = True
        result = []

        while queue:
            current = queue.pop(0)
            result.append(current)

            for neighbor in self.graph[current]:
                if not visited.get(neighbor, False):
                    visited[neighbor] = True
                    queue.append(neighbor)

        return result

    # 深度优先搜索
    def dfs(self, start_vertex, visited=None, result=None):
        if visited is None:
            visited = {vertex: False for vertex in self.graph}
        if result is None:
            result = []

        visited[start_vertex] = True
        result.append(start_vertex)

        for neighbor in self.graph[start_vertex]:
            if not visited.get(neighbor, False):
                self.dfs(neighbor, visited, result)

        return result

5. 前缀树（Trie）

实现示例

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

6. 并查集（Union-Find）

实现示例

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return

        # 按秩合并
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

四、数据结构性能比较

下面是主要 Python 数据结构的时间复杂度比较

五、数据结构选择指南

• 需要快速查找和更新 使用字典（Dictionary）
• 需要保持插入顺序 使用列表（List）或有序字典（OrderedDict）
• 需要唯一元素 使用集合（Set）
• 需要固定数据 使用元组（Tuple）
• 需要两端快速操作 使用双端队列（Deque）
• 需要优先级处理 使用堆（Heap）或优先队列（PriorityQueue）
• 需要频繁计数 使用 Counter
• 需要动态数据结构 根据具体需求选择树（Tree）、图（Graph）等