【Python 语法】Python 数据结构

Python 的数据结构可以根据 存储方式、访问方式、适用场景 等进行分类。

线性结构（Linear Structures）

1. 顺序存储

列表（List）

• 可变（Mutable）：可以修改、添加或删除元素。
• 有序（Ordered）：元素按插入顺序存储，可通过索引访问。
• 支持重复元素：允许存储相同的值。
• 动态大小：可以随时增减元素。

my_list = [3, 1, 4, 1, 5, 9, 2] # 创建一个列表

# 1. append() - 在列表末尾添加元素
my_list.append(6) # [3, 1, 4, 1, 5, 9, 2, 6]

# 2. extend() - 用可迭代对象扩展列表
my_list.extend([7, 8, 9]) # [3, 1, 4, 1, 5, 9, 2, 6, 7, 8, 9]

# 3. insert() - 在指定索引处插入元素
my_list.insert(2, 42) # [3, 1, 42, 4, 1, 5, 9, 2, 6, 7, 8, 9]

# 4. remove() - 删除指定值（删除第一个匹配的值）
my_list.remove(1) # [3, 42, 4, 1, 5, 9, 2, 6, 7, 8, 9]

# 5. pop() - 删除并返回指定索引的元素（默认最后一个）
popped_element = my_list.pop() # 9 [3, 42, 4, 1, 5, 9, 2, 6, 7, 8]

# 6. index() - 返回元素第一次出现的索引
index_of_5 = my_list.index(5) # 4

# 7. count() - 统计元素出现次数
count_of_1 = my_list.count(1) # 1

# 8. sort() - 对列表进行排序
my_list.sort() # [1, 2, 3, 4, 5, 6, 7, 8, 9, 42]

# 9. reverse() - 反转列表
my_list.reverse() # [42, 9, 8, 7, 6, 5, 4, 3, 2, 1]

# 10. copy() - 复制列表
copy_list = my_list.copy() # [42, 9, 8, 7, 6, 5, 4, 3, 2, 1]

# 11. clear() - 清空列表
my_list.clear() # []

元组（Tuple）

• 不可变（Immutable）：创建后不能修改元素值。
• 有序：可以通过索引访问。
• 支持重复元素。
• 占用更少内存，比列表更快。

my_tuple = (3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5) # 创建一个元组

# 1. count() - 统计元素出现次数
count_of_5 = my_tuple.count(5)  # 3

# 2. index() - 返回元素第一次出现的索引
index_of_9 = my_tuple.index(9)  # 5

# 3. index()（指定范围） - 在索引 3 到 8 之间查找元素 5
index_of_5_in_range = my_tuple.index(5, 3, 9)  # 6

相比于 List，元组的不可变性使其缺少修改数据的方法，例如 append()、remove()、insert() 等操作。如果 需要修改数据，可以转换成 List，修改后再转换回 Tuple。

• 虽然 元组的方法只有 count() 和 index()。
• 但仍可以使用 +、*、切片、内置函数 等方式进行操作。

1. + 连接（拼接）

tuple1 = (1, 2, 3)
tuple2 = (4, 5, 6)
new_tuple = tuple1 + tuple2  # (1, 2, 3, 4, 5, 6)

2. * 复制

tuple1 = (1, 2, 3)
tuple2 = tuple1 * 2  # (1, 2, 3, 1, 2, 3)

字符串（String）

• 不可变（Immutable）：一旦创建，字符串的内容不可修改。
• 有序（Ordered）：字符串中的字符按顺序排列，可以通过索引访问。
• 支持重复字符：允许出现相同的字符。
• 固定大小：字符串的长度一旦确定，就不能再修改。

my_string = " Hello, Python!  "  # 创建一个字符串

# 1. upper() - 将所有字母转换为大写
upper_str = my_string.upper()  # " HELLO, PYTHON!  "

# 2. lower() - 将所有字母转换为小写
lower_str = my_string.lower()  # " hello, python!  "

# 3. capitalize() - 将第一个字符转换为大写，剩余字符为小写
capitalized_str = my_string.capitalize()  # " hello, python!  "

