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

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

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

1. Основные структуры данных в Java

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

1.1 Массивы (Arrays)

Массив — это простейшая структура данных, хранящая элементы одного типа в непрерывной области памяти. В Java массивы имеют фиксированную длину.

// Объявление и инициализация массива
int[] numbers = new int[5];
numbers[0] = 10;
numbers[1] = 20;
numbers[2] = 30;
numbers[3] = 40;
numbers[4] = 50;

// Или сразу с значениями
String[] fruits = {"Яблоко", "Банан", "Апельсин"};

// Проход по массиву
for (int i = 0; i < fruits.length; i++) {
    System.out.println(fruits[i]);
}

// Улучшенный for-each
for (String fruit : fruits) {
    System.out.println(fruit);
}

Преимущества: быстрый доступ по индексу (O(1)).
Недостатки: фиксированный размер, сложность вставки и удаления элементов.

1.2 Связные списки (LinkedList)

Связный список состоит из узлов, каждый из которых содержит данные и ссылку на следующий (или предыдущий) узел. В Java есть встроенная реализация java.util.LinkedList.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("Первый");
list.add("Второй");
list.addFirst("Нулевой"); // Добавление в начало
list.addLast("Третий");   // Добавление в конец

System.out.println("Первый элемент: " + list.getFirst());
System.out.println("Последний элемент: " + list.getLast());
System.out.println("Размер списка: " + list.size());

// Удаление элемента
list.remove("Второй");

Преимущества: быстрая вставка и удаление в начале/конце списка (O(1)).
Недостатки: медленный доступ по индексу (O(n)).

1.3 Стек (Stack)

Стек работает по принципу LIFO (Last In, First Out) — последним пришёл, первым ушёл. Java предоставляет класс Stack и интерфейс Deque для работы со стеком.

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

// Добавление элементов
stack.push(10);
stack.push(20);
stack.push(30);

// Просмотр верхнего элемента без удаления
System.out.println("Верхний элемент: " + stack.peek()); // 30

// Извлечение верхнего элемента
int top = stack.pop();
System.out.println("Извлечен: " + top); // 30
System.out.println("Новый верхний: " + stack.peek()); // 20

// Проверка, пуст ли стек
System.out.println("Стек пуст? " + stack.isEmpty()); // false

Стек часто используется для проверки правильности скобочных последовательностей, обхода деревьев и реализации алгоритмов "назад/вперёд" в браузерах.

1.4 Очередь (Queue)

Очередь работает по принципу FIFO (First In, First Out) — первым пришёл, первым ушёл. В Java очередь реализована через интерфейс Queue и класс LinkedList.

import java.util.LinkedList;
import java.util.Queue;

Queue<String> queue = new LinkedList<>();

// Добавление в конец очереди
queue.offer("Клиент 1");
queue.offer("Клиент 2");
queue.offer("Клиент 3");

// Кто первый в очереди?
System.out.println("Первый: " + queue.peek()); // Клиент 1

// Обслуживаем первого
String served = queue.poll();
System.out.println("Обслужен: " + served); // Клиент 1
System.out.println("Теперь первый: " + queue.peek()); // Клиент 2

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

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

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

Простой, но неэффективный алгоритм, который многократно проходит по массиву и меняет соседние элементы местами, если они стоят в неправильном порядке.

public class BubbleSort {
    public static void sort(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};
        sort(data);
        System.out.println("Отсортированный массив: " + Arrays.toString(data));
    }
}

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

2.2 Быстрая сортировка (Quick Sort)

Один из самых эффективных алгоритмов, использующий подход "разделяй и властвуй".

public class QuickSort {
    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(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] =