1. 线性表（顺序 / 链式存储的线性结构）

  • LinkedList
    • 本质：双向链表实现，同时实现了List和Deque接口（所以既是列表，又能当队列 / 栈用）。
    • 核心特性：
      • 作为List：可以按索引访问（get(int index)），但随机访问效率低（链表需要遍历），适合频繁在中间增删元素的场景。
      • 作为Deque：支持双端操作（首尾都能增删），可模拟栈或队列。
    • 常用方法：
      • 列表功能：add(E)、get(int)、remove(int)
      • 双端队列功能：addFirst(E)、addLast(E)、removeFirst()、removeLast()

2. 栈（LIFO：后进先出）

  • Stack（不推荐）
    • 本质：继承自Vector的遗留类（Java 早期设计，有线程安全开销，效率低）。
    • 核心特性：仅支持栈操作（压栈、弹栈、查看栈顶）。
    • 常用方法：push(E)（压栈）、pop()（弹栈，移除并返回栈顶）、peek()（查看栈顶）。
    • 注意：实际开发 / 算法题中几乎不用，推荐用Deque的实现类（如ArrayDeque）模拟栈，方法更统一。
  • Deque 模拟栈
    • 用ArrayDeque（数组实现，效率更高）或LinkedList，通过push(E)（等价于addFirst(E)）、pop()（等价于removeFirst()）、peekFirst()实现栈操作，这是标准做法。

3. 队列（FIFO：先进先出，或特殊规则）

  • Queue（接口）
    • 本质：定义队列的规范，需用实现类（如LinkedList、ArrayDeque、PriorityQueue）。
    • 核心特性：
      • 普通队列（FIFO）：如LinkedList、ArrayDeque。
      • 优先级队列：PriorityQueue（元素按优先级排序，不遵循 FIFO，默认小顶堆）。
    • 常用方法（队列通用）：
      • 添加：offer(E)（失败返回 false）、add(E)（失败抛异常）。
      • 移除：poll()（移除并返回队头，空队列返回 null）、remove()（空队列抛异常）。
      • 查看：peek()（返回队头，空队列返回 null）、element()（空队列抛异常）。
  • Deque（双端队列，接口）
    • 继承自Queue，支持两端都能增删元素（既可以当队列，也可以当栈）。
    • 实现类：ArrayDeque（数组实现，效率最高，推荐）、LinkedList（链表实现，适合频繁增删）。
    • 队列场景用法：用addLast(E)（入队）、removeFirst()（出队）模拟 FIFO。

4. 映射（键值对存储）

  • HashMap
    • 本质：Map接口的实现类，基于哈希表存储键值对（key-value）。
    • 核心特性：
      • key 唯一（重复会覆盖旧值），value 可重复。
      • 无序（Java 8 后迭代顺序基本稳定，但不保证有序）。
      • 线程不安全（多线程用ConcurrentHashMap），允许 key/value 为 null。
    • 常用方法：
      • put(K, V)（存键值对）、get(K)（根据 key 取值）、containsKey(K)（判断 key 是否存在）、remove(K)（删除键值对）。

二、核心区别与选择依据

数据结构 核心功能 典型场景 推荐实现类 / 用法
LinkedList 列表 + 双端操作 频繁增删的列表、简单双端队列 直接使用
栈（Stack 替代） LIFO 操作 括号匹配、表达式求值、深度优先搜索 (DFS) Deque stack = new ArrayDeque<>()
队列 FIFO 操作 广度优先搜索 (BFS)、任务调度 Queue queue = new ArrayDeque<>()
优先级队列 按优先级取元素 TopK 问题、贪心算法 PriorityQueue pq = new PriorityQueue<>()
HashMap 键值对存储（快速查询） 计数、缓存、映射关系存储（如 id-> 对象） 直接使用

书籍：《Java 核心技术卷 I》