# 4. title() - 将每个单词的首字母转换为大写
title_str = my_string.title()  # " Hello, Python!  "

# 5. strip() - 移除两端的空白字符
stripped_str = my_string.strip()  # "Hello, Python!"

# 6. replace() - 替换字符串中的子字符串
replaced_str = my_string.replace("Python", "World")  # " Hello, World!  "

# 7. split() - 按空白字符拆分字符串
split_list = my_string.split()  # ['Hello,', 'Python!']

# 8. join() - 将列表元素连接为字符串
joined_str = "-".join(split_list)  # "Hello,-Python!"

# 9. find() - 查找子字符串的位置
index_of_python = my_string.find("Python")  # 8

# 10. count() - 统计子字符串出现的次数
count_python = my_string.count("Python")  # 1

# 11. index() - 查找子字符串的位置，未找到则抛出异常
index_of_world = my_string.index("World")  # 会抛出 ValueError: substring not found

# 12. startswith() - 判断字符串是否以 "Hello" 开头
starts_with_hello = my_string.startswith("Hello")  # True

# 13. endswith() - 判断字符串是否以 "!" 结尾
ends_with_exclamation = my_string.endswith("!")  # False

# 14. isalpha() - 判断字符串是否只包含字母
is_alpha = "abc".isalpha()  # True
is_alpha_num = "abc123".isalpha()  # False

# 15. isdigit() - 判断字符串是否只包含数字
is_digit = "12345".isdigit()  # True

# 16. isalnum() - 判断字符串是否只包含字母和数字
is_alnum = "abc123".isalnum()  # True

2. 线性存储

栈（Stack）

• 后进先出（LIFO, Last In First Out）
• 只能在一端进行插入和删除（称为栈顶）
• 操作类似于“堆叠的盘子”，后放的盘子要先取出

stack = []  # 创建一个空栈

# 1. 入栈
stack.append(1)
stack.append(2)
stack.append(3)
print("Stack after push:", stack)  # [1, 2, 3]

# 2. 查看栈顶元素（不删除）
top = stack[-1]
print("Top element:", top)  # 3

# 3. 出栈
popped = stack.pop()
print("Popped element:", popped)  # 3
print("Stack after pop:", stack)  # [1, 2]

# 4. 判断是否为空
print("Is stack empty?", not stack)  # False

# 5. 栈的大小
print("Stack size:", len(stack))  # 2

高效栈用 deque 实现。

from collections import deque

stack = deque()

stack.append(1)  # 入栈
stack.append(2)
stack.append(3)
print(stack.pop())  # 出栈，返回 3
print(stack)  # deque([1, 2])

队列（Queue）

• 先进先出（FIFO, First In First Out）
• 从队尾入队，从队首出队
• 操作类似于“排队买票”，先来的人先买票离开

queue = []  # 创建一个空队列

# 1. 入队
queue.append("A")
queue.append("B")
queue.append("C")
print("Queue after enqueue:", queue)  # ['A', 'B', 'C']

# 2. 查看队首元素（不删除）
front = queue[0]
print("Front element:", front)  # 'A'

# 3. 出队
dequeued = queue.pop(0)
print("Dequeued element:", dequeued)  # 'A'
print("Queue after dequeue:", queue)  # ['B', 'C']

# 4. 判断是否为空
print("Is queue empty?", not queue)  # False

# 5. 队列大小
print("Queue size:", len(queue))  # 2

高效队列用 deque 实现。

queue = deque()

queue.append("A")  # 入队
queue.append("B")
queue.append("C")
print(queue.popleft())  # 出队，返回 'A'
print(queue)  # deque(['B', 'C'])

双端队列（Deque，Double-Ended Queue）

• 两端插入和删除都是 $O(1)$ 的时间复杂度（比 list.pop(0) 快）
• 适用于队列和栈的双重需求

from collections import deque

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

# 1. 右端入队
dq.append(4) # deque([1, 2, 3, 4])

