В чём разница между List, Set и Queue

Интерфейсы List, Set и Queue — это три фундаментальные ветви интерфейса Collection в Java, предназначенные для принципиально разных задач хранения и обработки данных.

🟢 Junior Level

Интерфейсы List, Set и Queue — это три фундаментальные ветви интерфейса Collection в Java, предназначенные для принципиально разных задач хранения и обработки данных.

Сравнительная таблица различий

Характеристика	`List` (Список)	`Set` (Множество)	`Queue` (Очередь)
Дубликаты	Разрешены (любое количество)	Запрещены (только уникальные элементы)	Разрешены (в большинстве реализаций)
Порядок элементов	Строго упорядочен (по индексам добавления)	Не гарантирован (`HashSet`), порядок вставки (`LinkedHashSet`) или сортировка (`TreeSet`)	Порядок обработки (обычно FIFO или приоритет)
Доступ к элементам	По целочисленному индексу `get(i)`	Только поиск/проверка наличия `contains(x)` или итератор	Только голова очереди (`peek()`, `poll()`)
Основная аналогия	Список покупок в блокноте	Мешок с уникальными лотерейными шарами	Очередь покупателей к кассе
Базовые реализации	`ArrayList`, `LinkedList`	`HashSet`, `LinkedHashSet`, `TreeSet`	`ArrayDeque`, `PriorityQueue`

// 1. List: сохраняет порядок добавления, допускает повторы
List<String> list = new ArrayList<>();
list.add("Java");
list.add("Kotlin");
list.add("Java"); // [Java, Kotlin, Java]

// 2. Set: отсекает дубликаты
Set<String> set = new HashSet<>();
set.add("Java");
set.add("Kotlin");
set.add("Java"); // Вернет false, в сете останется: [Java, Kotlin]

// 3. Queue: обработка элементов по правилу FIFO
Queue<String> queue = new ArrayDeque<>();
queue.offer("Первый");
queue.offer("Второй");
String processed = queue.poll(); // Извлечет "Первый"

🟡 Middle Level

1. Две группы методов интерфейса `Queue`

Интерфейс Queue спроектирован с учетом ситуаций ограниченной емкости (Bounded Queues) и пустых очередей. Для каждой операции существуют два метода с разным поведением при сбое:

Действие	Бросает исключение при сбое	Возвращает специальное значение (`false` / `null`)
Вставка в очередь	`add(e)` (бросает `IllegalStateException`, если очередь полна)	`offer(e)` (возвращает `false`, если нет места)
Извлечение с удалением	`remove()` (бросает `NoSuchElementException`, если очередь пуста)	`poll()` (возвращает `null`, если очередь пуста)
Просмотр без удаления	`element()` (бросает `NoSuchElementException`, если очередь пуста)	`peek()` (возвращает `null`, если очередь пуста)

[!TIP] В высоконагруженном коде всегда используйте связку offer() / poll() / peek(): она исключает накладные расходы на создание и выброс исключений при нормальном рабочем опустошении или заполнении очередей.

2. Сравнительная алгоритмическая сложность

Операция	`ArrayList` (List)	`HashSet` (Set)	`TreeSet` (Set)	`ArrayDeque` (Queue)	`PriorityQueue` (Queue)
Доступ по индексу	$O(1)$	Не поддерживается	Не поддерживается	Не поддерживается	Не поддерживается
Вставка в конец	$O(1)^*$ аморт.	$O(1)$	$O(\log N)$	$O(1)$	$O(\log N)$
Вставка в начало/голову	$O(N)$ (сдвиг)	$O(1)$	$O(\log N)$	$O(1)$	$O(\log N)$
Поиск (`contains`)	$O(N)$ (полный перебор)	$O(1)$	$O(\log N)$	$O(N)$	$O(N)$
Удаление по значению	$O(N)$	$O(1)$	$O(\log N)$	$O(N)$	$O(N)$
Извлечение головы	$O(N)$ (`remove(0)`)	Не применимо	$O(\log N)$ (`pollFirst`)	$O(1)$	$O(\log N)$

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

