Java数据结构速成【1】

一、数组（Array）与动态数组（ArrayList）

数组是连续内存存储的同类型元素集合，ArrayList 是动态扩容的数组实现。

1. 基本数组（固定长度）

声明与初始化：

// 声明方式1：指定长度
int[] intArr = new int[5]; // 初始值为0
String[] strArr = new String[3]; // 初始值为null// 声明方式2：直接赋值
int[] nums = {1, 2, 3, 4};

核心操作：

// 访问元素（通过索引，O(1)）
int val = nums[0]; // 获取第一个元素// 修改元素
nums[1] = 10; // 将索引1的元素改为10//获取长度
int len = nums.length// 遍历
// 方式1：for循环
for (int i = 0; i < nums.length; i++) {System.out.println(nums[i]);
}// 方式2：增强for循环
for (int num : nums) {System.out.println(num);
}

2. 动态数组（ArrayList）

声明与初始化：

// 声明泛型集合（只能存引用类型，基本类型需用包装类）
List<Integer> list = new ArrayList<>(); // 初始容量为10
List<String> strList = new ArrayList<>(Arrays.asList("a", "b")); // 初始化并赋值

核心操作：

// 添加元素（尾部添加，O(1)）
list.add(1); // [1]
list.add(2); // [1, 2]// 指定位置插入（O(n)，需移动后续元素）
list.add(1, 3); // [1, 3, 2]// 访问元素（O(1)）
int first = list.get(0); // 1// 修改元素（O(1)）
list.set(0, 10); // [10, 3, 2]// 删除元素（O(n)）
list.remove(1); // 删除索引1的元素 → [10, 2]
list.remove(Integer.valueOf(2)); // 删除值为2的元素 → [10]// 查找元素位置（O(n)）
int index = list.indexOf(10); // 0（不存在返回-1）//获取长度
int len = list.size// 遍历
for (int num : list) {System.out.println(num);
}
for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));
}

适用场景：需要频繁访问元素、已知大致长度的场景（如存储查询结果）。

数组列表的容量与数组的大小有一个非常重要的区别。如果分配一个有100个元素的数组，数组就有100个空位置(槽)可以使用。而容量为100个元素的数组列表只是可能保存100个元素(实际上也可以超过100，不过要以重新分配空间为代价)，但是在一开始，甚至完成初始化构造之后，数组列表并不包含任何元素。

• 对于数组new Employee[100]：

  • 它确实有 100 个 "槽位"，每个位置都可以直接存放元素（初始为 null）
  • 你可以直接通过array[0]到array[99]访问或赋值
  • 数组的长度是固定的，不能改变

• 对于new ArrayList<>(100)：

  • 这里的 100 是 "容量"，表示内部数组的初始长度为 100
  • 但ArrayList 在初始化后仍然是空的（size=0），没有任何元素
  • 这些 "槽位" 是 ArrayList 内部管理的缓冲空间，用户不能直接访问
  • 只有当你调用add()方法时，才会真正填充元素，size 才会增加
  • 当元素数量超过容量时，ArrayList 会自动扩容（创建更大的新数组，复制元素）

二、链表（LinkedList）

链表通过节点引用连接，内存不连续，适合频繁插入 / 删除的场景。Java 中 LinkedList 是双向链表实现，也可自定义单向链表。

1. 自定义单向链表

节点定义：

class ListNode {int val; // 节点值ListNode next; // 下一个节点引用// 构造方法ListNode(int x) { val = x; next = null; }
}

核心操作：