# 2. 左端入队
dq.appendleft(0) # deque([0, 1, 2, 3, 4])

# 3. 右端出队
dq.pop() # deque([0, 1, 2, 3])

# 4. 左端出队
dq.popleft() # deque([1, 2, 3])

# 5. 扩展队列（右侧）
dq.extend([4, 5]) # deque([1, 2, 3, 4, 5]) 

# 6. 扩展队列（左侧，逆序插入）
dq.extendleft([-1, -2]) # deque([-2, -1, 1, 2, 3, 4, 5])

# 7. 旋转（循环右移2位）
dq.rotate(2) # deque([4, 5, -2, -1, 1, 2, 3])

# 8. 旋转（循环左移1位）
dq.rotate(-1) # deque([5, -2, -1, 1, 2, 3, 4])

# 9. 反转队列
dq.reverse() # deque([4, 3, 2, 1, -1, -2, 5])

# 10. 清空队列
dq.clear() # deque([])

优先队列（Priority Queue）/ 最小堆

优先队列是一种 按照优先级顺序存储元素 的数据结构，Python 提供 heapq 模块来实现 最小堆（Min-Heap），默认情况下 最小值优先出队。

• 元素按照优先级排序，默认最小值优先
• 插入和删除的时间复杂度为 $O(logn)$
• 适用于任务调度、路径搜索（Dijkstra 算法）等

import heapq

# 创建一个空的优先队列（最小堆）
pq = []

# 1. 入队
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 4)
heapq.heappush(pq, 2)
print("After heappush:", pq)  # [1, 2, 4, 3] (最小值在前)

# 2. 出队（返回最小值）
min_item = heapq.heappop(pq)
print("heappop():", min_item)  # 1
print("After heappop:", pq)  # [2, 3, 4]

# 3. 批量建堆
nums = [9, 5, 7, 2, 6]
heapq.heapify(nums)  # 直接转换成最小堆
print("heapify():", nums)  # [2, 5, 7, 9, 6] (2 最小)

# 4. 先入队再出队最小值（比 heappush+heappop 效率高）
result = heapq.heappushpop(pq, 0)
print("heappushpop(0):", result)  # 0
print("After heappushpop:", pq)  # [2, 3, 4]

# 5. 获取前 n 个最大/最小元素
largest = heapq.nlargest(2, pq)
smallest = heapq.nsmallest(2, pq)
print("nlargest(2):", largest)  # [4, 3]
print("nsmallest(2):", smallest)  # [2, 3]

非线性结构（Non-Linear Structures）

• 数据 非顺序存储
• 适用于 查找、关联映射、层级关系

1. 哈希表

哈希表（Hash Table）/ 哈希映射（Hash Map）特点：

• 通过 键值对（key-value） 存储数据
• 平均 O(1) 的查找、插入和删除
• Python 的 dict 本质上是一个 哈希表

hash_map = {}  # 或 hash_map = dict()
hash_map["name"] = "Alice"
hash_map["age"] = 25
print(hash_map["name"])  # Alice
print(hash_map.get("age", "Not Found"))  # 25

字典（Dictionary）

• 键值对存储（Key-Value）：类似 JavaScript 的对象。
• 无序（Python 3.6 之前），有序（Python 3.7+）：Python 3.7+ 中，字典保持插入顺序。
• 键唯一：不能有重复的键。

完整示例：

my_dict = {"name": "Alice", "age": 25, "city": "New York"} # 创建一个字典

# 1. keys() - 获取所有键
print("keys():", my_dict.keys())  # dict_keys(['name', 'age', 'city'])

# 2. values() - 获取所有值
print("values():", my_dict.values())  # dict_values(['Alice', 25, 'New York'])

# 3. items() - 获取所有键值对
print("items():", my_dict.items())  
# dict_items([('name', 'Alice'), ('age', 25), ('city', 'New York')])

# 4. get() - 获取键的值（若不存在返回默认值）
print("get('age'):", my_dict.get("age"))  # 25
print("get('gender', 'Not Found'):", my_dict.get("gender", "Not Found"))  # 'Not Found'

