链表

在算法中，数据结构的选择直接影响程序的效率，其核心是匹配具体场景的操作需求（如频繁查找、插入、排序等）。常见数据结构可分为线性结构、树形结构、图形结构等，每种结构因存储方式和操作特性的不同，适用于特定场景。 一、线性结构：一对一的数据关系 线性结构是最基础的数据结构，元素间呈线性排列，核心差异在于内存存储方式（连续或离散）和操作效率。 数据结构 核心特点 优点 缺点 典型使用场景 数组（Array） 元素连续存储，通过索引访问，长度固定（静态）或动态扩容 随机访问快（O(1)），内存连续利用率高 插入/删除效率低（需移动元素，O(n)）；动态扩容有性能损耗 需频繁随机访问场景：如存储用户列表、矩阵运算、滑动窗口算法 链表（Linked List） 元素离散存储，通过指针/引用连接（单链表、双链表、循环链表） 插入/删除快（O(1)，只需改指针）；长度灵活 随机访问慢（O(n)，需从头遍历）；额外存储指针，内存开销大 频繁插入/删除场景：如链表式队列、LRU缓存（双链表）、邻接表（图的存储） 栈（Stack） 遵循后进先出（LIFO），仅允许在栈顶操作（push/pop） 操作简单，时间复杂度O(1) 功能单一，仅支持栈顶操作 表达式求值（如括号匹配）、递归调用栈、深度优先搜索（DFS） 队列（Queue） 遵循先进先出（FIFO），允许在队尾插入、队头删除 顺序处理数据，操作效率O(1) 中间元素操作困难 任务调度（如线程池任务队列）、广度优先搜索（BFS）、消息队列 双端队列（Deque） 队列两端均可插入/删除，结合栈和队列特性 操作灵活，两端操作O(1) 实现较复杂（如基于链表或循环数组） 滑动窗口问题、缓存实现（如Java中的ArrayDeque） 二、树形结构：一对多的层级关系 树形结构通过“父节点-子节点”形成层级，适用于具有层级关系的数据，核心是优化查找和排序效率。 数据结构 核心特点 优点 缺点 典型使用场景 二叉树（Binary Tree） 每个节点最多2个子节点（左、右），无平衡要求 结构简单，适合递归操作 极端情况下退化为链表（如有序插入成单链），查找效率低（O(n)） 基础树形结构学习，表达式树（如编译器语法解析） 二叉搜索树（BST） 左子树节点值 < 根节点值 < 右子树节点值，支持快速查找 查找、插入、删除平均效率O(logn) 不平衡时退化为链表（如顺序插入） 动态数据的查找（如字典查询），但实际中多被平衡树替代 红黑树（Red-Black Tree） 自平衡二叉搜索树，通过颜色规则（红/黑）维持平衡，最长路径不超过最短路径2倍 查找、插入、删除稳定O(logn)，平衡性好 实现复杂，旋转操作耗时 TreeMap（Java）、C++ STL中的map/set，数据库索引（小型索引） B树/B+树 多路平衡查找树，B树节点存储数据，B+树数据仅在叶子节点，且叶子节点连成链表 减少IO次数（适合磁盘存储），支持范围查询 B+树非叶子节点不存数据，空间利用率更高 数据库索引（如MySQL InnoDB的聚簇索引）、文件系统（大量数据的磁盘存储） 堆（Heap） 完全二叉树，分为大顶堆（父>子）和小顶堆（父<子），支持优先操作 插入/删除O(logn)，获取最值O(1) 不支持随机访问，查找效率低（O(n)） 优先队列（如任务调度按优先级执行）、堆排序、Top K问题（如取最大的10个数） 三、哈希结构：通过哈希函数快速映射 哈希结构（Hash）的核心是键值对（Key-Value）映射，通过哈希函数将键转换为存储地址，实现快速查找。 ...