// 1. 创建链表（1 → 2 → 3）
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);// 2. 遍历链表
ListNode cur = head;
while (cur != null) {System.out.println(cur.val); // 输出1,2,3cur = cur.next;
}// 3. 插入节点（在2后面插入4）
ListNode newNode = new ListNode(4);
newNode.next = head.next.next; // 4 → 3
head.next.next = newNode; // 2 → 4 → 3 → null// 4. 删除节点（删除4）
head.next.next = head.next.next.next; // 2 → 3 → null// 5. 反转链表（迭代法）
ListNode reverse(ListNode head) {ListNode prev = null;ListNode cur = head;while (cur != null) {ListNode next = cur.next; // 保存下一个节点cur.next = prev; // 反转当前节点指针prev = cur; // 移动prevcur = next; // 移动cur}return prev; // 新头节点
}

2. Java 内置 LinkedList（双向链表）

LinkedList 是 java.util.LinkedList 类的实例，它实现了 List 接口和 Deque 接口，因此既支持普通列表的增删改查操作，也支持双端队列的特性（如首尾快速操作）。以下是其核心增删改查操作的详细说明，结合方法示例和特性分析：

声明与初始化：

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);

特有操作（与 ArrayList 相比）：

// 头部/尾部操作（O(1)）
linkedList.addFirst(0); // 头部添加 → [0,1,2]
linkedList.addLast(3); // 尾部添加 → [0,1,2,3]
linkedList.removeFirst(); // 删除头部 → [1,2,3]
linkedList.removeLast(); // 删除尾部 → [1,2]// 获取首尾元素
int first = linkedList.getFirst(); // 1
int last = linkedList.getLast(); // 2

增删改查操作详解

以下操作均以 LinkedList<String> list = new LinkedList<>(); 为基础示例。

1. 增（添加元素）

LinkedList 提供多种添加元素的方法，覆盖 “尾部添加”“指定索引添加”“首尾快速添加” 等场景：

2. 删（删除元素）

支持 “按索引删”“按元素删”“首尾快速删”，同样利用双向链表的结构优势：

3. 改（修改元素）

仅支持 “按索引修改”，因为链表无随机访问特性，需先定位到索引：

4. 查（查询元素）

支持 “按索引查”“按元素查”“查首尾元素”“遍历查询” 等：

适用场景：频繁在首尾插入 / 删除（如实现队列、栈）、未知长度的动态数据。

三、哈希表（HashMap）

基于键值对存储，通过哈希函数快速定位元素，查询 / 插入 / 删除平均 O (1)。

声明与初始化

// 声明泛型哈希表（key和value类型需指定）
Map<String, Integer> map = new HashMap<>();
// 初始化并赋值
Map<Integer, String> initMap = new HashMap<>() {{put(1, "a");put(2, "b");
}};

核心操作

// 添加键值对（若key已存在，会覆盖value）
map.put("apple", 5);
map.put("banana", 3);// 获取value（key不存在返回null）
int count = map.get("apple"); // 5// 判断key是否存在
boolean hasApple = map.containsKey("apple"); // true// 判断value是否存在
boolean hasValue3 = map.containsValue(3); // true// 删除键值对
map.remove("banana"); // 删除key为"banana"的条目// 获取所有key/value
Set<String> keys = map.keySet(); // [apple]
Collection<Integer> values = map.values(); // [5]// 遍历（推荐entrySet，同时获取key和value）
for (Map.Entry<String, Integer> entry : map.entrySet()) {String key = entry.getKey();int value = entry.getValue();System.out.println(key + ":" + value);
}

适用场景：计数（如统计字符出现次数）、缓存（存储键值映射）、快速查找（通过 key 定位 value）。

四、栈（Stack/Deque）

栈是 “后进先出”（LIFO）结构，Java 推荐用 Deque 接口的 ArrayDeque 实现（Stack 类已过时）。

声明与核心操作

// 声明栈（Deque的push/pop/peek对应栈操作）
Deque<Integer> stack = new ArrayDeque<>();// 入栈（压栈，O(1)）
stack.push(1);
stack.push(2); // 栈顶为2 → [1,2]// 出栈（弹栈顶元素，O(1)）
int top = stack.pop(); // 返回2，栈变为[1]// 查看栈顶元素（不弹出，O(1)）
int peek = stack.peek(); // 1// 判断是否为空
boolean isEmpty = stack.isEmpty(); // false// 遍历（需弹出所有元素，会清空栈）
while (!stack.isEmpty()) {System.out.println(stack.pop());
}