# 5. pop() - 删除指定键并返回其值
age = my_dict.pop("age")
print("pop('age'):", age, my_dict)  # 25 {'name': 'Alice', 'city': 'New York'}

# 6. popitem() - 删除并返回最后插入的键值对（Python 3.7+）
last_item = my_dict.popitem() 
print("popitem():", last_item, my_dict)  # ('city', 'New York') {'name': 'Alice'}

# 7. update() - 合并另一个字典
my_dict.update({"gender": "Female", "age": 26}) # {'name': 'Alice', 'gender': 'Female', 'age': 26}

# 8. setdefault() - 获取 key 的值，若 key 不存在，则赋默认值
print("setdefault('city', 'Los Angeles'):", my_dict.setdefault("city", "Los Angeles")) # Los Angeles
print("After setdefault:", my_dict) # {'name': 'Alice', 'gender': 'Female', 'age': 26, 'city': 'Los Angeles'}

# 9. copy() - 复制字典
copy_dict = my_dict.copy()  # {'name': 'Alice', 'gender': 'Female', 'age': 26, 'city': 'Los Angeles'}

# 10. clear() - 清空字典
my_dict.clear() # {}

集合（Set）

• 无序（Unordered）：元素没有固定的顺序。
• 不允许重复元素（Unique）。
• 支持集合运算（交集、并集、差集等）。

完整示例：

# 创建集合
my_set = {1, 2, 3, 4, 5}
another_set = {3, 4, 5, 6, 7}

print(my_set & another_set)  # 交集 {3, 4, 5}
print(my_set | another_set)  # 并集 {1, 2, 3, 4, 5, 6, 7}

# 1. add() - 添加元素
my_set.add(6) # {1, 2, 3, 4, 5, 6}

# 2. remove() - 删除元素（不存在会报错）
my_set.remove(6) # {1, 2, 3, 4, 5}

# 3. discard() - 删除元素（不存在不会报错）
my_set.discard(10)  # 无影响 {1, 2, 3, 4, 5}

# 4. pop() - 随机删除一个元素
popped_item = my_set.pop() # 可能删除 1, 2, 3, 4, 5 中的任意一个
print("pop():", popped_item, my_set) # 1 {2, 3, 4, 5}  (结果可能不同)

# 5. clear() - 清空集合
my_set.clear() # set()

# 6. copy() - 复制集合
copy_set = another_set.copy() # {3, 4, 5, 6, 7}

# 7. update() - 用另一个集合扩展
my_set.update([1, 2, 3]) # {1, 2, 3}

# 8. union() - 并集
union_set = my_set.union(another_set) # {1, 2, 3, 4, 5, 6, 7}

# 9. intersection() - 交集
intersection_set = my_set.intersection(another_set) # {3}

# 10. difference() - 差集（存在于 my_set 但不存在于 another_set）
difference_set = my_set.difference(another_set) # {1, 2}

# 11. symmetric_difference() - 对称差集（只在其中一个集合中存在）
symmetric_diff_set = my_set.symmetric_difference(another_set) # {1, 2, 4, 5, 6, 7}

# 12. issubset() - 判断是否为子集
print("issubset(another_set):", {3}.issubset(my_set))  # True

# 13. issuperset() - 判断是否为超集
print("issuperset({3}):", my_set.issuperset({3}))  # True

# 14. isdisjoint() - 判断是否无交集
print("isdisjoint({10, 11}):", my_set.isdisjoint({10, 11}))  # True

2. 树结构

二叉树（Binary Tree）

二叉树 (Binary Tree)，是一种 每个节点最多有两个子节点 的数据结构。二叉树并 没有对节点值的排列做任何特殊限制。

二叉查找树 是二叉树的一种特例，它要求节点的值必须满足如下条件：

• 对于任何节点 node，node 的左子树中的所有节点值都比 node 的值小。
• 对于任何节点 node，node 的右子树中的所有节点值都比 node 的值大。

