DATA STRUCTURES

构建数字世界的基石 · 核心原理与可视化解析

1. 数组 Array

概念定义

数组是一种线性数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。它是最基础、最常用的数据结构。内存地址计算公式：addr[i] = base + i * size。

核心特点

随机访问： 支持通过下标 O(1) 时间复杂度访问元素，这是数组最大的优势。
内存连续： 对 CPU 缓存友好，利用空间局部性原理（Spatial Locality）提高访问效率。
大小固定： 静态数组创建时需指定容量，扩容成本较高（需复制所有数据 O(n)）。
动态数组： Python list、Java ArrayList 等实现自动扩容，通常扩容为 1.5~2 倍，摊销复杂度仍为 O(1)。
多维数组： 支持二维、三维等多维结构，常用于矩阵运算、图像处理等场景。

适用场景

需要频繁随机访问元素的场景（如索引查找）。
数据量相对固定，不频繁插入删除。
实现其他数据结构的底层存储（如堆、哈希表）。
缓冲区、环形队列的实现。

基本操作

Access(i): 读取索引 i 处的元素。
Update(i, val): 修改索引 i 处的元素。
Insert/Delete: 需移动后续元素，平均复杂度 O(n)。

// 连续内存空间与索引映射

Python Example

# 初始化数组
arr = [10, 25, 42, 8, 99]

# 随机访问 O(1)
print(arr[2])  # Output: 42

# 修改元素 O(1)
arr[0] = 5

# 插入元素 (需移动后续元素) O(n)
arr.insert(1, 15)  # [5, 15, 25, 42, 8, 99]

# 删除元素 O(n)
arr.pop(2)  # [5, 15, 42, 8, 99]

# 二维数组（矩阵）
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(matrix[1][2])  # 6

2. 链表 Linked List

概念定义

链表由一系列节点组成，每个节点包含数据域和指针域（指向下一个节点）。节点在内存中可以不连续存储。

链表类型

单向链表： 每个节点只有一个 next 指针，内存开销小。
双向链表： 节点含 prev 和 next 指针，可双向遍历，删除操作更高效。
循环链表： 尾节点指向头节点形成环，适合轮询调度。
跳表 Skip List： 多层索引的链表，查找效率达 O(log n)，Redis 的有序集合实现。

核心特点

动态扩容： 天然支持动态大小，无需预分配内存，适合数据量不确定的场景。
插入删除快： 已知位置时，仅需修改指针，操作复杂度为 O(1)。
随机访问慢： 必须从头遍历，查找复杂度 O(n)，不支持索引访问。
内存碎片： 节点分散存储，不利于 CPU 缓存，但避免了内存浪费。
额外空间： 每个节点需存储指针，空间开销比数组大。

适用场景

频繁插入删除操作的场景（如任务队列）。
LRU 缓存实现（双向链表 + 哈希表）。
多项式、大数运算。
图的邻接表表示。

基本操作

Insert(node): 修改指针指向即可。
Delete(node): 断开并重新连接指针。
Search(val): 线性遍历查找。

// 节点通过指针串联，非连续存储

Python Example (Node Class)

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

# 构建链表 A -> B -> C
head = Node("A")
node_b = Node("B")
node_c = Node("C")

head.next = node_b
node_b.next = node_c

# 遍历
current = head
while current:
    print(current.data)
    current = current.next

# 在头部插入 O(1)
def insert_at_head(head, data):
    new_node = Node(data)
    new_node.next = head
    return new_node

# 删除节点 O(1) (已知前一节点)
def delete_node(prev_node):
    if prev_node and prev_node.next:
        prev_node.next = prev_node.next.next

3. 栈 Stack

概念定义

栈是一种遵循“后进先出”（LIFO, Last In First Out）原则的线性数据结构。就像叠盘子一样，最后放上去的盘子最先被取走。

适用场景

函数调用栈（递归、保存返回地址）。
浏览器历史记录（后退功能）。
括号匹配检查、表达式求值。
撤销/重做功能（Undo/Redo）。
深度优先搜索（DFS）算法。
反转字符串、回文检测。

核心特点