适用场景：括号匹配、表达式求值、回溯算法（记录路径）。

五、队列（Queue）

队列是 “先进先出”（FIFO）结构，常用 LinkedList 或 ArrayDeque 实现。

声明与核心操作

// 声明队列
Queue<Integer> queue = new LinkedList<>();// 入队（尾部添加，O(1)）
queue.offer(1);
queue.offer(2); // 队列：[1,2]// 出队（头部删除，O(1)）
int front = queue.poll(); // 返回1，队列变为[2]// 查看队首元素（不删除，O(1)）
int peek = queue.peek(); // 2// 判断是否为空
boolean isEmpty = queue.isEmpty(); // false// 遍历（需出队所有元素，会清空队列）
while (!queue.isEmpty()) {System.out.println(queue.poll());
}

适用场景：BFS（广度优先搜索）、任务调度、缓冲队列。

六、树（二叉树）

二叉树由节点组成，每个节点最多有左右两个子节点，常用递归或迭代遍历。

节点定义

class TreeNode {int val;TreeNode left; // 左子节点TreeNode right; // 右子节点TreeNode(int x) { val = x;left = null;right = null;}
}

遍历方式（以如下二叉树为例）

plaintext

    1/ \2   3/ \
4   5

1. 深度优先遍历（DFS）

• 前序遍历（根 → 左 → 右）：1 → 2 → 4 → 5 → 3

  // 递归实现
  void preorder(TreeNode root) {if (root == null) return;System.out.print(root.val + " "); // 访问根preorder(root.left); // 遍历左子树preorder(root.right); // 遍历右子树
  }// 迭代实现（用栈）
  void preorderIterative(TreeNode root) {if (root == null) return;Deque<TreeNode> stack = new ArrayDeque<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();System.out.print(node.val + " ");// 右子节点先入栈（栈是LIFO，保证左子树先处理）if (node.right != null) stack.push(node.right);if (node.left != null) stack.push(node.left);}
  }
  

• 中序遍历（左 → 根 → 右）：4 → 2 → 5 → 1 → 3

  // 递归实现
  void inorder(TreeNode root) {if (root == null) return;inorder(root.left);System.out.print(root.val + " ");inorder(root.right);
  }
  

• 后序遍历（左 → 右 → 根）：4 → 5 → 2 → 3 → 1

  // 递归实现
  void postorder(TreeNode root) {if (root == null) return;postorder(root.left);postorder(root.right);System.out.print(root.val + " ");
  }
  

2. 广度优先遍历（BFS，层序遍历）

按层级访问：1 → 2 → 3 → 4 → 5

void levelOrder(TreeNode root) {if (root == null) return;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size(); // 当前层节点数for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();System.out.print(node.val + " ");// 下一层节点入队if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}}
}

适用场景：二叉搜索树（BST）操作、路径问题、子树判断。

补充1：

Collection 是 Java 集合框架的根接口，定义了所有集合（List、Set、Queue 等）的通用操作。它的子接口（如 List、Set、Queue）则在其基础上扩展了各自特性相关的方法。以下是具体说明：

一、Collection 接口的核心方法

Collection 接口定义了所有集合共有的增删改查、判断、迭代等操作，主要包括：

二、子接口新增的常用方法

Collection 的子接口在继承上述方法的基础上，根据自身特性扩展了专属方法：

1. List 接口（有序、可重复、可按索引访问）

List 最大的特点是支持索引操作，新增方法主要围绕索引展开：

2. Set 接口（无序、不可重复）

Set 强调元素唯一性，没有新增太多方法（主要依赖 Collection 的基础方法），但部分实现类有特色方法：

3. Queue 接口（队列，FIFO 先进先出）

Queue 侧重队列操作，新增方法围绕 “队首 / 队尾” 的添加、删除、查询：

4. Deque 接口（双端队列，首尾均可操作）

