从链表到哈希表：数据结构入门核心知识点全梳理

一、链表：灵活的动态存储结构

链表是一种物理存储单元上非连续、非顺序的存储结构，它的每个节点由数据域和指针域组成。数据域用来存储数据，指针域则指向下一个节点的地址。这种结构让它在插入和删除操作上有着天然的优势。

核心分类与操作

• 单向链表：每个节点只有一个指向下一节点的指针，是最基础的链表结构。
• 双向链表：节点同时拥有前驱和后继指针，支持双向遍历，在某些场景下效率更高。
• 循环链表：链表首尾相连，适合处理环形逻辑，比如约瑟夫环问题。

高频操作

• 创建与销毁：动态分配与释放节点内存，避免内存泄漏。
• 插入与删除：头插法、尾插法，以及指定位置的节点增删，时间复杂度仅为 O (1)。
• 经典问题：用快慢指针判断链表是否有环、寻找环的入口、找倒数第 k 个节点等，都是面试常客。

链表 vs 数组

这是一个经典的面试对比题，核心区别可以总结为：

• 空间：数组空间连续，链表空间可以不连续。
• 扩容：数组长度固定，扩容成本高；链表元素数量无上限，动态扩容更灵活。
• 效率：数组随机访问快（O (1)），但插入删除慢（O (n)）；链表则正好相反。

二、栈与队列：受限的线性表

栈和队列都属于 “操作受限” 的线性表，它们的核心区别在于元素的存取顺序。

栈：后进先出（LIFO）

栈就像一个羽毛球筒，你只能从最上面拿球，也只能把新球放在最上面。允许操作的一端称为栈顶，另一端称为栈底。

• 核心操作：入栈（Push）、出栈（Pop）、判空（IsEmpty）。
• 典型应用：函数调用栈、表达式求值、括号匹配、浏览器的前进后退功能。
• 实现方式：既可以用数组实现顺序栈，也可以用链表实现链式栈。

队列：先进先出（FIFO）

队列就像我们日常排队买奶茶，先到的人先买，新来的人只能排在队尾。队头负责出队，队尾负责入队。

• 核心操作：入队（Enqueue）、出队（Dequeue）、判空（IsEmpty）。
• 典型应用：任务队列、消息队列、广度优先搜索（BFS）。
• 循环队列：为了解决普通队列 “假溢出” 问题而设计，是数组实现队列的最优方案。

三、二叉树：非线性结构的基础

树是一种典型的非线性数据结构，而二叉树是其中最基础也最重要的一种，每个节点最多有两个子节点（左孩子和右孩子）。

核心概念

• 满二叉树：所有叶子节点都在同一层，且每个非叶子节点都有两个子节点。
• 完全二叉树：除了最后一层，其他层的节点数都达到最大值，且最后一层的节点都靠左排列。堆就是一种完全二叉树。
• 节点的度：一个节点拥有的子节点数，二叉树节点的度最大为 2。
• 高度与深度：节点的高度是从该节点到最远叶子节点的距离；深度是从根节点到该节点的距离。

遍历方式

遍历是操作二叉树的基础，主要分为两大类：

• 深度优先遍历（DFS）：
• 前序遍历：根 → 左 → 右
• 中序遍历：左 → 根 → 右（二叉搜索树的中序遍历是有序的）
• 后序遍历：左 → 右 → 根
• 广度优先遍历（BFS / 层序遍历）：从上到下、从左到右逐层访问节点，通常用队列实现。

四、哈希表：O (1) 时间复杂度的查找神器

哈希表（Hash Table）的核心思想是通过哈希函数（Hash Function）将键（Key）映射到数组的某个索引，从而实现近乎 O (1) 时间复杂度的插入、删除和查找操作。

核心问题：哈希冲突

当不同的键通过哈希函数计算出相同的索引时，就会发生哈希冲突。常见的解决方法有：

• 链地址法：在冲突的索引位置维护一个链表，将所有映射到该位置的元素都存放在这个链表中。这是 Java 的HashMap等容器采用的主流方案。
• 开放寻址法：当发生冲突时，通过某种探测算法（如线性探测、二次探测）寻找下一个可用的空位置。

典型应用

• 缓存实现：如 Redis 的底层就大量使用了哈希表。
• 去重与统计：比如统计字符串中每个字符出现的次数。
• 数据库索引：加速数据的查询速度。