为什么数据结构重要？
刚学编程的时候，我以为”会写循环和函数”就够了。后来写了几千行代码之后才意识到，很多时候不是代码逻辑错了，是选了错误的数据结构。
比如，想频繁从中间插入元素，硬用数组就慢得离谱；想快速查一个东西，单链表就得从头扫到尾。
这些就是数据结构要解决的问题。
数组 vs 链表：内存里的两种组织方式
数组（Array）：连续存放
数组把元素紧密排列在一片连续的内存里。你可以通过下标一次性定位到任意位置，因为所有元素挨在一起，用基地址 + 偏移量一算就到了。
arr = [10, 20, 30, 40, 50]# 定位 arr[3]：基地址 + 3 × 元素大小| 操作 | 时间复杂度 | 原因 |
|---|---|---|
| 随机访问 | O(1) | 下标直接计算地址 |
| 尾部追加 | O(1) 均摊 | 有空间就塞进去，满了才扩容 |
| 中间插入 | O(n) | 后面所有元素都得往后挪 |
| 中间删除 | O(n) | 后面所有元素都得往前补 |
链表（Linked List）：链式分布
链表的每个节点飘在不同内存位置，靠指针串起来。每一个节点存着自己的数据和指向下一个节点的引用。
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next
class LinkedList: def __init__(self): self.head = None
def prepend(self, val): """头部插入 O(1)""" node = ListNode(val, self.head) self.head = node
def find(self, val): """查找 O(n)，只能从头扫""" cur = self.head while cur: if cur.val == val: return cur cur = cur.next return None
def delete(self, val): """删除 O(n)，找到目标才能删""" if not self.head: return if self.head.val == val: self.head = self.head.next return cur = self.head while cur.next: if cur.next.val == val: cur.next = cur.next.next return cur = cur.next| 操作 | 时间复杂度 | 原因 |
|---|---|---|
| 头部插入 | O(1) | 改一个指针就行 |
| 查找 | O(n) | 不能跳，只能一个接一个找 |
| 删除 | O(n) | 先找到要删的那个节点 |
两个结构的取舍一句话：需要按位置随机跳就用数组，需要频繁在头部增删就用链表。
栈（Stack）：LIFO 后进先出
栈就像一摞盘子——后放上去的先拿。只有一端开放，入栈（push）和出栈（pop）都在同一侧。
class Stack: def __init__(self): self.items = []
def push(self, val): self.items.append(val)
def pop(self): if self.is_empty(): raise IndexError("栈空") return self.items.pop()
def peek(self): if self.is_empty(): raise IndexError("栈空") return self.items[-1]
def is_empty(self): return len(self.items) == 0
def size(self): return len(self.items)三个操作都是 O(1)：push、pop、peek。
栈能干什么？ 浏览器的后退按钮、函数调用栈、括号匹配检查、表达式求值，都是栈。需要”先记住再回溯”的场景，栈就是你的工具。
队列（Queue）：FIFO 先进先出
队列像排队——先来的先服务。一端进入（enqueue），另一端出去（dequeue）。
和栈的区别很简单：栈是单端操作，队列两端各开一个口。
from collections import deque
class Queue: def __init__(self): self.items = deque()
def enqueue(self, val): self.items.append(val)
def dequeue(self): if self.is_empty(): raise IndexError("队列空") return self.items.popleft() # 从左侧弹出 = FIFO
def peek(self): if self.is_empty(): raise IndexError("队列空") return self.items[0]
def is_empty(self): return len(self.items) == 0
def size(self): return len(self.items)这里用 collections.deque 而不是 list，因为 pop(0) 得把后面所有元素前移（O(n)），而 deque.popleft() 是真正的 O(1)。
队列能干什么？ BFS 层序遍历、消息队列、任务调度、打印机缓冲队列。
树（Tree）：层级结构
普通二叉树
每个节点最多两个子节点，这就是二叉树。没有”左小右大”的约束。
二叉搜索树（BST）：左小右大
BST 有一个核心约束：左子树上所有节点 < 根节点 < 右子树上所有节点。这个约束让查找变成 O(log n)——每次比较砍掉一半候选。
四种遍历
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right
def preorder(root): """先序：根 → 左 → 右""" if not root: return [] return [root.val] + preorder(root.left) + preorder(root.right)
def inorder(root): """中序：左 → 根 → 右（BST 这里就是升序输出）""" if not root: return [] return inorder(root.left) + [root.val] + inorder(root.right)
def postorder(root): """后序：左 → 右 → 根""" if not root: return [] return postorder(root.left) + postorder(root.right) + [root.val]# BST 查找def bst_search(root, target): cur = root while cur: if cur.val == target: return cur elif target < cur.val: cur = cur.left else: cur = cur.right return None平衡的 BST 插入、查找、删除都是 O(log n)。不平衡就退化成链表 O(n)——这也解释了为什么后续搞出了 AVL 树、红黑树这些东西。
堆（Heap）：松散的半排序
堆是一棵完全二叉树，同时满足堆序性质：
- 最小堆：父节点 ≤ 子节点，堆顶永远是最小的
- 最大堆：父节点 ≥ 子节点，堆顶永远是最大的
堆的精妙之处在于，虽然它是完全二叉树，但实际用数组存储。父子关系靠下标公式算：
class MinHeap: def __init__(self): self.heap = []
def push(self, val): """插入 + 上浮 O(log n)""" self.heap.append(val) self._sift_up(len(self.heap) - 1)
def pop(self): """弹出堆顶 + 下沉 O(log n)""" if not self.heap: raise IndexError("堆空") if len(self.heap) == 1: return self.heap.pop() root = self.heap[0] self.heap[0] = self.heap.pop() # 末元素移到堆顶 self._sift_down(0) return root
def peek(self): if not self.heap: raise IndexError("堆空") return self.heap[0]
def _sift_up(self, i): while i > 0: p = (i - 1) // 2 if self.heap[p] <= self.heap[i]: break self.heap[p], self.heap[i] = self.heap[i], self.heap[p] i = p
def _sift_down(self, i): n = len(self.heap) while True: smallest = i l, r = 2 * i + 1, 2 * i + 2 if l < n and self.heap[l] < self.heap[smallest]: smallest = l if r < n and self.heap[r] < self.heap[smallest]: smallest = r if smallest == i: break self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i] i = smallestpush 和 pop 都是 O(log n)，peek 是 O(1)。堆顶永远是极值——这一点在优先队列、Top-K 问题、堆排序、Dijkstra 算法里都被反复用到。
各结构对比
| 结构 | 插入 | 删除 | 查找 | 空间 | 特点 |
|---|---|---|---|---|---|
| 数组 | O(n) 中间 / O(1) 尾部 | O(n) | O(1) 按索引 | O(n) | 内存连续 |
| 链表 | O(1) 头部 | O(n) | O(n) | O(n) | 动态插入快 |
| 栈 | O(1) | O(1) | — | O(n) | LIFO，只在一端操作 |
| 队列 | O(1) | O(1) | — | O(n) | FIFO，两端操作 |
| BST | O(log n) 平均 | O(log n) 平均 | O(log n) 平均 | O(n) | 左小右大，有序 |
| 堆 | O(log n) | O(log n) | O(1) 看顶 | O(n) | 极值永远在顶 |
没有万能的最优结构。算法的性能上限，往往在选存储结构的那一刻就已经定了。
练习题目
每个数据结构对应一道 LeetCode 经典题，建议按顺序刷：
| 结构 | 题目 | 链接 |
|---|---|---|
| 数组+链表 | 设计链表(707) | leetcode.cn |
| 栈 | 有效的括号(20) | leetcode.cn |
| 队列 | 用栈实现队列(232) | leetcode.cn |
| 二叉树 | 二叉树的中序遍历(94) | leetcode.cn |
| 堆 | 数组中的第K个最大元素(215) | leetcode.cn |
部分信息可能已经过时