Какая главная задача?
  │
  ├── Нужен быстрый доступ по номеру/индексу? ──────► List (ArrayList)
  │
  ├── Нужна строгая уникальность элементов? ────────► Set
  │     ├── Порядок не важен, нужен максимум скорости? ──► HashSet (O(1))
  │     ├── Нужен порядок вставки элементов? ────────────► LinkedHashSet
  │     └── Нужна постоянная сортировка элементов? ──────► TreeSet (O(log N))
  │
  └── Нужен порядок обработки задач (Producer-Consumer)? ──► Queue
        ├── Обычная очередь FIFO или стек LIFO? ────────► ArrayDeque
        └── Извлечение по приоритету (компаратору)? ─────► PriorityQueue

🔴 Senior Level

1. Расход памяти: Скрытая цена `HashSet`

Инженеры часто упускают колоссальную разницу в потреблении памяти между ArrayList и HashSet:

ArrayList (1 000 000 элементов):
[ Массив Object[] ] ──► 1 млн прямых ссылок (~4 МБ памяти на указатели)

HashSet (1 000 000 элементов):
Каждый элемент оборачивается в объект HashMap$Node:
├── Заголовок объекта (Mark Word + Klass Word) = 12 байт
├── Хэш-код (int) = 4 байта
├── Ссылка на ключ (Key) = 4 байта
├── Ссылка на значение (dummy PRESENT) = 4 байта
├── Ссылка на следующий узел (next) = 4 байта
└── Выравнивание (Padding) = 4 байта
Итого на 1 элемент: 32 байта (узел) + 4 байта (ячейка массива bucket) = ~36 байт!

[!IMPORTANT] Для хранения 1 миллиона элементов HashSet потребует около 36–40 МБ накладных расходов памяти только на служебные структуры данных, тогда как ArrayList обойдется всего в 4–8 МБ.

2. Парадокс равенства: `TreeSet` нарушает контракт `equals()`!

Спецификация Set утверждает, что множество содержит уникальные элементы согласно методу equals(). Однако TreeSet опирается на интерфейс Comparable или переданный Comparator:

class Item implements Comparable<Item> {
    int id;
    String name;

    // equals() сравнивает И id, И name:
    @Override
    public boolean equals(Object o) { ... return this.id == o.id && this.name.equals(o.name); }

    // compareTo сравнивает ТОЛЬКО id:
    @Override
    public int compareTo(Item o) { return Integer.compare(this.id, o.id); }
}

Set<Item> set = new TreeSet<>();
set.add(new Item(1, "Первый"));
set.add(new Item(1, "Второй")); // НЕ ДОБАВИТСЯ! compareTo() вернул 0.

TreeSet считает два объекта дубликатами, если comparator.compare(a, b) == 0. Метод equals() даже не вызывается!
Если компаратор не согласован с equals(), поведение коллекции перестает соответствовать общему контракту интерфейса Set.

3. Конкурентные альтернативы для многопоточной среды

В параллельных приложениях стандартные коллекции ArrayList, HashSet и ArrayDeque не синхронизированы:

Для List:
- CopyOnWriteArrayList: идеально подходит для редких записей и частых чтений (при модификации массив копируется целиком, чтения происходят без блокировок).
Для Set:
- ConcurrentHashMap.newKeySet(): лучший выбор в production. Построен на сегментированной / CAS-синхронизации узлов без глобальных блокировок.
Для Queue:
- ConcurrentLinkedQueue: неблокирующая очередь на базе алгоритма Майкла и Скотта (CAS на атомарных ссылках).
- ArrayBlockingQueue / LinkedBlockingQueue: блокирующие очереди с механизмом противодавления (backpressure) для паттерна «Производитель — Потребитель» (Producer-Consumer).