Deque 继承 Queue，支持首尾双向操作，新增方法如下：

三、总结

• Collection 定义了集合的通用行为（增删、判断、迭代等），是所有集合的基础。
• List 新增索引操作（get(index)、add(index) 等），适合有序、可重复场景。
• Set 强调唯一性，核心方法与 Collection 一致，排序相关方法在 SortedSet 中。
• Queue/Deque 新增队列 / 双端队列操作（offer()、poll()、peek() 等），适合先进先出或双向操作场景。

这些接口的设计体现了 “接口隔离原则”—— 每个子接口只扩展自身特性所需的方法，使集合框架更灵活。

补充2：

ArrayDeque 是 Java 集合框架中的一个双端队列（double-ended queue）实现，它之所以能同时用作队列（Queue） 和栈（Stack），核心原因是其底层设计支持首尾两端的高效操作，同时实现了 Deque 接口（该接口继承了 Queue 接口并扩展了栈所需的操作）。

一、ArrayDeque 的底层特性

ArrayDeque 基于动态数组实现（并非链表），但数组的头尾是 “循环” 的（类似环形缓冲区），这使得：

• 可以在头部（head） 和尾部（tail） 进行 O(1) 时间复杂度的添加 / 删除操作；
• 无需像普通数组那样移动元素，因此首尾操作效率极高。

二、同时支持队列和栈的关键：Deque 接口的方法设计

ArrayDeque 实现了 Deque 接口，该接口融合了队列和栈的操作规范：

1. 作为队列（FIFO，先进先出）使用

队列的核心操作是 “尾部添加、头部删除”，Deque 提供了对应的方法：

• 入队：addLast(e) 或 offerLast(e)=offer(e)（向尾部添加元素）；
• 出队：removeFirst() 或 pollFirst()（从头部删除并返回元素）；
• 查看队首：getFirst() 或 peekFirst()（返回头部元素，不删除）。

这些方法完全符合队列的 “先进先出” 特性，例如：

Deque<Integer> queue = new ArrayDeque<>();
queue.offerLast(1);  // 入队：[1]
queue.offerLast(2);  // 入队：[1, 2]
queue.pollFirst();   // 出队：返回1，队列变为[2]

2. 作为栈（LIFO，后进先出）使用

栈的核心操作是 “头部添加、头部删除”（或 “尾部添加、尾部删除”，本质是同一个端点），Deque 提供了对应的方法：

• 压栈：addFirst(e) 或 push(e)（向头部添加元素，push 是栈的专用方法）；
• 弹栈：removeFirst() 或 pop()（从头部删除并返回元素，pop 是栈的专用方法）；
• 查看栈顶：getFirst() 或 peekFirst()（返回头部元素，不删除）。

这些方法符合栈的 “后进先出” 特性，例如：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);       // 压栈：[1]
stack.push(2);       // 压栈：[2, 1]
stack.pop();         // 弹栈：返回2，栈变为[1]

三、相比传统 Stack 类和 LinkedList 的优势

• 比 Stack 类更高效：java.util.Stack 是古老的遗留类，基于 Vector 实现，方法加了同步锁（性能低），且设计上继承了 Vector（不符合单一职责原则）；而 ArrayDeque 是专门为双端操作设计的，无同步开销，效率更高。
• 比 LinkedList 更高效：LinkedList 虽然也实现了 Deque，但底层是链表（节点有额外的前驱 / 后继指针开销），而 ArrayDeque 基于数组，内存连续，缓存友好，大多数情况下操作速度更快。

总结

ArrayDeque 能同时作为队列和栈使用的核心原因是：

1. 底层动态数组支持首尾两端的高效操作（O(1) 时间复杂度）；
2. 实现了 Deque 接口，该接口同时定义了队列（FIFO）和栈（LIFO）所需的操作方法；
3. 通过不同的方法组合（尾部操作 / 头部操作），自然适配两种数据结构的特性。
4. 但是 ArrayDeque不是线程安全的，要想同步需要额外的外部操作