数据结构

八大基础数据结构速查，每节包含：核心特点 + 操作复杂度 + 关键代码 + 适用场景。

---

速查总表

数据结构	访问	查找	插入	删除	特点
数组	O(1)	O(n)	O(n)	O(n)	随机访问快，增删慢
链表	O(n)	O(n)	O(1)*	O(1)*	增删快，访问慢
栈	O(n)	O(n)	O(1)	O(1)	LIFO，只操作栈顶
队列	O(n)	O(n)	O(1)	O(1)	FIFO，一进一出
哈希表	—	O(1)	O(1)	O(1)	键值映射，最坏 O(n)
二叉搜索树	O(log n)	O(log n)	O(log n)	O(log n)	有序，平衡时高效
堆	O(1)**	—	O(log n)	O(log n)	快速取极值
图	—	O(V+E)	O(1)	O(E)	表示关系网络

* 已知前驱节点时 ** 只能 O(1) 访问堆顶

---

一、数组 Array

连续内存存储相同类型元素，通过下标直接访问。

arr = [1, 2, 3, 4]

arr[0]          # 访问  O(1)
arr.append(5)   # 末尾追加  O(1) 均摊
arr.insert(2, 10)  # 中间插入  O(n)
arr.pop()       # 删除末尾  O(1)
arr.pop(0)      # 删除头部  O(n)

适用场景：随机访问频繁、数据量已知或变化小（矩阵运算、固定大小缓冲区）。

---

二、链表 Linked List

节点由数据 + 指针组成，内存非连续，增删高效但无法随机访问。

类型	说明
单链表	每个节点指向下一个
双链表	节点同时有前驱和后继指针
循环链表	尾节点指向头节点

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 创建链表：1 → 2 → 3
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

# 在节点 2 后插入 4（O(1)，已知前驱）
node = head.next
new_node = ListNode(4)
new_node.next = node.next
node.next = new_node        # 1 → 2 → 4 → 3

# 删除节点 4
node.next = node.next.next  # 1 → 2 → 3

适用场景：频繁插入删除（LRU 缓存）、实现栈和队列。

---

三、栈 Stack

后进先出（LIFO），只在栈顶操作。

stack = []
stack.append(1)   # push
stack.append(2)   # push
top = stack[-1]   # peek → 2
stack.pop()       # pop  → 2

适用场景：函数调用栈、括号匹配、表达式求值、撤销/重做。

---

四、队列 Queue

先进先出（FIFO），一端入队，另一端出队。

推荐：collections.deque

from collections import deque

queue = deque()
queue.append(1)    # 入队 O(1)
queue.append(2)
queue.popleft()    # 出队 O(1) → 1
queue[0]           # 查看队首，不出队

链表实现（最优）

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

class Queue:
    def __init__(self):
        self.head = self.tail = None
        self._size = 0

    def enqueue(self, value):       # 入队 O(1)
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self._size += 1

    def dequeue(self):              # 出队 O(1)
        if not self.head:
            raise IndexError("Queue is empty")
        val = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self._size -= 1
        return val

    def peek(self):
        if not self.head:
            raise IndexError("Queue is empty")
        return self.head.value

    def __len__(self):
        return self._size

实现方式	入队	出队	说明
collections.deque	O(1)	O(1)	推荐，内置高效
链表实现	O(1)	O(1)	无额外依赖
列表（insert(0,x)）	O(n)	O(1)	不推荐，入队性能差

变种：双端队列（两端均可操作）、优先队列（按优先级出队，用堆实现）。

适用场景：任务调度、消息队列、BFS。

---

五、哈希表 Hash Table

通过哈希函数将键映射到存储位置，实现近 O(1) 的增删查。

# Python 字典即哈希表
h = {}
h["apple"] = 1          # 插入/更新  O(1)
h.get("apple")          # 查找  O(1)，不存在返回 None
del h["apple"]          # 删除  O(1)
"banana" in h           # 判断是否存在  O(1)

哈希冲突解决

方法	思路	代表
链地址法	每个桶存链表，冲突元素追加到链表	Python dict、Java HashMap（链表→红黑树）
开放地址法	冲突时线性/二次探测找下一个空槽	Python set（部分实现）

为什么哈希表通常是 O(1)？

好的哈希函数将 key 均匀分散到各个桶；当负载因子（元素数/桶数）超过阈值（如 0.75）时触发扩容（Rehashing），保持链表长度极短。Java HashMap 链表长度超 8 还会转为红黑树，将最坏情况从 O(n) 降到 O(log n)。

适用场景：快速查找（数据库索引、缓存）、词频统计、去重。

---

六、二叉树 Binary Tree

每个节点最多有左、右两个子节点。

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

# 构建树
root = TreeNode(1)
root.left  = TreeNode(2)
root.right = TreeNode(3)

遍历方式