🎯 Шпаргалка для интервью

30-секундный ответ для собеседования

«Главные различия между ними заключаются в уникальности, порядке и способе доступа:

List хранит упорядоченную последовательность элементов, допускает дубликаты и предоставляет произвольный доступ по индексу за $O(1)$ (ArrayList);

Set хранит исключительно уникальные элементы, отсекая дубликаты по equals()/hashCode() (HashSet) или компаратору (TreeSet), оптимизирован для мгновенной проверки членства contains() за $O(1)$;

Queue организует поток обработки элементов (обычно FIFO) и предоставляет доступ только к вершине/голове через неблокирующие методы offer(), poll(), peek()».

Вопросы повышенной сложности с ответами

Почему HashSet потребляет в 4–5 раз больше оперативной памяти, чем ArrayList на том же объеме данных? Ответ: ArrayList хранит элементы в плоском непрерывном массиве ссылок Object[], расходуя всего по 4–8 байт на элемент (при Compressed OOPs). HashSet под капотом создает HashMap, где каждый добавляемый элемент упаковывается в полноценный объект ноды (HashMap$Node). Нода содержит заголовок объекта (12 байт), кэш хэш-кода (4 байта), ссылку на ключ, ссылку на статическое значение PRESENT, ссылку next на случай коллизии и байты выравнивания, что суммарно занимает 32 байта в куче плюс 4–8 байт в массиве корзин (таблице бакетов).
Чем методы offer(), poll(), peek() отличаются от add(), remove(), element() в интерфейсе Queue? Ответ: Методы add(), remove(), element() при невозможности выполнить операцию (очередь переполнена или очередь пуста) генерируют исключения (IllegalStateException, NoSuchElementException). Методы offer(), poll(), peek() возвращают специальные служебные значения (false при невозможности добавить элемент из-за переполнения bounded-очереди, и null при попытке чтения/извлечения из пустой очереди). В production всегда отдается предпочтение offer/poll/peek для исключения накладных расходов на генерацию стек-трейсов исключений.
Почему TreeSet может посчитать два объекта равными, даже если их метод equals() возвращает false? Ответ: В отличие от HashSet, который проверяет совпадение через hashCode() и equals(), TreeSet построен на красно-черном дереве (TreeMap) и полностью игнорирует методы hashCode() и equals(). Уникальность элементов в TreeSet определяется исключительно результатом вызова Comparable.compareTo() или внешнего Comparator.compare(). Если компаратор возвращает 0, объект объявляется дубликатом и не добавляется в дерево, даже если equals() считает объекты разными.
Что выбрать для реализации стека (LIFO): устаревший java.util.Stack, LinkedList или ArrayDeque? Ответ: Однозначно ArrayDeque. Класс java.util.Stack является устаревшим (legacy), так как наследует Vector и на каждый метод накладывает синхронизацию через блокировку монитора synchronized, замедляя однопоточный код. LinkedList создает узел Node на каждый добавленный элемент, нагружая GC и ухудшая кэш-локальность. ArrayDeque работает на кольцевом массиве в непрерывной памяти без блокировок и без создания промежуточных узлов, обеспечивая максимальную скорость как для очередей (FIFO), так и для стеков (LIFO).

Типичные ошибки и Red Flags

❌ Использовать ArrayList.contains() для частой проверки наличия в больших коллекциях. (Сложность $O(N)$ приведет к катастрофической просадке производительности до $O(N^2)$; для частых проверок всегда нужен Set).
❌ Утверждать, что Queue всегда работает строго по принципу FIFO. (Ложь: существуют приоритетные очереди PriorityQueue, извлекающие элементы по весу, и двусторонние очереди Deque, работающие как стек LIFO).
❌ Рекомендовать Vector или Hashtable для многопоточной разработки. (Критический Red Flag: незнание современных конкурентных коллекций из java.util.concurrent).