Java算法与数据结构：实用指南

Java 中的算法与数据结构：从理论到实践

理解算法与数据结构是每一位 Java 开发者职业生涯的基石。缺乏这方面的知识，将难以编写高效、可扩展且易于维护的代码。在本文中，我们将剖析您日常会用到的主要数据结构和算法，并通过实际示例展示它们在 Java 中的实现。

1. Java 集合框架中的基本数据结构

Java 提供了一个强大的集合框架，其中包含了基本的数据结构。让我们来看看其中最常用的三种。

ArrayList——动态数组

ArrayList 是动态数组的一种实现。当添加新元素时，它会自动扩展，因此对于事先未知大小的列表来说，这是一个绝佳的选择。

import java.util.ArrayList;

public class ArrayListExample {    public static void main(String[] args) {        ArrayList<String> fruits = new ArrayList<>();        fruits.add("Apple");        fruits.add("Banana");        fruits.add("Orange");

        System.out.println("Second element: " + fruits.get(1)); // Banana        fruits.remove(0);        System.out.println("Size after removal: " + fruits.size()); // 2                for (String fruit : fruits) {            System.out.println(fruit);        }    }}

操作复杂度：按索引访问 — O(1)，在中间插入/删除 — O(n)。

HashMap——哈希表

HashMap 存储键值对，并能够提供近乎瞬时的按键访问数据能力。

import java.util.HashMap;

public class HashMapExample {    public static void main(String[] args) {        HashMap<String, Integer> ages = new HashMap<>();        ages.put("Anna", 25);        ages.put("Ivan", 30);        ages.put("Maria", 28);

        System.out.println("Anna's age: " + ages.get("Anna")); // 25                // Checking for key existence        if (ages.containsKey("Ivan")) {            System.out.println("Ivan found!");        }                // Iterating over all entries        for (String name : ages.keySet()) {            System.out.println(name + ": " + ages.get(name) + " years old");        }    }}

操作复杂度：插入、查找、删除 — 平均 O(1)。

LinkedList——双向链表

LinkedList 由节点组成，每个节点存储指向前后元素的引用。它非常适合在列表的开头或结尾进行频繁的插入和删除操作。

import java.util.LinkedList;

public class LinkedListExample {    public static void main(String[] args) {        LinkedList<Integer> queue = new LinkedList<>();                // Using as a queue (FIFO)        queue.addLast(1);        queue.addLast(2);        queue.addLast(3);                System.out.println("First in queue: " + queue.getFirst()); // 1        queue.removeFirst();        System.out.println("After removal: " + queue); // [2, 3]                // Using as a stack (LIFO)        queue.push(10); // add to the beginning        queue.push(20);        System.out.println("Stack top: " + queue.pop()); // 20    }}

操作复杂度：在开头/结尾插入/删除 — O(1)，按索引访问 — O(n)。

2. Java 中的排序算法

排序是最常见的任务之一。让我们来看两种经典的实现。

冒泡排序

一种简单但速度较慢的算法。主要用于教学目的。

public class BubbleSort {    public static void bubbleSort(int[] arr) {        int n = arr.length;        boolean swapped;                for (i