遍历	顺序	用途
前序	根 → 左 → 右	复制/序列化树
中序	左 → 根 → 右	BST 得到有序序列
后序	左 → 右 → 根	删除树、计算目录大小
层序	按层从上到下	最短路径、BFS

def inorder(root):          # 中序遍历（递归）
    if not root:
        return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

特殊类型

类型	特点
二叉搜索树 BST	左子树 < 根 < 右子树，查找 O(log n)
AVL 树	自平衡，任意节点左右子树高度差 ≤ 1
红黑树	近似平衡，插删比 AVL 快，Java TreeMap 使用
B/B+ 树	多路平衡，MySQL 索引的底层结构

适用场景：文件系统、表达式解析、数据库索引（B+树）。

---

七、堆 Heap

完全二叉树，满足堆序性：最大堆每个父节点 ≥ 子节点，最小堆反之。

最大堆示例：         数组表示：[30, 20, 10, 15, 5]
     30
    /  \
   20   10          父节点(i)  = (i-1) // 2
  /  \              左子节点(i) = 2*i + 1
 15   5             右子节点(i) = 2*i + 2

核心操作

操作	复杂度	说明
插入	O(log n)	末尾插入后上浮（sift up）
删除堆顶	O(log n)	末尾元素移至堆顶后下沉（sift down）
建堆（Floyd）	O(n)	从最后一个非叶子节点倒序下沉
查看堆顶	O(1)	直接取 heap[0]

import heapq

# Python 内置最小堆
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappop(heap)     # → 1（最小值）

# 模拟最大堆：插入负值
heapq.heappush(heap, -5)
-heapq.heappop(heap)    # → 5

# 将无序数组直接建堆（O(n)，比逐个插入的 O(n log n) 更快）
arr = [4, 1, 7, 3, 9, 2]
heapq.heapify(arr)      # arr 变为合法最小堆

堆 ≠ JVM 堆

• 数据结构的堆：完全二叉树，用于优先队列、Top K 问题
• JVM 的堆：内存区域，存放 Java 对象，与树结构无关

手动实现最大堆

class MaxHeap:

    def __init__(self):
        self.heap = []

    def insert(self, value):
        self.heap.append(value)
        self._shift_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            return None
        max_val = self.heap[0]          # 保存堆顶（最大值）
        self.heap[0] = self.heap[-1]    # 末尾元素移到堆顶
        self.heap.pop()
        self._shift_down(0)
        return max_val

    def build_heap(self, arr):
        """Floyd 建堆：O(n)"""
        self.heap = arr.copy()
        for i in range((len(self.heap) - 1) // 2, -1, -1):
            self._shift_down(i)

    def _shift_up(self, idx):
        while idx > 0:
            parent = (idx - 1) // 2
            if self.heap[idx] > self.heap[parent]:
                self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
                idx = parent
            else:
                break

    def _shift_down(self, idx):
        n = len(self.heap)
        while True:
            left, right, largest = 2*idx+1, 2*idx+2, idx
            if left  < n and self.heap[left]  > self.heap[largest]: largest = left
            if right < n and self.heap[right] > self.heap[largest]: largest = right
            if largest != idx:
                self.heap[idx], self.heap[largest] = self.heap[largest], self.heap[idx]
                idx = largest
            else:
                break

# 测试
h = MaxHeap()
for v in [3, 1, 5, 2]:
    h.insert(v)
print(h.heap)       # [5, 2, 3, 1]
print(h.pop())      # 5
print(h.heap)       # [3, 2, 1]

适用场景：优先队列、Top K 问题、堆排序、Dijkstra 算法。

---

八、图 Graph

由**顶点（Vertex）和边（Edge）**组成，描述实体间的关系。

类型	说明	例子
有向图	边有方向（A→B）	网页链接、任务依赖
无向图	边无方向（A-B）	社交好友关系
带权图	边有权重	地图导航（距离/耗时）

两种存储方式

邻接表（稀疏图推荐）

# 空间 O(V+E)，遍历邻居快
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}

邻接矩阵（稠密图/快速判断边）

# 空间 O(V²)，判断两点是否相邻 O(1)
class Graph:
    def __init__(self, n):
        self.matrix = [[0] * n for _ in range(n)]

    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        self.matrix[v][u] = weight   # 无向图；有向图删此行

    def has_edge(self, u, v):
        return self.matrix[u][v] != 0

	邻接矩阵	邻接表
空间	O(V²)	O(V+E)
判断边是否存在	O(1)	O(V)
遍历所有邻居	O(V)	O(degree)
适用	稠密图	稀疏图（实际更常用）

Dijkstra 最短路径

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]   # (距离, 节点)

    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:  # 已找到更短路径，跳过
            continue
        for neighbor, weight in graph[node].items():
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return dist

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

适用场景：社交网络分析、导航最短路径、PageRank、任务拓扑排序。