访问限制： 只能访问栈顶元素，受限的线性结构。
实现方式： 可用数组或链表实现，数组实现更常见。
函数栈： 每次函数调用压栈（局部变量、返回地址），返回时出栈。

基本操作

Push(val): 入栈，元素加到栈顶。
Pop(): 出栈，移除并返回栈顶元素。
Peek(): 查看栈顶元素。

// LIFO: 元素 3 最后进入，最先出去

Python Example (List as Stack)

stack = []

# 入栈 Push
stack.append(1)
stack.append(2)
stack.append(3)

# 查看栈顶 Peek
print(stack[-1])  # 3

# 出栈 Pop
top = stack.pop() # 3
print(stack)      # [1, 2]

# 括号匹配示例
def is_valid_parentheses(s):
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}
    for char in s:
        if char in pairs:  # 左括号
            stack.append(char)
        else:  # 右括号
            if not stack or pairs[stack.pop()] != char:
                return False
    return len(stack) == 0

print(is_valid_parentheses("({[]})"))  # True

4. 队列 Queue

概念定义

队列是一种遵循“先进先出”（FIFO, First In First Out）原则的线性数据结构。就像排队买票，先来的人先服务。

适用场景

任务调度（打印机队列、CPU 调度）。
消息队列（RabbitMQ, Kafka, Redis Pub/Sub）。
广度优先搜索（BFS）算法。
缓冲区管理（IO 请求队列）。
事件循环（JavaScript Event Loop）。
多线程同步（生产者-消费者模式）。

核心特点

公平性： 先到先服务（FCFS），保证顺序处理。
实现方式： 数组实现需要移动元素（可用循环队列优化），链表实现更高效。
优先队列： 变体，元素按优先级出队，通常用堆实现。

基本操作

Enqueue(val): 入队，加到队尾。
Dequeue(): 出队，移除队头元素。

// FIFO: 从 Tail 进入，从 Head 离开

Python Example (collections.deque)

from collections import deque

queue = deque()

# 入队 Enqueue
queue.append("A")
queue.append("B")
queue.append("C")

# 出队 Dequeue
first = queue.popleft() # "A"
print(queue)            # deque(['B', 'C'])

# BFS 示例（层序遍历）
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        print(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

5. 哈希表 Hash Table

概念定义

哈希表（散列表）通过哈希函数 Hash(key) 将键映射到存储桶（Bucket）的索引，从而实现快速查找。好的哈希函数应该分布均匀、计算高效。

冲突解决方法

链地址法（Separate Chaining）： 每个桶维护链表或红黑树（Java 8+），冲突元素追加。
开放寻址法（Open Addressing）： 发生冲突时探测下一位置（线性探测、二次探测、双重哈希）。
再哈希法： 使用多个哈希函数计算新位置。
建立公共溢出区： 将冲突元素存储到单独的溢出表。

核心特点

极速查找： 平均时间复杂度 O(1)，最坏情况 O(n)（所有元素冲突）。
键值对存储： 适合存储映射关系，快速查找。
哈希冲突： 不同的 Key 可能映射到同一个 Index，负载因子（Load Factor）影响性能。
动态扩容： 负载因子超过阈值（如 0.75）时自动扩容，rehash 所有元素。
无序性： 元素存储无序，LinkedHashMap 可保持插入顺序。

适用场景

快速查找、去重（如统计单词频率）。
数据库索引（哈希索引）。
缓存实现（LRU、LFU）。
分布式系统（一致性哈希）。

基本操作

Put(key, value): 插入或更新键值对。
Get(key): 获取值。
Remove(key): 删除键值对。

// Key 经过 Hash 函数计算出 Index

Python Example (Dictionary)

# 创建哈希表
prices = {}

# 插入
prices["Apple"] = 5
prices["Banana"] = 3

# 查找 O(1)
if "Apple" in prices:
    print(prices["Apple"])  # 5

# 删除
del prices["Banana"]

# 单词频率统计
def word_frequency(text):
    freq = {}
    for word in text.split():
        freq[word] = freq.get(word, 0) + 1
    return freq

text = "hello world hello python"
print(word_frequency(text))
# {'hello': 2, 'world': 1, 'python': 1}

6. 树 Tree

概念定义

树是一种分层数据的抽象模型。二叉树（Binary Tree）是每个节点最多有两个子节点的树结构。

树的类型

二叉搜索树 BST： 左子节点 < 根节点 < 右子节点，平均 O(log n) 查找，最坏退化为 O(n)。
AVL 树： 严格平衡的二叉搜索树，任意节点左右子树高度差 ≤ 1，查找最稳定。
红黑树： 弱平衡树，Java TreeMap/TreeSet、Linux 内核底层实现，插入删除性能优于 AVL。
B 树： 多路搜索树，节点可有多个子节点，数据库索引（InnoDB）。
B+ 树： B 树的变体，叶子节点形成链表，MySQL 索引首选，范围查询高效。
字典树 Trie： 见第 10 节。
线段树： 用于区间查询（区间和、最大值），竞赛常用。
树状数组（Fenwick Tree）： 轻量级线段树，单点更新与前缀和查询。

核心特点

层级关系： 根节点、父节点、子节点、叶子节点。
递归结构： 每个子树也是一棵树。
应用广泛： 文件系统、DOM 树、数据库索引（B+树）。

遍历方式

Pre-order: 根 -> 左 -> 右（用于复制树结构）
In-order: 左 -> 根 -> 右（BST 中得到有序序列）
Post-order: 左 -> 右 -> 根（用于删除树）
Level-order: 层序遍历，使用队列实现

// 二叉树结构：Root, Left Child, Right Child

Python Example (Binary Tree Node)

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

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
#      1
#     / \
#    2   3
#   / \
#  4   5

# 中序遍历（左-根-右）
def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=' ')
        inorder(root.right)