这种排列使得查找、插入和删除操作能以 $O(logn)$ 的时间复杂度进行（在树平衡的情况下）。

平衡二叉树（AVL 树 / 红黑树）

• 自平衡 的二叉搜索树，确保 O(log n) 查找、插入、删除
• Python sortedcontainers 库可以用于 平衡树结构
• Python 的 dict 和 set 底层使用哈希表，但 C++ 的 map/set 是 红黑树

sortedcontainers 是一个第三方库，提供了高效的排序容器，支持自动平衡。这个库实现了 平衡二叉树（如 AVL 树 / 红黑树） 的功能，允许 O(log n) 的插入、删除和查找操作。

from sortedcontainers import SortedList

# 创建一个 SortedList 对象
sorted_list = SortedList()

# 1. 向 SortedList 中添加元素
sorted_list.add(10)
sorted_list.add(5)
sorted_list.add(20)
sorted_list.add(15)

print("SortedList after adding elements:")
print(sorted_list)  # SortedList([5, 10, 15, 20])

# 2. 从 SortedList 中删除元素
sorted_list.remove(10)
print("SortedList after removing 10:")
print(sorted_list)  # SortedList([5, 15, 20])

# 3. 查找元素的索引位置
print("Index of 15:", sorted_list.index(15))  # 1

# 4. 查找元素的插入位置 (返回插入位置)
print("Bisect left for 12:", sorted_list.bisect_left(12))  # 1
print("Bisect right for 12:", sorted_list.bisect_right(12))  # 2

# 5. 判断元素是否存在
print("Does SortedList contain 15?", 15 in sorted_list)  # True
print("Does SortedList contain 10?", 10 in sorted_list)  # False

# 6. 获取指定索引的元素
print("Element at index 1:", sorted_list[1])  # 15

# 7. 弹出指定索引处的元素
popped_element = sorted_list.pop(1)
print("Popped element:", popped_element)  # 15
print("SortedList after pop:")
print(sorted_list)  # SortedList([5, 20])

# 8. 迭代遍历 SortedList
print("Iterating over SortedList:")
for item in sorted_list:
    print(item, end=" ")  # 5 20

# 9. 获取元素的个数
print("\nNumber of elements in SortedList:", len(sorted_list))  # 2

Trie（字典树 / 前缀树）

• 用于 高效的字符串查找（如自动补全、字典存储）
• 查找时间复杂度为 O(m)（m 是字符串长度）
• 适用于 搜索引擎、字典匹配、DNA 序列匹配

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = 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 = 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

trie = Trie()
trie.insert("hello")
print(trie.search("hello"))  # True
print(trie.search("hell"))   # False

3. 图（Graph）

• 由顶点（Nodes） 和 边（Edges） 组成
• 可以是 有向图 / 无向图，支持 加权 / 无权
• 广泛用于社交网络、地图导航、网络路由等

networkx 图论库

import networkx as nx
import matplotlib.pyplot as plt

# 创建一个无向图
G = nx.Graph()

# 1. 添加带权重的单条边
G.add_edge(1, 2, weight=4.2)

# 2. 添加带权重的多条边
G.add_edges_from([(2, 3, {'weight': 2.5}), (3, 4, {'weight': 7.1})])

# 3. 打印所有边及其属性（包括权重）
print("Edges with weights:", G.edges(data=True))  
# 输出: Edges with weights: [(1, 2, {'weight': 4.2}), (2, 3, {'weight': 2.5}), (3, 4, {'weight': 7.1})]

# 4. 获取指定边的权重
edge_weight = G[1][2]['weight']
print("Weight of edge (1, 2):", edge_weight)  # 输出: Weight of edge (1, 2): 4.2

# 5. 修改某条边的权重
G[1][2]['weight'] = 9.0
print("Updated weight of edge (1, 2):", G[1][2]['weight'])  # 输出: Updated weight of edge (1, 2): 9.0

# 6. 获取某条边的所有属性
edge_data = G.get_edge_data(1, 2)
print("Edge data for (1, 2):", edge_data)  # 输出: Edge data for (1, 2): {'weight': 9.0}

