В чому різниця між 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).