Java 中常见的数据结构及其常用 API

本文总结了 Java 中常见的数据结构及其常用 API，帮助开发者在写算法时能够快速选择合适的数据结构和操作。通过使用合适的 API，可以有效减少计算复杂度，并提高代码的执行效率。

1. 数组

数组是 Java 中最常用的数据结构之一，Java 提供了很多操作数组的 API。常用的 API 包括排序、查找、复制、填充等。

Arrays 类
Arrays 类提供了许多静态方法来操作数组，常用方法包括：

• Arrays.sort()：排序数组。使用优化过的快速排序，时间复杂度为 O(nlogn)。

  int[] arr = {2, 6, 8, 7, 10};
  Arrays.sort(arr);
  System.out.println(Arrays.toString(arr));  // 输出: [2, 6, 7, 8, 10]
  

• Arrays.binarySearch()：二分查找，要求数组必须是排序好的。

  int index = Arrays.binarySearch(arr, 6);
  System.out.println(index);  // 输出: 1
  

• Arrays.equals()：比较两个数组是否相等。

  boolean result = Arrays.equals(arr1, arr2);
  

• Arrays.fill()：填充数组。

  Arrays.fill(arr, 5);
  

• Arrays.copyOf()：复制数组，并且可以指定新数组的长度。

  int[] newArray = Arrays.copyOf(arr, 10);
  

• Arrays.asList()：将数组转换为 List 集合。

  List<Integer> list = Arrays.asList(arr);
  

2. 链表

Java 中的链表通过 LinkedList 类实现，它是双向链表。LinkedList 支持快速的插入和删除操作，但随机访问较慢。常用的 API 包括：

• add(E e)：在链表末尾添加元素。

• addFirst(E e)：在链表头部添加元素。

• addLast(E e)：在链表末尾添加元素。

• removeFirst()：删除链表头部元素。

• removeLast()：删除链表尾部元素。

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.addFirst("B");
System.out.println(list);  // 输出: [B, A]

3. 哈希表

哈希表用于快速查找元素。Java 提供了 HashSet 和 HashMap 类来实现哈希表。

HashSet
HashSet 是基于哈希表实现的 Set 集合，主要用于快速查找和去重。

• add(E e)：添加元素。

• remove(Object o)：移除元素。

• contains(Object o)：检查是否包含元素。

HashSet<String> set = new HashSet<>();
set.add("A");
set.add("B");
set.contains("A");  // 返回 true

HashMap
HashMap 提供了键值对的存储和检索操作。

• put(K key, V value)：存储键值对。

• get(K key)：根据键获取值。

• containsKey(K key)：检查是否包含指定键。

HashMap<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.get("A");  // 输出: 1

4. ArrayList

ArrayList 是 Java 中最常用的动态数组实现，支持根据索引访问元素，适用于插入较少的场景。

• add(E e)：添加元素。

• get(int index)：获取指定位置的元素。

• remove(int index)：删除指定位置的元素。

• size()：获取 ArrayList 的大小。

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
System.out.println(list.get(0));  // 输出: A

5. 字符串处理

Java 提供了丰富的字符串处理方法。StringBuilder 类专门用于操作字符串，适合频繁修改字符串时使用。

常用 API：

• length()：返回字符串的长度。

• charAt(int index)：返回指定位置的字符。

• substring(int start, int end)：返回指定范围的子字符串。

• append(String str)：拼接字符串。

StringBuilder sb = new StringBuilder("Hello");
sb.append(" World");
System.out.println(sb.toString());  // 输出: Hello World

6. 栈

栈通常通过 java.util.Stack 类或 java.util.ArrayDeque 实现。Stack 是线程安全的，而 ArrayDeque 更高效，适合写算法时使用。

Stack API

• push(E item)：将元素压入栈顶。

• pop()：弹出栈顶元素。

• peek()：查看栈顶元素。

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.pop();  // 弹出 2

7. 队列

队列可以通过 LinkedList 或 ArrayDeque 实现。常用 API：

LinkedList

• add(E e)：在队列尾部添加元素。

• remove()：移除队列头部元素。

• peek()：查看队列头部元素。

LinkedList<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.remove();  // 移除 1

ArrayDeque

• offer(E e)：在队列尾部添加元素。

• poll()：移除队列头部元素。

• peek()：查看队列头部元素。

ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
queue.poll();  // 移除 1