前言数据结构是计算机底层基石算法、Java 集合、MySQL 索引、RocketMQ 存储、Redis 底层全部依赖数据结构。无论是校招笔试、后端面试、算法刷题都绕不开数组、链表、栈队列、树、哈希、图、堆八大基础结构。本文从逻辑特性、底层实现、操作复杂度、适用场景、优缺点、代码示例完整梳理零基础可直接通读复习。一、基础概念前置1. 数据结构分类线性结构元素存在一对一关系 数组、链表、栈、队列非线性结构一对多 / 多对多 树、堆、哈希表、图2. 时间复杂度与空间复杂度核心评判标准衡量代码执行效率只保留最高阶项忽略常数、低阶O (1)常数级单次操作哈希查找O (log n)对数级二分查找、平衡树查询O (n)线性遍历链表遍历O (n log n)排序最优复杂度快排、归并O (n²)平方级冒泡、双重循环空间复杂度程序运行额外开辟内存大小。3. 两种存储方式顺序存储连续内存数组随机访问快扩容 / 删除慢链式存储分散内存 指针链表随机访问慢插入删除快二、线性结构详解1. 数组 Array核心特点连续内存存储下标随机访问 O (1)长度固定静态数组Java ArrayList 动态扩容中间插入 / 删除需要移动大量元素O (n)支持二分查找无序数组不可二分。优缺点优点随机访问速度极快、内存紧凑无额外指针开销 缺点固定长度、扩容开销大、中间增删效率低适用场景需要频繁根据下标查询、少量修改底层封装 List、栈、队列。动态数组 ArrayList 底层原理默认容量 10扩容 1.5 倍底层 Object 数组尾部添加 O (1)中间插入 O (n)。2. 链表 Linked List分类单向链表、双向链表、循环链表单向链表结构每个节点 数据域 后继指针内存不连续无下标。查询必须从头遍历 O (n)头部插入删除O (1)尾部插入删除单向链表 O (n)双向链表 O (1)双向链表LinkedList 底层节点多前驱指针可双向遍历头尾操作高效额外占用指针内存。优缺点优点内存碎片化也能存储、扩容无开销、任意位置插入删除仅修改指针 缺点无法随机访问、遍历慢、额外指针占用内存适用场景频繁头尾增删、长度不确定LRU 缓存、消息队列。3. 栈 Stack后进先出 LIFO只能在一端栈顶入栈、出栈。 基础操作push 入栈、pop 出栈、peek 取栈顶、isEmpty 判空。两种实现数组栈顺序栈扩容存在开销链表栈链式栈无扩容问题典型场景函数调用栈、表达式求值、括号匹配、二叉树非递归遍历、逆序输出。4. 队列 Queue先进先出 FIFO队尾入队队头出队。 基础操作offer 入队、poll 出队、peek 队首。细分类型普通队列FIFO双端队列 Deque头尾均可增删Java ArrayDeque循环队列数组实现解决假溢出RocketMQ 底层队列思路优先队列堆实现按优先级出队适用场景消息队列、任务调度、广度优先 BFS、限流排队。三、哈希结构哈希表 Hash Table核心思想通过哈希函数将 key 映射为数组下标直接定位存储位置理想查询 O (1)。哈希冲突解决方案链地址法HashMap 采用数组下标冲突时下标位置挂载链表链表过长转为红黑树JDK8。开放寻址法Redis 字典冲突向后寻找空位置适合数据量小、无删除场景。Java HashMap 底层数组 链表 红黑树负载因子 0.75达到阈值扩容 2 倍key 重写 hashCodeequals。优缺点优点增删查平均 O (1)查询性能天花板 缺点无序、哈希冲突退化、内存占用高适用场景缓存、键值存储、去重、分布式 Map、Redis 底层字典。四、树形结构1. 普通二叉树每个节点最多两个子节点左孩子、右孩子。 遍历方式前序根→左→右中序左→根→右二叉搜索树有序输出后序左→右→根层序广度优先 BFS队列实现2. 二叉搜索树 BST规则左子树所有节点 根 右子树所有节点 中序遍历得到升序序列。 缺陷极端数据退化成链表查询 O (n)。3. 平衡二叉树 AVL左右子树高度差不超过 1解决 BST 退化旋转维持平衡插入删除开销大工程极少使用。4. 红黑树工业标准平衡树HashMap、TreeMap、Linux 进程调度底层结构 五大特性保证最长路径不超过最短路径 2 倍查询、插入、删除稳定 O (log n)平衡代价低于 AVL。5. 堆 Heap完全二叉树分为大顶堆、小顶堆大顶堆父节点 ≥ 子节点堆顶最大值小顶堆父节点 ≤ 子节点堆顶最小值底层用数组存储下标计算 父 i左孩子 2i1右孩子 2i2 核心操作堆化、建堆、弹出堆顶。场景优先队列、TopK 问题、堆排序、任务优先级调度。6. B 树数据库索引核心MySQL InnoDB 索引底层结构多路平衡查找树非叶子节点仅存索引键不存完整数据所有数据存储在叶子节点叶子节点双向链表串联范围查询极快 优势磁盘 IO 次数少适合磁盘存储的数据库索引。7. Trie 字典树前缀树字符逐层存储适合字符串检索。 场景搜索联想、词频统计、IP 路由、敏感词过滤。五、图结构 Graph组成顶点 V 边 E 分类有向图 / 无向图、加权图 / 无权图。两种存储邻接矩阵二维数组稠密图适用空间开销大邻接表数组 链表稀疏图主流实现两大遍历DFS 深度优先栈 / 递归实现BFS 广度优先队列实现经典算法最短路径 Dijkstra、最小生成树 Prim/Kruskal、拓扑排序。 场景社交好友关系、地图路径、任务依赖。六、各结构时间复杂度汇总表背诵表格结构查找插入删除有序数组O(1)O(n)O(n)可有序单向链表O(n)O (1) 头插O(n)否哈希表O (1) 平均O(1)O(1)无序二叉搜索树O (logn) 平均O(logn)O(logn)有序红黑树O(logn)O(logn)O(logn)有序堆O(n)O(logn)O (logn) 堆顶局部有序B 树O(logn)O(logn)O(logn)全局有序七、开发底层对应关系学以致用ArrayList → 动态数组LinkedList → 双向链表ArrayDeque → 数组双端队列栈 / 队列HashMap → 哈希表 链表 红黑树TreeMap → 红黑树PriorityQueue → 小顶堆MySQL 索引 → B 树Redis ZSet → 跳表平衡树替代方案Redis 字典 → 哈希表操作系统进程调度 → 红黑树搜索引擎词库 → Trie 树八、高频面试对比题总结数组和链表区别分别适用场景 数组随机访问快适合查询链表增删快适合频繁修改。HashMap 为什么用红黑树不用 AVL 红黑树平衡旋转次数更少综合读写性能更好。B 树为什么作为数据库索引不用红黑树 磁盘 IO 昂贵B 树矮、单次 IO 读取更多索引范围查询链表遍历更高效。堆和二叉搜索树区别 堆只保证堆顶最值不满足全局有序BST 全局有序。栈和队列使用场景差异 栈逆序、递归队列排队、广度遍历。哈希冲突有哪些解决方式各自优缺点九、学习路线建议线性结构数组→链表→栈→队列手写基础增删改查哈希表理解哈希冲突、HashMap 底层源码树二叉树遍历→BST→红黑树→堆→B 树进阶Trie、跳表、图遍历与经典算法配套刷题数组链表、二叉树、TopK、二分查找十、结语所有中间件、框架底层性能优化本质都是合理选择数据结构Redis 依靠哈希表、跳表MySQL 依靠 B 树消息队列依靠数组、链表。掌握每种结构的时间复杂度、内存特性、读写场景才能在开发中合理选型写出高性能代码也是算法笔试、后端面试核心得分点。 数据结构与算法不分家先吃透基础结构再学习排序、二分、动态规划等算法会事半功倍。