inorder(root)  # 4 2 5 1 3

7. 图 Graph

概念定义

图由顶点（Vertex）和边（Edge）组成，表示多对多的关系。分为有向图和无向图，带权图和无权图。

核心算法

BFS 广度优先： 使用队列，适合无权图最短路径、层序遍历。
DFS 深度优先： 使用栈/递归，适合连通性检测、拓扑排序、环检测。
Dijkstra： 单源最短路径算法（非负权边），使用优先队列优化。
Bellman-Ford： 支持负权边的最短路径算法，可检测负权环。
Floyd-Warshall： 全源最短路径，动态规划实现。
Prim / Kruskal： 最小生成树算法（MST）。
拓扑排序： 有向无环图（DAG）的线性排序，课程依赖、任务调度。
强连通分量： Tarjan、Kosaraju 算法。

适用场景

社交网络（好友关系）。
地图导航（最短路径）。
网络拓扑。

表示方法

邻接矩阵： 二维数组，查询快，耗内存。
邻接表： 链表数组，省内存，适合稀疏图。

// 复杂网络结构：节点互联

Python Example (Adjacency List)

graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C"]
}

# 查找 A 的邻居
print(graph["A"]) # ['B', 'C']

# DFS 递归实现
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=' ')
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

dfs(graph, "A")  # A B C D

8. 堆 Heap

概念定义

堆是一种特殊的完全二叉树，满足堆属性：父节点的值总是大于（最大堆）或小于（最小堆）其子节点的值。堆通常用数组实现。

核心特点

完全二叉树： 除最后一层外所有层都被填满。
堆序性质： 最大堆根节点最大，最小堆根节点最小。
高效操作： 插入和删除的时间复杂度为 O(log n)。
数组表示： 节点 i 的左子节点为 2i+1，右子节点为 2i+2。

适用场景

优先队列的实现（任务调度）。
堆排序算法。
Top K 问题（找最大/最小的K个元素）。
Dijkstra 最短路径算法。

基本操作

Insert(val): 插入元素并上浮调整 O(log n)。
Extract-Max/Min: 取出堆顶并下沉调整 O(log n)。
Peek(): 查看堆顶元素 O(1)。
Heapify: 将数组转化为堆 O(n)。

// 最大堆：父节点 >= 子节点

Python Example (heapq - Min Heap)

import heapq

# 创建最小堆
min_heap = []
heapq.heappush(min_heap, 50)
heapq.heappush(min_heap, 30)
heapq.heappush(min_heap, 70)
heapq.heappush(min_heap, 10)

