2.1.1. List, Set, Queue

ArrayList, LinkedList, HashSet, TreeSet, PriorityQueue

Материалы

Иерархия интерфейсов коллекций

Collection (интерфейс)
├── List
├── Set
│   ├── SortedSet
│   └── NavigableSet
└── Queue
    ├── Deque
    ├── BlockingQueue
    ├── TransferQueue
    └── BlockingDeque

List - Упорядоченная коллекция

Основные характеристики

• Порядок элементов: сохраняется порядок добавления
• Дубликаты: разрешены
• Индексация: доступ по индексу (0-based)
• Null-элементы: обычно разрешены

Реализации

ArrayList

• Структура данных: Resizable Array (динамический массив)
• Доступ по индексу: O(1) - быстрый random access
• Вставка/удаление в конце: O(1) амортизированное
• Вставка/удаление в середине: O(n) - требует сдвига элементов
• Использование памяти: компактное, но может быть перевыделение
• Когда использовать: частый доступ по индексу, редкие вставки в середину

List<String> arrayList = new ArrayList<>();
arrayList.add("first");
arrayList.add("second");
String element = arrayList.get(0); // O(1)

LinkedList

• Структура данных: Doubly-linked list (двусвязный список)
• Доступ по индексу: O(n) - нужно пройти по списку
• Вставка/удаление в начале/конце: O(1)
• Вставка/удаление в середине: O(1) если есть итератор, O(n) если нужно найти позицию
• Использование памяти: больше накладных расходов (ссылки на prev/next)
• Когда использовать: частые вставки/удаления, использование как Queue/Deque

List<String> linkedList = new LinkedList<>();
linkedList.add("first");
linkedList.add(0, "new first"); // Вставка в начало - O(1)

Ключевые методы List

void add(int index, E element)      // Вставка по индексу
E get(int index)                     // Получение по индексу
E set(int index, E element)          // Замена элемента
E remove(int index)                  // Удаление по индексу
int indexOf(Object o)                // Поиск индекса элемента
List<E> subList(int from, int to)   // Подсписок (view)

Random Access vs Sequential Access

• Random Access (ArrayList): поддерживает маркер-интерфейс RandomAccess
• Sequential Access (LinkedList): итерация эффективнее индексированного доступа

Set - Коллекция уникальных элементов

Основные характеристики

• Уникальность: не допускает дубликаты
• Порядок: зависит от реализации
• Null-элементы: зависит от реализации
• Базируется на: обычно equals() и hashCode()

Реализации

HashSet

• Структура данных: Hash Table (хеш-таблица)
• Порядок: не гарантируется
• Производительность: O(1) для add, remove, contains (в среднем)
• Null-элементы: один null разрешен
• Когда использовать: быстрая проверка наличия элемента, порядок не важен

Set<String> hashSet = new HashSet<>();
hashSet.add("apple");
hashSet.add("banana");
hashSet.add("apple"); // Не добавится - дубликат
boolean contains = hashSet.contains("apple"); // O(1)

LinkedHashSet

• Структура данных: Hash Table + Linked List
• Порядок: сохраняется порядок добавления (insertion order)
• Производительность: O(1) для основных операций, немного медленнее HashSet
• Null-элементы: один null разрешен
• Когда использовать: нужна уникальность + предсказуемый порядок итерации

Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("first");
linkedHashSet.add("second");
// Итерация будет в порядке добавления

TreeSet

• Структура данных: Balanced Tree (красно-черное дерево)
• Порядок: отсортированный (natural ordering или Comparator)
• Производительность: O(log n) для add, remove, contains
• Null-элементы: не разрешены (с Java 7)
• Интерфейсы: реализует NavigableSet и SortedSet
• Когда использовать: нужна отсортированная коллекция уникальных элементов

Set<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.add(2);
treeSet.add(8);
// Итерация: 2, 5, 8 (отсортировано)

NavigableSet методы (TreeSet)

E lower(E e)        // Наибольший элемент < e
E floor(E e)        // Наибольший элемент <= e
E ceiling(E e)      // Наименьший элемент >= e
E higher(E e)       // Наименьший элемент > e
E pollFirst()       // Удалить и вернуть первый
E pollLast()        // Удалить и вернуть последний
NavigableSet<E> descendingSet()  // Обратный порядок

Queue - Очередь (FIFO)

Основные характеристики

• Порядок обработки: обычно FIFO (First-In-First-Out)
• Операции: добавление в хвост, извлечение из головы
• Два набора методов: throwing exceptions vs returning special values

Методы Queue

Queue<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
String head = queue.poll(); // "first", удаляет из очереди
String next = queue.peek(); // "second", не удаляет

Реализации Queue

LinkedList (как Queue)

• Двусвязный список, эффективен для Queue операций
• Поддерживает null-элементы

ArrayDeque

• Структура данных: Resizable Array (циклический массив)
• Производительность: быстрее LinkedList для Queue операций
• Null-элементы: не разрешены
• Рекомендуется для Stack и Queue вместо Stack и LinkedList

Queue<String> queue = new ArrayDeque<>();
queue.offer("task1");
queue.offer("task2");

PriorityQueue

• Структура данных: Binary Heap (куча)
• Порядок: основан на natural ordering или Comparator
• Производительность: O(log n) для offer и poll, O(1) для peek
• Null-элементы: не разрешены
• Не FIFO: элементы извлекаются по приоритету

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(2);
pq.offer(8);
pq.poll(); // 2 (наименьший элемент)

Deque - Double-Ended Queue

Основные характеристики

