数据结构[Python版]

1. 双向链表

• 双向遍历
• 插入/删除操作高效

插入时间复杂度O(1)，给定Node删除时间复杂度为O(1)，查询复杂度O(n)

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

class DoublyLinkedList:
    def __init__(self):
        # 初始化头尾虚拟节点并互连
        self.dummy_head = Node()  
        self.dummy_tail = Node()  
        self.dummy_head.next = self.dummy_tail
        self.dummy_tail.prev = self.dummy_head
        self.size = 0  # 实际节点数量，不计虚拟节点

    def _insert_between(self, prev_node, next_node, value):
        """在prev_node和next_node之间插入新节点"""
        new_node = Node(value)
        new_node.prev = prev_node
        new_node.next = next_node
        prev_node.next = new_node
        next_node.prev = new_node
        self.size += 1
        return new_node

    def append_left(self, value):
        """在链表头部插入（dummy_head后）"""
        self._insert_between(self.dummy_head, self.dummy_head.next, value)

    def append_right(self, value):
        """在链表尾部插入（dummy_tail前）"""
        self._insert_between(self.dummy_tail.prev, self.dummy_tail, value)

    def remove(self, value):
        """删除第一个匹配值的节点"""
        current = self.dummy_head.next
        while current != self.dummy_tail:
            if current.value == value:
                # 断开当前节点连接
                current.prev.next = current.next
                current.next.prev = current.prev
                self.size -= 1
                return True
            current = current.next
        return False

    def __str__(self):
        """可视化链表结构"""
        res = []
        current = self.dummy_head.next
        while current != self.dummy_tail:
            res.append(str(current.value))
            current = current.next
        return " <-> ".join(res) if res else "Empty List"

例题：

• LRU缓存 146. LRU 缓存 - 力扣（LeetCode）

2. 单调栈

寻找下一个更大/更小元素

• 构造一个递减栈，如果当前元素大于stk[-1]， 弹出栈顶，用于寻找下一个更大的元素
• 构造一个递增栈，如果当前元素小于stk[-1]， 弹出栈顶，用于寻找下一个更小的元素

# 递减单调栈
def next_greater_element(nums):
    stack = []
    result = [-1] * len(nums)
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    return result

例题：

• 每日温度问题 739. 每日温度 - 力扣（LeetCode）
• 柱状图最大矩形 84. 柱状图中最大的矩形 - 力扣（LeetCode）

3. 单调队列

O(1)获得滑动窗口最值

以滑动窗口最大值为例：

• “又老又小”的值是没用的，维护一个递减队列

from collections import deque

class MonotonicQueue:
    def __init__(self):
        self.q = deque()
    
    def push(self, n):
        while self.q and self.q[-1] < n:
            self.q.pop()
        self.q.append(n)
    
    def max(self):
        return self.q[0]
    
    def pop(self, n):
        if self.q[0] == n:
            self.q.popleft()

# 滑动窗口最大值示例
def max_sliding_window(nums, k):
    window = MonotonicQueue()
    res = []
    for i in range(len(nums)):
        if i < k-1:
            window.push(nums[i])
        else:
            window.push(nums[i])
            res.append(window.max())
            window.pop(nums[i-k+1])
    return res

例题：

• 239. 滑动窗口最大值 - 力扣（LeetCode）

4 树

4.1 二叉搜索树

在最优情况下（树接近完全二叉树），插入、删除和查找操作的时间复杂度为O(log n)

• 节点排序性质

  • 若左子树不为空，则左子树上所有节点的值都小于根节点的值。

  • 若右子树不为空，则右子树上所有节点的值都大于根节点的值。

  • 左右子树也必须是二叉搜索树

• 对二叉搜索树进行中序遍历（左-根-右），得到的节点值序列是单调递增的

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

class BST:
    def insert(self, root, val):
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insert(root.left, val)
        else:
            root.right = self.insert(root.right, val)
        return root
    
    def search(self, root, val):
        if not root:
            return False
        if root.val == val:
            return True
        elif val < root.val:
            return self.search(root.left, val)
        else:
            return self.search(root.right, val)

例题

• 98. 验证二叉搜索树 - 力扣（LeetCode）
• 450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

4.2 前缀树

• 用于高效存储和检索字符串集合中的键。

• 它的每个节点代表一个字符，从根节点到某一节点的路径表示一个字符串

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

例题

• 208. 实现 Trie (前缀树) - 力扣（LeetCode）
• 211. 添加与搜索单词 - 数据结构设计 - 力扣（LeetCode）

4.3 B+树

特性：

• 多路平衡搜索树
• 所有数据存储在叶子节点
• 叶子节点形成有序链表

应用：

• 数据库索引
• 文件系统

4.4 红黑树

特性：

1. 节点是红色或黑色
2. 根节点是黑色
3. 叶子节点（NIL）是黑色
4. 红色节点的子节点都是黑色
5. 任意路径黑节点数量相同

应用：

• Linux进程调度

5. 堆

堆是一种特殊的完全二叉树结构，可以理解为一个公司,这个公司很公平,谁能力强谁就当老大,不存在弱的人当老大,老大手底下的人一定不会比他强，当我们只关心所有数据中的最大值或者最小值，存在多次获取最大值或者最小值，多次插入或删除数据时，就可以使用堆，

满足以下性质：

• 最小堆：每个节点的值 ≤ 子节点的值
• 最大堆：每个节点的值 ≥ 子节点的值

核心特征：

• 堆顶元素始终为极值（最小值或最大值）
• 插入/删除时间复杂度为 O(log n)
• 完全二叉树结构（可用数组高效存储）

手码最小堆

• 插入：将一个新元素插入堆中，同时保持堆的性质。
  • 放入列表尾部
  • 上浮
• 删除：移除并返回堆顶元素
  • 最后一个值放到堆顶
  • 下沉

heapq实现堆

import heapq

# 最小堆
heap = []
heapq.heappush(heap, 3)
heapq.heappop(heap)

# 最大堆实现
nums = [3, 1, 4]
heapq.heapify([-x for x in nums])
max_val = -heapq.heappop(nums)

例题

• 347. 前 K 个高频元素 - 力扣（LeetCode）

• 295. 数据流的中位数 - 力扣（LeetCode）

6. 图

6.1 邻接表

# 邻接表表示法
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}

# DFS遍历
def dfs(graph, node, visited):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

6.2 并查集

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 初始化：每个节点的父节点是它自己
        self.rank = [1] * n  # 初始化：每个集合的秩为 1

    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):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_x] = root_y
                self.rank[root_y] += 1

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

7. 跳表

1206. 设计跳表 - 力扣（LeetCode）