常用数据结构及复杂度在软件开发中数据结构是组织和存储数据的方式它直接影响程序的性能。理解常见数据结构及其时间复杂度Big O 表示法是每个工程师的必备技能。本文将从实战角度出发通过大量代码示例深入剖析数组、链表、栈、队列、哈希表、树和图等核心数据结构并分析它们在插入、删除、查找等操作下的复杂度。### 一、数组Array数组是最基础的数据结构它使用连续的内存空间存储一组相同类型的元素。其核心优势在于通过索引访问元素时时间复杂度为 O(1)但插入和删除操作特别是中间位置会导致元素移动复杂度为 O(n)。#### 实战示例Python 数组操作python# 示例数组的插入、删除和访问def array_operations(): arr [10, 20, 30, 40, 50] print(原始数组:, arr) # 访问第三个元素 (索引2) - O(1) element arr[2] print(f访问索引2的元素: {element}) # 输出: 30 # 在索引1插入元素25 - O(n) arr.insert(1, 25) print(插入25后:, arr) # 输出: [10, 25, 20, 30, 40, 50] # 删除索引3的元素 - O(n) arr.pop(3) print(删除索引3后:, arr) # 输出: [10, 25, 20, 40, 50] # 查找元素20 - O(n) index arr.index(20) print(f元素20的索引: {index}) # 输出: 2array_operations()复杂度总结- 访问O(1)- 查找O(n)- 插入末尾O(1)- 插入中间O(n)- 删除末尾O(1)- 删除中间O(n)### 二、链表Linked List链表通过节点Node之间的指针连接数据不要求连续内存。单链表的插入和删除操作在已知位置时效率高O(1)但查找元素需要遍历O(n)。#### 实战示例Python 单链表实现pythonclass Node: def __init__(self, data): self.data data self.next Noneclass LinkedList: def __init__(self): self.head None # 在链表末尾插入元素 - O(n) def append(self, data): new_node Node(data) if not self.head: self.head new_node return current self.head while current.next: current current.next current.next new_node # 在链表头部插入元素 - O(1) def prepend(self, data): new_node Node(data) new_node.next self.head self.head new_node # 删除指定元素 - O(n) def delete(self, data): if not self.head: return if self.head.data data: self.head self.head.next return current self.head while current.next and current.next.data ! data: current current.next if current.next: current.next current.next.next def display(self): elements [] current self.head while current: elements.append(current.data) current current.next print(链表内容:, elements)# 测试链表操作ll LinkedList()ll.append(10)ll.append(20)ll.prepend(5) # 头部插入ll.display() # 输出: [5, 10, 20]ll.delete(10)ll.display() # 输出: [5, 20]复杂度总结- 访问O(n)- 查找O(n)- 插入头部/已知位置O(1)- 插入末尾O(n)- 删除已知位置O(1)- 删除查找后删除O(n)### 三、栈Stack和队列Queue栈是后进先出LIFO结构常用于函数调用和撤销操作队列是先进先出FIFO结构常用于任务调度和缓冲区。#### 实战示例Python 实现栈和队列pythonfrom collections import deque# 栈实现class Stack: def __init__(self): self.items [] def push(self, item): # O(1) self.items.append(item) def pop(self): # O(1) if not self.is_empty(): return self.items.pop() return None def peek(self): # O(1) if not self.is_empty(): return self.items[-1] return None def is_empty(self): return len(self.items) 0# 队列实现使用deque保证效率class Queue: def __init__(self): self.items deque() def enqueue(self, item): # O(1) self.items.append(item) def dequeue(self): # O(1) if not self.is_empty(): return self.items.popleft() return None def front(self): # O(1) if not self.is_empty(): return self.items[0] return None def is_empty(self): return len(self.items) 0# 测试栈stack Stack()stack.push(1)stack.push(2)stack.push(3)print(栈弹出:, stack.pop()) # 输出: 3# 测试队列queue Queue()queue.enqueue(1)queue.enqueue(2)queue.enqueue(3)print(队列出队:, queue.dequeue()) # 输出: 1复杂度总结- 栈push O(1), pop O(1), peek O(1)- 队列enqueue O(1), dequeue O(1), front O(1)### 四、哈希表Hash Table哈希表通过哈希函数将键映射到存储位置以实现平均 O(1) 的查找、插入和删除操作。但在处理哈希冲突时如链地址法最坏情况可能退化为 O(n)。#### 实战示例Python 字典操作python# Python 内置字典就是哈希表实现def hash_table_demo(): user_scores { Alice: 95, Bob: 87, Charlie: 92 } # 插入 - O(1) 平均 user_scores[David] 88 print(插入David后:, user_scores) # 访问 - O(1) 平均 alice_score user_scores[Alice] print(fAlice的分数: {alice_score}) # 输出: 95 # 删除 - O(1) 平均 del user_scores[Bob] print(删除Bob后:, user_scores) # 查找 - O(1) 平均 if Charlie in user_scores: print(Charlie在字典中) # 冲突处理演示链地址法 # 当两个键哈希值相同时Python使用开放寻址法处理冲突 # 这里仅展示概念 custom_table {} custom_table[key1] 1 custom_table[key2] 2 # 可能发生冲突但Python自动处理 print(自定义哈希表:, custom_table)hash_table_demo()复杂度总结- 插入平均 O(1)最坏 O(n)- 删除平均 O(1)最坏 O(n)- 查找平均 O(1)最坏 O(n)### 五、树Tree树是一种非线性结构二叉搜索树BST在平衡状态下查找、插入和删除的时间复杂度为 O(log n)。但若不平衡可能退化为 O(n)。#### 实战示例Python 二叉搜索树pythonclass TreeNode: def __init__(self, val): self.val val self.left None self.right Noneclass BinarySearchTree: def __init__(self): self.root None # 插入 - O(log n) 平均O(n) 最坏 def insert(self, val): if not self.root: self.root TreeNode(val) return self._insert_recursive(self.root, val) def _insert_recursive(self, node, val): if val node.val: if node.left: self._insert_recursive(node.left, val) else: node.left TreeNode(val) else: if node.right: self._insert_recursive(node.right, val) else: node.right TreeNode(val) # 查找 - O(log n) 平均O(n) 最坏 def search(self, val): return self._search_recursive(self.root, val) def _search_recursive(self, node, val): if not node or node.val val: return node if val node.val: return self._search_recursive(node.left, val) return self._search_recursive(node.right, val) # 中序遍历 - O(n) def inorder_traversal(self): result [] self._inorder(self.root, result) return result def _inorder(self, node, result): if node: self._inorder(node.left, result) result.append(node.val) self._inorder(node.right, result)# 测试BSTbst BinarySearchTree()values [50, 30, 70, 20, 40, 60, 80]for v in values: bst.insert(v)print(中序遍历:, bst.inorder_traversal()) # 输出: [20, 30, 40, 50, 60, 70, 80]found bst.search(40)print(查找40:, found.val if found else 未找到) # 输出: 40复杂度总结- 插入平衡树O(log n)- 删除平衡树O(log n)- 查找平衡树O(log n)- 遍历O(n)### 六、图Graph图由顶点和边组成常用邻接矩阵或邻接表表示。深度优先搜索DFS和广度优先搜索BFS的时间复杂度为 O(V E)其中 V 是顶点数E 是边数。#### 实战示例Python 图实现与遍历pythonfrom collections import defaultdict, dequeclass Graph: def __init__(self): self.graph defaultdict(list) # 邻接表 # 添加边 - O(1) def add_edge(self, u, v): self.graph[u].append(v) self.graph[v].append(u) # 无向图 # 广度优先搜索 - O(V E) def bfs(self, start): visited set() queue deque([start]) visited.add(start) result [] while queue: vertex queue.popleft() result.append(vertex) for neighbor in self.graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return result # 深度优先搜索 - O(V E) def dfs(self, start): visited set() result [] self._dfs_recursive(start, visited, result) return result def _dfs_recursive(self, vertex, visited, result): visited.add(vertex) result.append(vertex) for neighbor in self.graph[vertex]: if neighbor not in visited: self._dfs_recursive(neighbor, visited, result)# 测试图g Graph()g.add_edge(0, 1)g.add_edge(0, 2)g.add_edge(1, 2)g.add_edge(1, 3)g.add_edge(2, 4)print(BFS从0开始:, g.bfs(0)) # 输出: [0, 1, 2, 3, 4]print(DFS从0开始:, g.dfs(0)) # 输出: [0, 1, 2, 3, 4]复杂度总结- 添加边O(1)- BFSO(V E)- DFSO(V E)### 总结本文从实战角度出发通过 Python 代码示例详细介绍了数组、链表、栈、队列、哈希表、树和图这七种常用数据结构。每种数据结构都有其独特的适用场景和时空复杂度-数组适合快速随机访问但插入和删除慢适用于静态数据。-链表适合频繁插入和删除但查找慢适用于动态场景。-栈和队列是线性结构的特例适用于特定顺序的数据处理。-哈希表提供近乎常数时间的操作是键值对存储的首选。-树在平衡时提供对数级操作适用于需要有序数据的场景。-图适用于复杂关系建模遍历算法是核心操作。理解这些数据结构的复杂度是编写高效代码的基础。在实际开发中应根据具体需求如数据量、操作频率、内存限制选择合适的数据结构甚至组合使用以达到最佳性能。