• Двусторонняя очередь: добавление/удаление с обоих концов
• Может работать как FIFO (Queue) или LIFO (Stack)

Методы Deque

Stack операции (через Deque)

Deque<String> stack = new ArrayDeque<>();
stack.push("first");  // addFirst
stack.push("second"); // addFirst
stack.pop();          // removeFirst → "second"
stack.peek();         // peekFirst → "first"

Реализации Deque

• ArrayDeque: рекомендуется (быстрее, без null)
• LinkedList: поддерживает null

Concurrent Collections

BlockingQueue

• Назначение: потокобезопасная очередь с блокировкой
• Методы: put(e) блокируется если очередь полная, take() блокируется если пустая

Реализации

• ArrayBlockingQueue: ограниченная очередь на массиве
• LinkedBlockingQueue: опционально ограниченная на linked nodes
• PriorityBlockingQueue: неограниченная очередь с приоритетами
• SynchronousQueue: нет внутреннего хранилища, каждая вставка ждет извлечения

BlockingDeque

• LinkedBlockingDeque: потокобезопасная двусторонняя очередь

Concurrent Set

• CopyOnWriteArraySet: для редких модификаций, частых чтений
• ConcurrentSkipListSet: потокобезопасная отсортированная set

Выбор реализации - Quick Reference

List

• ArrayList: по умолчанию, random access
• LinkedList: частые вставки/удаления, использование как Queue

Set

• HashSet: по умолчанию, максимальная скорость
• LinkedHashSet: предсказуемый порядок итерации
• TreeSet: отсортированная коллекция

Queue

• ArrayDeque: по умолчанию для Queue/Stack
• PriorityQueue: обработка по приоритету
• LinkedList: когда нужны null-элементы

Concurrent

• ConcurrentHashMap: потокобезопасная Map
• CopyOnWriteArrayList: редкие изменения, частые чтения
• BlockingQueue реализации: producer-consumer паттерн

Важные концепции

Modifiability

• Unmodifiable: нельзя изменять (add, remove, clear выбросят UnsupportedOperationException)
• Modifiable: можно изменять
• Immutable: неизменяемые, гарантия что объект не изменится
• Mutable: изменяемые

Создание unmodifiable коллекций

List<String> list = List.of("a", "b", "c");  // Java 9+, immutable
Set<String> set = Set.of("a", "b");          // Java 9+, immutable

// Из существующей коллекции
List<String> unmod = Collections.unmodifiableList(originalList);

Fail-Fast Iterators

• Большинство коллекций используют fail-fast итераторы
• Бросают ConcurrentModificationException при модификации во время итерации
• Исключение: можно использовать iterator.remove()

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
    list.remove(s); // ConcurrentModificationException!
}

// Правильно:
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (condition) {
        it.remove(); // OK
    }
}

RandomAccess маркер

if (list instanceof RandomAccess) {
    // Используем индексированный доступ
    for (int i = 0; i < list.size(); i++) {
        process(list.get(i));
    }
} else {
    // Используем итератор
    for (String s : list) {
        process(s);
    }
}

Performance Характеристики

* Амортизированное O(1), иногда O(n) при расширении массива
** O(1) если есть итератор на элемент

Типичные ошибки и best practices

1. Размер коллекции

// Плохо - много перевыделений
List<String> list = new ArrayList<>(); // capacity = 10
for (int i = 0; i < 10000; i++) {
    list.add("item" + i);
}

// Хорошо - указываем ожидаемый размер
List<String> list = new ArrayList<>(10000);

2. Выбор между equals и ==

// Set использует equals() для проверки уникальности
// Нужно правильно переопределить equals() и hashCode()

class Person {
    String name;
    int age;
    
    @Override
    public boolean equals(Object o) { ... }
    
    @Override
    public int hashCode() { ... }
}

3. Не использовать устаревшие классы

• ❌ Vector → ✅ ArrayList или CopyOnWriteArrayList
• ❌ Stack → ✅ ArrayDeque
• ❌ Hashtable → ✅ HashMap или ConcurrentHashMap

4. Синхронизация

// Для thread-safe коллекций используй concurrent пакет
Map<String, String> map = new ConcurrentHashMap<>();

// Или синхронизированные обертки (но concurrent лучше)
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

Итоги

1. List - упорядоченная коллекция с индексами и дубликатами
2. Set - коллекция уникальных элементов (HashSet, TreeSet, LinkedHashSet)
3. Queue - очередь FIFO, Deque - двусторонняя очередь
4. ArrayList - по умолчанию для List (O(1) доступ по индексу)
5. HashSet - по умолчанию для Set (O(1) операции)
6. ArrayDeque - по умолчанию для Queue/Stack (быстрее LinkedList)
7. Правильно переопределяй equals/hashCode для объектов в Set
8. Используй concurrent коллекции для многопоточности
9. Указывай initial capacity если знаешь размер заранее
10. Избегай устаревших классов (Vector, Stack, Hashtable)

Задания для практики

1. ArrayList vs LinkedList: Создай список из 100000 элементов. Сравни время вставки в начало и в конец для ArrayList и LinkedList.

2. HashSet для уникальности: Дан массив строк с дубликатами. Получи список уникальных строк, сохраняя порядок первого появления.

3. PriorityQueue: Реализуй систему обработки задач с приоритетом. Task(name, priority). Задачи должны обрабатываться в порядке убывания приоритета.

4. Deque как стек: Реализуй проверку сбалансированности скобок в строке “(())” используя ArrayDeque.

5. Fail-fast итератор: Продемонстрируй ConcurrentModificationException и покажи правильный способ удаления элементов во время итерации.