Какие знаешь структуры данных из Collection кроме Map?

Структуры данных Java Collection Framework

Java Collection Framework предоставляет множество структур данных для хранения и обработки групп объектов. Разберемся с основными кроме Map.

1. List — упорядоченная коллекция

List хранит элементы в определенном порядке, позволяет дублирование и доступ по индексу.

ArrayList

// Динамический массив, основан на массиве
List<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add(0, "C++");  // вставка в начало

// O(1) доступ по индексу
String first = list.get(0);

// O(n) вставка/удаление в начало
list.remove(0);

// Итерирование
for (String item : list) {
    System.out.println(item);
}

LinkedList

// Двусвязный список
List<Integer> linked = new LinkedList<>();
linked.add(1);
linked.add(2);
linked.addFirst(0);      // O(1) добавление в начало
linked.addLast(3);       // O(1) добавление в конец

int first = linked.removeFirst();  // O(1) удаление с начала
int last = linked.removeLast();     // O(1) удаление с конца

// O(n) доступ по индексу
int element = linked.get(1);

Vector

// Синхронизированный ArrayList (устаревший)
List<String> vector = new Vector<>();
vector.add("element");
// Не рекомендуется использовать, есть Collections.synchronizedList()

2. Set — неупорядоченная коллекция уникальных элементов

Set не содержит дубликатов и не гарантирует порядок (кроме подклассов).

HashSet

// Основан на HashMap, быстрый поиск
Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple");  // дубликат, не добавится

System.out.println(set.size());  // 2
boolean exists = set.contains("Apple");  // O(1)

// Порядок не гарантирован
for (String item : set) {
    System.out.println(item);
}

LinkedHashSet

// HashSet с гарантированным порядком вставки
Set<String> linked = new LinkedHashSet<>();
linked.add("First");
linked.add("Second");
linked.add("Third");

// Выведет в порядке вставки
for (String item : linked) {
    System.out.println(item);
}

TreeSet

// Отсортированный Set на основе красно-черного дерева
Set<Integer> tree = new TreeSet<>();
tree.add(5);
tree.add(2);
tree.add(8);
tree.add(1);

// Автоматически отсортирован
for (Integer num : tree) {
    System.out.println(num);  // 1, 2, 5, 8
}

// Полезные методы
int first = tree.first();        // 1
int last = tree.last();          // 8
Set<Integer> subset = tree.subSet(2, 8);  // элементы от 2 до 8 (не включая 8)

3. Queue — очередь (FIFO)

Queue работает по принципу "первый пришел, первый ушел".

LinkedList как Queue

// LinkedList имплементирует Queue
Queue<String> queue = new LinkedList<>();
queue.add("First");      // добавить в конец
queue.offer("Second");   // альтернатива add()

String first = queue.peek();   // O(1) посмотреть первый элемент
first = queue.poll();          // O(1) удалить и вернуть первый
first = queue.remove();        // O(1) удалить и вернуть первый (исключение если пусто)

PriorityQueue

// Очередь с приоритетом, основана на куче (heap)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(2);
pq.add(8);

// Извлекаются в порядке приоритета (по умолчанию минимум первый)
while (!pq.isEmpty()) {
    System.out.println(pq.poll());  // 2, 5, 8
}

// С кастомным компаратором
PriorityQueue<Integer> maxPq = new PriorityQueue<>(
    Comparator.reverseOrder()
);
maxPq.add(5);
maxPq.add(2);
maxPq.add(8);
while (!maxPq.isEmpty()) {
    System.out.println(maxPq.poll());  // 8, 5, 2
}

4. Deque — двусторонняя очередь

Deque позволяет добавлять и удалять элементы с обоих концов.

// Двусвязный список имплементирует Deque
Deque<String> deque = new LinkedList<>();

// Операции с началом
deque.addFirst("First");     // добавить в начало
deque.removeFirst();         // удалить с начала
String first = deque.getFirst();  // получить начало

// Операции с концом
deque.addLast("Last");       // добавить в конец
deque.removeLast();          // удалить с конца
String last = deque.getLast();    // получить конец

// Также может использоваться как LIFO (Stack)
deque.push("Value");         // добавить в начало
String value = deque.pop();  // удалить с начала

5. Таблица сравнения

*На началo/конец

Итог

Выбор структуры зависит от требований:

• Нужен доступ по индексу? → ArrayList
• Часто удаляю/добавляю в начало? → LinkedList
• Нужны только уникальные элементы? → HashSet
• Нужна сортировка? → TreeSet
• FIFO очередь? → Queue (LinkedList)
• Приоритеты? → PriorityQueue