【Java】常见数据结构及方法
1. 数组（Array）
| 项目 | 说明 |
|---|---|
| 初始化方式 | int[] arr1 = new int[5];（指定长度）int[] arr2 = {1,2,3,4,5};（直接赋值） |
| 常用方法 | 通过索引访问：arr[i]（获取）、arr[i] = value（修改）arr.length（获取长度） |
| 遍历方式 | 1. 普通 for 循环：for(int i=0; i<arr.length; i++) { ... }2. 增强 for 循环： for(int num : arr) { ... } |
| 特点 | 固定大小，相同类型元素，随机访问快（O (1)），增删效率低 |
2. ArrayList
| 项目 | 说明 |
|---|---|
| 初始化方式 | List<String> list = new ArrayList<>();（空集合）List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3));（带初始元素） |
| 常用方法 | add(E e)：添加元素get(int index)：获取指定位置元素remove(int index)：删除指定位置元素size()：获取长度contains(Object o)：判断是否包含元素clear()：清空集合 |
| 遍历方式 | 1. 普通 for 循环：for(int i=0; i<list.size(); i++) { list.get(i); }2. 增强 for 循环： for(String s : list) { ... }3. 迭代器： Iterator<String> it = list.iterator();while(it.hasNext()) { it.next(); } |
| 特点 | 基于动态数组，查询快（O (1)），增删中间元素慢（O (n)），线程不安全 |
3. LinkedList
| 项目 | 说明 |
|---|---|
| 初始化方式 | LinkedList<String> linkedList = new LinkedList<>();LinkedList<Integer> linkedList = new LinkedList<>(Arrays.asList(1,2,3)); |
| 常用方法 | 继承 List 方法 + 特有方法：addFirst(E e)：头部添加addLast(E e)：尾部添加removeFirst()：删除头部removeLast()：删除尾部getFirst()/getLast()：获取首尾元素 |
| 遍历方式 | 同 ArrayList（普通 for 循环 / 增强 for 循环 / 迭代器） |
| 特点 | 基于双向链表，增删首尾快（O (1)），查询慢（O (n)），可作为队列 / 栈使用 |
4. HashSet
| 项目 | 说明 |
|---|---|
| 初始化方式 | Set<String> set = new HashSet<>();Set<Integer> set = new HashSet<>(Arrays.asList(1,2,3)); |
| 常用方法 | add(E e)：添加元素（重复元素不生效）remove(Object o)：删除元素contains(Object o)：判断是否包含size()：获取元素个数clear()：清空集合 |
| 遍历方式 | 1. 增强 for 循环：for(String s : set) { ... }2. 迭代器： Iterator<String> it = set.iterator();while(it.hasNext()) { ... } |
| 特点 | 基于哈希表，无序，元素不可重复，查询 / 添加 / 删除效率高（O (1)），线程不安全 |
5. TreeSet
| 项目 | 说明 |
|---|---|
| 初始化方式 | Set<Integer> treeSet = new TreeSet<>();（自然排序）Set<String> treeSet = new TreeSet<>(Comparator.reverseOrder());（自定义排序） |
| 常用方法 | 同 HashSet + 排序相关：first()：获取第一个元素（最小）last()：获取最后一个元素（最大）subSet(E from, E to)：获取子集合 |
| 遍历方式 | 同 HashSet（增强 for 循环 / 迭代器），遍历结果按排序规则输出 |
| 特点 | 基于红黑树，元素有序（自然排序或自定义排序），查询 / 添加 / 删除效率 O (log n) |
6. HashMap
| 项目 | 说明 |
|---|---|
| 初始化方式 | Map<String, Integer> map = new HashMap<>();Map<String, Integer> map = new HashMap<>(Map.of("a",1, "b",2));（Java 9+） |
| 常用方法 | put(K key, V value)：添加键值对get(Object key)：根据键获取值remove(Object key)：删除键值对containsKey(Object key)：判断是否包含键keySet()：获取所有键values()：获取所有值entrySet()：获取键值对集合 |
| 遍历方式 | 1. 遍历键：for(String key : map.keySet()) { map.get(key); }2. 遍历键值对： for(Map.Entry<String, Integer> entry : map.entrySet()) {entry.getKey(); entry.getValue();} |
| 特点 | 基于哈希表，键不可重复（重复会覆盖），无序，允许 null 键 / 值，效率高，线程不安全 |
7. TreeMap
| 项目 | 说明 |
|---|---|
| 初始化方式 | Map<String, Integer> treeMap = new TreeMap<>();（按键自然排序）Map<String, Integer> treeMap = new TreeMap<>(Comparator.reverseOrder());（自定义排序） |
| 常用方法 | 同 HashMap + 排序相关：firstKey()/lastKey()：首尾键subMap(K from, K to)：获取子映射 |
| 遍历方式 | 同 HashMap，遍历键时按排序规则输出 |
| 特点 | 基于红黑树，按键有序，查询 / 添加 / 删除效率 O (log n)，不允许 null 键 |
8. Queue（以 LinkedList 为例）
| 项目 | 说明 |
|---|---|
| 初始化方式 | Queue<String> queue = new LinkedList<>(); |
| 常用方法 | offer(E e)：添加元素（失败返回 false）poll()：移除并返回头部（空返回 null）peek()：返回头部（空返回 null）size()：获取元素个数 |
| 遍历方式 | 增强 for 循环或迭代器（同 Collection），但通常不推荐遍历（破坏队列结构） |
| 特点 | 遵循 FIFO（先进先出），适合实现队列场景 |
8.5 Deque 双端队列
| 项目 | 说明 |
|---|---|
| 常用实现类 | ArrayDeque（基于动态数组，效率高，无容量限制）LinkedList（基于链表，适合频繁插入删除） |
| 初始化方式 | Deque<String> deque = new ArrayDeque<>();Deque<Integer> deque = new LinkedList<>(); |
| 常用方法 | 尾部操作（类似队列）：addLast(E e)/offerLast(E e)：尾部添加元素removeLast()/pollLast()：移除并返回尾部元素getLast()/peekLast()：返回尾部元素头部操作（类似栈）： addFirst(E e)/offerFirst(E e)：头部添加元素removeFirst()/pollFirst()：移除并返回头部元素getFirst()/peekFirst()：返回头部元素通用操作： size()：获取元素个数isEmpty()：判断是否为空clear()：清空队列 |
| 遍历方式 | 1. 增强 for 循环（顺序遍历）：for(String s : deque) { ... }2. 迭代器： Iterator<String> it = deque.iterator();while(it.hasNext()) { ... }3. 反向迭代器： Iterator<String> reverseIt = deque.descendingIterator();while(reverseIt.hasNext()) { ... } |
| 特点 | 1. 允许在两端进行元素的添加、删除和访问 2. 可灵活实现队列（用尾部添加、头部移除）或栈（用头部添加、头部移除） 3. ArrayDeque效率通常高于LinkedList和传统Stack类4. 线程不安全，如需线程安全可使用 ConcurrentLinkedDeque |
| 典型应用场景 | 1. 实现栈（替代Stack类）2. 实现双端队列 3. 需要在两端操作元素的场景（如滑动窗口、缓存等） |
9. Stack（推荐用 ArrayDeque 替代）
| 项目 | 说明 |
|---|---|
| 初始化方式 | Deque<Integer> stack = new ArrayDeque<>(); |
| 常用方法 | push(E e)：入栈pop()：出栈并返回顶部元素peek()：返回顶部元素isEmpty()：判断是否为空 |
| 遍历方式 | 增强 for 循环或迭代器（但通常按栈规则操作，不直接遍历） |
| 特点 | 遵循 LIFO（后进先出），适合实现栈场景，ArrayDeque 效率高于传统 Stack 类 |