# 7. 获取所有带属性的边（包括权重）
print("All edges with data:", list(G.edges(data=True))) 
# 输出: All edges with data: [(1, 2, {'weight': 9.0}), (2, 3, {'weight': 2.5}), (3, 4, {'weight': 7.1})]

# 8. 获取图的最短路径（带权重）
shortest_path = nx.shortest_path(G, source=1, target=4, weight='weight')
print("Shortest path from 1 to 4:", shortest_path)  # 输出: Shortest path from 1 to 4: [1, 2, 3, 4]

# 9. 获取图的最短路径长度（带权重）
shortest_path_length = nx.shortest_path_length(G, source=1, target=4, weight='weight')
print("Shortest path length from 1 to 4:", shortest_path_length)  # 输出: Shortest path length from 1 to 4: 18.8

# 10. 绘制带权重的图
pos = nx.spring_layout(G)
labels = nx.get_edge_attributes(G, 'weight')  # 获取边的权重
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, font_size=15)
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
plt.show()

# 11. 获取图的直径
# 直径是图中最长的最短路径的长度
print("Diameter of the graph:", nx.diameter(G))  # 输出: Diameter of the graph: 2

# 12. 获取图的中心节点
print("Center of the graph:", nx.center(G))  # 输出: Center of the graph: [2, 3]

# 13. 获取节点的接近中心性
print("Closeness centrality of node 2:", nx.closeness_centrality(G, 2))  # 输出接近中心性

# 14. 获取节点的介数中心性
print("Betweenness centrality of node 2:", nx.betweenness_centrality(G)[2])  # 输出节点 2 的介数中心性

# 15. 获取 PageRank 值
print("PageRank values:", nx.pagerank(G))  # 输出节点的 PageRank 值

# 16. 获取子图
subgraph = G.subgraph([1, 2, 3])
print("Subgraph nodes:", subgraph.nodes())  # 输出: Subgraph nodes: [1, 2, 3]

并查集（Union-Find）

• 高效合并（Union）和查找（Find），用于动态连通性问题
• 主要用于 图的连通性检测、最小生成树（Kruskal）、网络连接等
• 路径压缩 + 按秩合并 可以优化到 O(α(n)) ≈ O(1)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(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):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootX] = rootY  # 合并集合

uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
print(uf.find(0) == uf.find(2))  # True（0 和 2 连接在一起）

特殊结构

跳表（Skip List）

• 通过 多层链表结构 提供 O(log n) 搜索，类似于平衡二叉树
• 建立 多层次的索引，允许在 每一层上进行跳跃式的查找
• 用于 高效的区间查询、排序数据结构
• Redis 的 有序集合（SortedSet） 采用 跳表实现

import random

class Node:  # 节点类 (Node)：每个节点有多个指针（表示跳跃层级）
    def __init__(self, value, level):
        self.value = value  # 节点值
        self.forward = [None] * (level + 1)  # forward[i]是指向第i层的下一个节点

class SkipList:  # 跳表类 (SkipList)：包含插入、查找和删除等操作
    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level  # 最大层数
        self.p = p  # 节点升层概率
        self.header = Node(None, self.max_level)  # 跳表头节点
        self.level = 0  # 当前跳表的层数

    def random_level(self):
        level = 0
        while random.random() < self.p and level < self.max_level:
            level += 1
        return level

    def insert(self, value):
        update = [None] * (self.max_level + 1)  # 记录查找路径
        current = self.header
        
        # 从跳表的最高层开始查找
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
        
        current = current.forward[0]
        
        # 如果找到了相同的值，则不插入
        if current and current.value == value:
            return
        
        # 否则插入新节点
        new_level = self.random_level()
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.header
            self.level = new_level
        
        new_node = Node(value, new_level)
        
        # 在各个层级插入新节点
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def search(self, value):
        current = self.header
        # 从最高层开始查找
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
        current = current.forward[0]
        
        return current if current and current.value == value else None

    def delete(self, value):
        update = [None] * (self.max_level + 1)
        current = self.header
        
        # 查找节点并更新路径
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
        
        current = current.forward[0]
        
        # 如果节点存在，删除节点
        if current and current.value == value:
            for i in range(self.level + 1):
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]
            
            # 如果最高层的节点没有节点，更新跳表的层数
            while self.level > 0 and not self.header.forward[self.level]:
                self.level -= 1

    def print_list(self):
        for i in range(self.level + 1):
            current = self.header.forward[i]
            print(f"Level {i}: ", end="")
            while current:
                print(current.value, end=" -> ")
                current = current.forward[i]
            print("None")

