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

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

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

1. Динамические массивы: ArrayList

ArrayList — это реализация динамического массива в Java. В отличие от обычного массива, его размер автоматически увеличивается при добавлении новых элементов. Это одна из самых часто используемых структур данных.

Основные операции

• Добавление элемента: add(element) — O(1) в среднем, O(n) при расширении массива.
• Получение элемента по индексу: get(index) — O(1).
• Удаление элемента: remove(index) — O(n), так как требует сдвига элементов.

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>();
        
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        
        System.out.println("Элемент по индексу 1: " + numbers.get(1)); // 20
        
        numbers.remove(0); // Удаляем первый элемент
        System.out.println("Размер после удаления: " + numbers.size()); // 2
    }
}

Когда использовать: Когда нужен быстрый доступ по индексу и вы часто добавляете элементы в конец списка.

2. Хеш-таблицы: HashMap

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

Как это работает?

Каждый ключ преобразуется в хеш-код, который определяет "корзину" (bucket), где будет храниться значение. В случае коллизий (когда разные ключи дают одинаковый хеш) используется связный список или красно-чёрное дерево (с Java 8).

Пример использования

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> studentGrades = new HashMap<>();
        
        studentGrades.put("Alice", 90);
        studentGrades.put("Bob", 85);
        studentGrades.put("Charlie", 92);
        
        // Поиск оценки
        int aliceGrade = studentGrades.get("Alice");
        System.out.println("Оценка Alice: " + aliceGrade); // 90
        
        // Проверка наличия ключа
        if (studentGrades.containsKey("David")) {
            System.out.println("David есть в списке");
        } else {
            System.out.println("David не найден");
        }
        
        // Перебор всех записей
        for (String name : studentGrades.keySet()) {
            System.out.println(name + ": " + studentGrades.get(name));
        }
    }
}

Сложность операций: В среднем O(1) для вставки, поиска и удаления. В худшем случае (при большом количестве коллизий) — O(n).

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

Сортировка — одна из базовых операций. Java предоставляет встроенные методы, но понимание их внутреннего устройства критически важно для написания эффективного кода.

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

Это один из самых быстрых алгоритмов сортировки. Он работает по принципу "разделяй и властвуй": выбирает опорный элемент и разделяет массив на две части — меньшие и большие опорного.

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 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;
            }
        }
        
        // Ставим опорный элемент на правильное место
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        return i + 1;
    }
    
    public static void main(String[] args) {
        int[] data = {8, 3, 7, 4, 2, 9, 1};
        quickSort(data, 0, data.length - 1);
        
        System.out.print("Отсортированный массив: ");
        for (int num : data) {
            System.out.print(num + " ");
        }
        // Вывод: 1 2 3 4 7 8 9
    }
}

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

Сортировка слиянием (MergeSort)

Ещё один популярный алгоритм, который всегда работает за O(n log n), но требует дополнительной памяти.

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);
            merge(arr, left, middle, right);
        }
    }
    
    private static void merge(int[] arr, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;
        
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];
        
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[middle + 1 + j];
        }
        
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }
        
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;