Алгоритмы и структуры данных на Java: практическое руководство

Алгоритмы и структуры данных на Java: от теории к практике

Понимание алгоритмов и структур данных — фундамент, на котором строится карьера любого Java-разработчика. Без этого знания сложно писать эффективный, масштабируемый и поддерживаемый код. В этой статье мы разберём ключевые структуры данных и алгоритмы, которые вы будете использовать ежедневно, и покажем их реализацию на Java с практическими примерами.

1. Базовые структуры данных в Java Collections Framework

Java предлагает мощный фреймворк коллекций, который включает в себя основные структуры данных. Рассмотрим три самые популярные.

ArrayList — динамический массив

ArrayList — это реализация динамического массива. Он автоматически расширяется при добавлении новых элементов, что делает его отличным выбором для списков с неизвестным заранее размером.

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> fruits = new ArrayList<>();
        fruits.add("Яблоко");
        fruits.add("Банан");
        fruits.add("Апельсин");

        System.out.println("Второй элемент: " + fruits.get(1)); // Банан
        fruits.remove(0);
        System.out.println("Размер после удаления: " + 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("Анна", 25);
        ages.put("Иван", 30);
        ages.put("Мария", 28);

        System.out.println("Возраст Анны: " + ages.get("Анна")); // 25
        
        // Проверка наличия ключа
        if (ages.containsKey("Иван")) {
            System.out.println("Иван найден!");
        }
        
        // Перебор всех записей
        for (String name : ages.keySet()) {
            System.out.println(name + ": " + ages.get(name) + " лет");
        }
    }
}

Сложность операций: вставка, поиск, удаление — в среднем O(1).

LinkedList — двусвязный список

LinkedList состоит из узлов, каждый из которых хранит ссылки на предыдущий и следующий элементы. Идеален для частых вставок и удалений в начале или конце списка.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> queue = new LinkedList<>();
        
        // Используем как очередь (FIFO)
        queue.addLast(1);
        queue.addLast(2);
        queue.addLast(3);
        
        System.out.println("Первый в очереди: " + queue.getFirst()); // 1
        queue.removeFirst();
        System.out.println("После удаления: " + queue); // [2, 3]
        
        // Используем как стек (LIFO)
        queue.push(10); // добавляем в начало
        queue.push(20);
        System.out.println("Верхушка стека: " + queue.pop()); // 20
    }
}

Сложность операций: вставка/удаление в начале/конце — O(1), доступ по индексу — O(n).

2. Алгоритмы сортировки на Java

Сортировка — одна из самых распространённых задач. Рассмотрим две классические реализации.

Сортировка пузырьком (Bubble Sort)

Простой, но медленный алгоритм. Используется в учебных целях.

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Меняем местами
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // Если не было обменов — массив уже отсортирован
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] data = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(data);
        System.out.println("Отсортированный массив:");
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}

Сложность: O(n²) в худшем и среднем случае, O(n) в лучшем.

Быстрая сортировка (QuickSort)

Один из самых эффективных алгоритмов для реальных задач.

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // Меняем местами
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // Ставим pivot на правильное место
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        return i + 1;
    }

    public static void main(String[] args) {
        int[] data = {10, 7, 8, 9, 1, 5};
        quickSort(data, 0, data.length - 1);
        System.out.println("Отсортировано QuickSort:");
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}

Сложность: O(n log n) в среднем, O(n²) в худшем случае (редко).

3. Алгоритмы поиска

Умение быстро находить данные — ключевой навык. Рассмотрим два основных подхода.

Линейный поиск (Linear Search)

Самый простой метод — последовательный перебор всех элементов.

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // Возвращаем индекс
            }
        }
        return -1; // Элемент не найден
    }

    public static void main(String[] args)