Какие знаешь структуры данных в Java?

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

В Java структуры данных реализованы через коллекции (Collections Framework) и отдельные классы. Их можно разделить на несколько категорий: массивы, списки, множества, очереди, отображения и специализированные структуры. Рассмотрим ключевые из них.

1. Массивы (Arrays)

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

int[] array = new int[10];
String[] names = {"Alice", "Bob"};

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

2. Списки (Lists)

Реализации интерфейса List хранят упорядоченные коллекции с возможностью дубликатов.

ArrayList

Динамический массив, который автоматически расширяется.

List<String> list = new ArrayList<>();
list.add("Element");
list.get(0);

• Доступ по индексу: O(1).
• Вставка/удаление в конце: O(1), в середине: O(n).

LinkedList

Двусвязный список, где каждый элемент ссылается на предыдущий и следующий.

List<Integer> linked = new LinkedList<>();
linked.addFirst(1);
linked.removeLast();

• Вставка/удаление в начале/конце: O(1).
• Доступ по индексу: O(n).

Vector и Stack

Устаревшие синхронизированные аналоги ArrayList и LIFO-структура соответственно.

3. Множества (Sets)

Реализации интерфейса Set хранят уникальные элементы без порядка (кроме LinkedHashSet).

HashSet

Хранит элементы в хэш-таблице, обеспечивая O(1) для основных операций.

Set<Integer> set = new HashSet<>();
set.add(5);
set.contains(5);

TreeSet

Хранит элементы в отсортированном порядке (красно-черное дерево).

Set<String> treeSet = new TreeSet<>();
treeSet.add("Zebra");
treeSet.add("Apple"); // Автоматическая сортировка

• Операции: O(log n).

LinkedHashSet

Сохраняет порядок вставки элементов, сочетая хэш-таблицу и связный список.

4. Очереди (Queues)

Интерфейс Queue для обработки элементов в определённом порядке.

PriorityQueue

Очередь с приоритетом на основе кучи (heap).

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(10);
pq.poll(); // Извлечение минимального элемента

ArrayDeque

Двусторонняя очередь на основе массива, эффективнее Stack для LIFO.

Deque<String> deque = new ArrayDeque<>();
deque.push("First");
deque.pop();

5. Отображения (Maps)

Структуры "ключ-значение" (интерфейс Map).

HashMap

Хэш-таблица для хранения пар ключ-значение.

Map<String, Integer> map = new HashMap<>();
map.put("key", 100);
map.get("key");

• Операции: O(1) в среднем случае.

TreeMap

Отсортированная по ключам карта на основе красно-черного дерева.

Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three");
treeMap.firstKey(); // Получение первого ключа

• Операции: O(log n).

LinkedHashMap

Сохраняет порядок вставки или порядок доступа (для LRU-кэшей).

6. Специализированные и потокобезопасные структуры

• ConcurrentHashMap: потокобезопасная хэш-таблица с сегментированием.
• CopyOnWriteArrayList: список с копированием при изменении, подходит для редких записей.
• BlockingQueue: блокирующие очереди для многопоточности (ArrayBlockingQueue, LinkedBlockingQueue).

Критерии выбора структуры данных

1. Скорость операций:
   • Быстрый доступ по индексу → ArrayList.
   • Частые вставки/удаления в начале/конце → LinkedList.
   • Проверка уникальности → HashSet.
2. Порядок элементов:
   • Сортировка → TreeSet/TreeMap.
   • Порядок вставки → LinkedHashSet/LinkedHashMap.
3. Потокобезопасность: использование ConcurrentHashMap, CopyOnWriteArrayList или синхронизированных обёрток (Collections.synchronizedList).
4. Память: ArrayList экономичнее LinkedList для хранения данных, но требует копирования при расширении.

Пример использования в Android-разработке

В Android-приложениях структуры данных применяются повсеместно:

• RecyclerView.Adapter: хранение данных в ArrayList.
• Кэширование: LruCache на основе LinkedHashMap.
• Сетевая обработка: ConcurrentHashMap для потокобезопасного кэша.
• Конфигурации: Bundle (реализация Map) для передачи данных между компонентами.

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