# 查看堆顶（最小值）
print(min_heap[0])  # 10

# 弹出最小值
smallest = heapq.heappop(min_heap)  # 10

# 创建最大堆（取负值技巧）
max_heap = []
heapq.heappush(max_heap, -90)
heapq.heappush(max_heap, -80)
largest = -heapq.heappop(max_heap)  # 90

9. 双端队列 Deque

概念定义

双端队列（Double-Ended Queue）是一种允许在两端进行插入和删除操作的线性数据结构。它结合了栈和队列的特点。

核心特点

双向操作： 头尾均支持 O(1) 插入和删除。
灵活性高： 可当作栈或队列使用。
实现方式： 通常用双向链表或循环数组实现。

适用场景

滑动窗口最大值/最小值问题。
工作窃取调度算法。
浏览器历史记录（前进/后退）。
撤销/重做功能实现。

基本操作

push_front(val): 头部插入。
push_back(val): 尾部插入。
pop_front(): 头部删除。
pop_back(): 尾部删除。

// 双端操作：两端均可进出

Python Example (collections.deque)

from collections import deque

dq = deque()

# 两端插入
dq.append("C")       # 右端插入
dq.appendleft("B")   # 左端插入
dq.append("D")
dq.appendleft("A")
# deque: ['A', 'B', 'C', 'D']

# 两端删除
left = dq.popleft()  # 'A'
right = dq.pop()     # 'D'
# deque: ['B', 'C']

# 滑动窗口最大值示例
def max_sliding_window(nums, k):
    dq = deque()  # 存储索引
    result = []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

10. 前缀树 Trie

概念定义

Trie（发音 "try"），又称前缀树或字典树，是一种用于高效存储和检索字符串键的树形数据结构。每条从根到节点的路径代表一个前缀。

核心特点

前缀共享： 相同前缀的单词共享节点，节省空间。
快速查找： 查找时间复杂度 O(m)，m 为字符串长度。
有序性： 可按字典序遍历所有字符串。
空间换时间： 通过多叉树结构换取查找效率。

适用场景

自动补全（搜索引擎建议）。
拼写检查器。
IP 路由表（最长前缀匹配）。
词频统计。

基本操作

Insert(word): 插入单词 O(m)。
Search(word): 精确查找 O(m)。
StartsWith(prefix): 前缀匹配 O(m)。

// 存储: "app", "apple", "api", "bat"

Python Example (Trie Implementation)

class TrieNode:
    def __init__(self):
        self.children = {}  # 子节点字典
        self.is_end = False # 标记单词结尾

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        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: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end
    
    def startsWith(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None
    
    def _find_node(self, prefix: str):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

# 使用示例
trie = Trie()
trie.insert("apple")
trie.insert("app")
print(trie.search("app"))      # True
print(trie.startsWith("ap"))   # True

11. 复杂度对比 Complexity

时间复杂度总览

以下表格汇总了各数据结构核心操作的平均时间复杂度，帮助你在不同场景下做出最优选择。

数据结构	访问	查找	插入	删除	空间复杂度
数组 Array	O(1)	O(n)	O(n)	O(n)	O(n)
链表 Linked List	O(n)	O(n)	O(1)*	O(1)*	O(n)
栈 Stack	O(n)	O(n)	O(1)	O(1)	O(n)
队列 Queue	O(n)	O(n)	O(1)	O(1)	O(n)
哈希表 Hash Table	N/A	O(1)	O(1)	O(1)	O(n)
二叉搜索树 BST	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
堆 Heap	O(1)*	O(n)	O(log n)	O(log n)	O(n)
Trie 前缀树	N/A	O(m)	O(m)	O(m)	O(n·m)

注释说明

O(1)*: 链表在已知位置时为 O(1)，否则需先遍历。
O(1)* (堆): 堆的访问指获取堆顶元素。
O(m): m 为字符串长度，与元素数量 n 无关。
BST 最坏情况: 退化为链表时复杂度变为 O(n)。
颜色标识：最优 O(1) / 良好 O(log n) / 一般 O(n)