# 测试跳表
skip_list = SkipList()

# 插入元素
skip_list.insert(3)
skip_list.insert(6)
skip_list.insert(7)
skip_list.insert(9)
skip_list.insert(12)
skip_list.insert(19)
skip_list.insert(17)

# 打印跳表
skip_list.print_list()

# 查找元素
print(skip_list.search(6))  # <__main__.Node object at 0x7f856fc748b0>
print(skip_list.search(15))  # None

# 删除元素
skip_list.delete(6)
skip_list.print_list()

Bloom Filter（布隆过滤器）

• 高效存储和检测集合中的元素，但可能产生误判（可能会错误地认为某个元素存在）
• 适用于 去重、黑名单检测
• 不能 删除元素
• 用于 Google Chrome 安全浏览、Redis 缓存去重

• 每个元素通过多个哈希函数计算出多个哈希值，将这些哈希值对应的位数组位置标记为 True。
• 查询时，再次通过哈希函数计算出这些位置，若所有位置均为 True，则认为元素可能存在；若 有任一位置为 False，则元素肯定不存在。

import hashlib

class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size = size  # 位数组的大小
        self.num_hashes = num_hashes  # 哈希函数的数量
        self.bit_array = [False] * size  # 初始化位数组为False

    def _hash(self, item, seed):
        """ 基于给定种子的哈希函数 """
        return int(hashlib.md5((str(seed) + item).encode()).hexdigest(), 16) % self.size

    def add(self, item):
        """ 添加元素到布隆过滤器 """
        for i in range(self.num_hashes):
            index = self._hash(item, i)
            self.bit_array[index] = True

    def contains(self, item):
        """ 检查元素是否在布隆过滤器中 """
        for i in range(self.num_hashes):
            index = self._hash(item, i)
            if not self.bit_array[index]:  # 如果有任何一个哈希位置为False，则元素不在集合中
                return False
        return True

# 测试布隆过滤器
bloom = BloomFilter(size=1000, num_hashes=5)

# 添加元素
bloom.add("apple")
bloom.add("banana")
bloom.add("cherry")

# 查询元素
print(bloom.contains("apple"))  # True
print(bloom.contains("banana"))  # True
print(bloom.contains("orange"))  # False (可能为False, 但也可能是误判)

LRU 缓存（Least Recently Used Cache）

• 最近最少使用，即 使用频率最低的元素最先被淘汰
• Python functools.lru_cache 提供了现成实现
• 适用于缓存系统，如 CPU 缓存、网页缓存

示例（使用 OrderedDict 实现 LRU 缓存）：

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # 最近使用的移到末尾
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 移除最久未使用的元素

lru = LRUCache(2)
lru.put(1, "A")
lru.put(2, "B")
print(lru.get(1))  # "A"
lru.put(3, "C")  # 2 被移除
print(lru.get(2))  # -1（缓存淘汰）

总结：如何选择数据结构？

• 需要快速查询？ → 哈希表（dict）、集合（set）、Trie
• 需要顺序存储？ → list（动态数组）、tuple
• 需要按顺序处理？ → 栈（LIFO）、队列（FIFO）、优先队列
• 需要排序查找？ → 二叉搜索树（BST）、跳表
• 需要高效合并？ → 并查集
• 需要图结构？ → 邻接表、邻接矩阵
• 需要去重检测？ → 布隆过滤器
• 需要缓存管理？ → LRU 缓存