Collection

Интерфейс для поэлементного обхода коллекций в Java. Позволяет безопасно удалять элементы во время обхода.

List<String> list = Arrays.asList("A", "B", "C");
Iterator<String> iterator = list.iterator();

while (iterator.hasNext()) {
    String item = iterator.next();
    System.out.println(item);
}

Базовый интерфейс для работы с коллекциями в Java.

Интерфейс коллекций, представляющий упорядоченный список элементов.

List<String> list = List.of("one", "two"); // Только для чтения

Реализован внутри в виде обычного массива. Поэтому при вставке элемента в середину, приходится сначала сдвигать на один все элементы после него, а уже затем в освободившееся место вставлять новый элемент. Минусы в скорости вставки/удаления элементов находящихся не в конце списка, так как при этой операции все элементы правее добавляемого/удаляемого сдвигаются. Размер по умолчанию - 10

• Начальный размер (capacity) равен 10, при добавлении размер увеличивается в среднем в 1.5 раз и элементы копируются, старый удаляется gc.

• При удалении элемента размер массива не уменьшается, capacity не меняется (есть метод trimToSize()).

• Если известно примерное количество элементов, указать capacity, чтобы не тратить ресурсы на расширение списка.

ArrayList<String> list = new ArrayList<>();
List<String> unmodifiableList = Collections.unmodifiableList(list); // только для чтения

Реализован в виде связного списка: набора отдельных элементов, каждый из которых хранит ссылку на следующий и предыдущий элементы. Чтобы вставить элемент в середину списка, достаточно поменять ссылки его будущих соседей. А вот чтобы получить элемент с номером 130, нужно пройтись последовательно по всем объектам от 0 до 130. Другими словами операции set и get очень медленные. Если необходимо вставлять (или удалять) в середину коллекции много элементов и гарантировать время этих операций, то лучше использовать LinkedList, в остальных случаях – ArrayList. LinkedList требует больше памяти для хранения такого же количества элементов, потому что кроме самого элемента хранятся еще указатели на соседей, тогда как в ArrayList элементы просто идут по порядку. LinkedList - вагоны поезда, сцепленные последовательно. Операции доступа по индексу производятся перебором с начала или конца (смотря что ближе) до нужного элемента. Как в LinkedList вставить новый элемент в середину списка: сначала проверяем наш capacity сдвигаем все что справа элементы и вставляем туда новый. если места не хватает выделяется память в 2 раза больше нынешнего capacity создается новый массив и все элементы копируются. чтобы оптимизировать память нужно задавать размер списка capacity изначально

• LinkedList не синхронизирован.

• Позволяет хранить любые объекты, в том числе null и повторяющиеся.

LinkedList<String> list = new LinkedList<>();

Интерфейс, который предоставляет коллекцию уникальных элементов, не допускающих дубликатов.

• Элементы уникальны — нельзя добавить дубликат.

• Порядок хранения элементов зависит от реализации.

• Реализации: HashSet LinkedHashSet TreeSet.

Set set = new HashSet();

// Добавление элементов
set.add("Apple");
set.add("Banana");

// Проверка наличия элемента
boolean hasApple = set.contains("Apple"); // true

// Удаление элемента
set.remove("Apple");

// Размер множества
int size = set.size(); // 1, после удаления Apple

// Очистка множества
set.clear();

Коллекция, которая хранит уникальные элементы без сохранения порядка. Она основана на хэш-таблице, что позволяет быстро выполнять операции вставки, удаления и поиска за O(1) в среднем случае.

• Элементы уникальны — нельзя добавить дубликат.

• Порядок элементов не гарантируется.

• Использует хэш-функции: для быстрого доступа к элементам и их распределения по хэш-таблице.

Set<String> hashSet = new HashSet<>();
hashSet.add("Dog");
hashSet.add("Cat");
hashSet.add("Bird");

System.out.println(hashSet); // Порядок может быть любым, например: [Bird, Cat, Dog]

Алгоритмическая сложность операций

В худшем случае, при коллизиях (когда хэш-функция распределяет элементы неравномерно), сложность этих операций может возрасти до O(n), где n — количество элементов в множестве.

Реализация интерфейса Set, основанная на хэш-таблице с двухсвязным списком для поддержания порядка добавления элементов. Это означает, что LinkedHashSet сочетает в себе преимущества быстрого доступа за счет использования хэш-таблицы, как у HashSet, и сохранения порядка вставки элементов, как у списка.

• Элементы уникальны — нельзя добавить дубликат.

• Элементы сохраняются в порядке добавления.

• Несмотря на порядок вставки, прямой доступ к элементам по индексу, как в списках, невозможен. Для работы с элементами LinkedHashSet нужно использовать итераторы или циклы.

Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Dog");
linkedHashSet.add("Cat");
linkedHashSet.add("Bird");

System.out.println(linkedHashSet); // Порядок: [Dog, Cat, Bird]

Алгоритмическая сложность операций

В худшем случае сложность может возрасти до O(n) из-за коллизий, но это редко происходит при хороших хэш-функциях.

Реализация интерфейса Set, которая хранит элементы в отсортированном порядке. Он основан на красно-черном дереве, что обеспечивает логарифмическое время для основных операций.

• Элементы уникальны — нельзя добавить дубликат.

• Элементы хранятся в естественном порядке (или согласно заданному компаратору).

• Реализует интерфейсы NavigableSet и SortedSet.

• Не позволяет хранить null элементы, так как не может определить их порядок.

Set<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.add(2);
treeSet.add(9);

System.out.println(treeSet); // Порядок: [2, 5, 9]

Алгоритмическая сложность операций

public static void main(String[] args) {
    // Создаем отсортированный набор
    SortedSet<Integer> sortedSet = new TreeSet<>();

    // Добавление элементов
    sortedSet.add(5);
    sortedSet.add(1);
    sortedSet.add(3);
    sortedSet.add(7);
    sortedSet.add(2);

    // Печатаем элементы в отсортированном порядке
    System.out.println("SortedSet: " + sortedSet); // Output: SortedSet: [1, 2, 3, 5, 7]

    // Получение первого и последнего элемента
    Integer first = sortedSet.first(); // 1
    Integer last = sortedSet.last(); // 7
    System.out.println("First element: " + first); // Output: First element: 1
    System.out.println("Last element: " + last); // Output: Last element: 7

    // Получение подмножества
    SortedSet<Integer> subSet = sortedSet.subSet(2, 6);
    System.out.println("SubSet (2 to 6): " + subSet); // Output: SubSet (2 to 6): [2, 3, 5]

    // Получение части набора до определенного элемента
    SortedSet<Integer> headSet = sortedSet.headSet(5);
    System.out.println("HeadSet (up to 5): " + headSet); // Output: HeadSet (up to 5): [1, 2, 3]

    // Получение части набора от определенного элемента
    SortedSet<Integer> tailSet = sortedSet.tailSet(3);
    System.out.println("TailSet (from 3): " + tailSet); // Output: TailSet (from 3): [3, 5, 7]
}

public static void main(String[] args) {
    NavigableSet<Integer> navigableSet = new TreeSet<>();

    // Добавление элементов
    navigableSet.add(5);
    navigableSet.add(3);
    navigableSet.add(8);
    navigableSet.add(1);

    // Получение первого и последнего элемента
    Integer first = navigableSet.first(); // 1
    Integer last = navigableSet.last(); // 8

    // Получение элементов, соседних с 5
    Integer lower = navigableSet.lower(5); // 3
    Integer higher = navigableSet.higher(5); // 8

    // Удаление первого элемента
    Integer removedFirst = navigableSet.pollFirst(); // 1

    // Итерация по элементам
    for (Integer number : navigableSet) {
        System.out.println(number); // 3, 5, 8
    }
}

Интерфейс в Java, представляющий структуру данных «очередь». Она основана на принципе FIFO (First-In-First-Out).

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();

        // Добавляем элементы
        deque.addFirst("First");
        deque.addLast("Last");

        // Получаем элементы
        System.out.println(deque.peekFirst()); // First
        System.out.println(deque.peekLast());  // Last

        // Удаляем элементы
        System.out.println(deque.pollFirst()); // First
        System.out.println(deque.pollLast());  // Last
    }
}

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Добавляем элементы
        pq.add(5);
        pq.add(1);
        pq.add(3);

        // Обрабатываем по приоритету (минимум первым)
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 1, 3, 5
        }
    }
}

Интерфейс в Java для работы с коллекцией пар «ключ-значение». Каждый ключ уникален, а значения могут повторяться.

• Не наследуется от Collection - это отдельная структура данных.

Реализация интерфейса Map, основанная на красно-черном дереве. Элементы упорядочены по ключам в соответствии с их естественным порядком или переданным компаратором.

TreeMap<String, Integer> treeMap = new TreeMap<>();

Класс в Java для работы с коллекцией пар «ключ-значение». Он похож на HashMap, но синхронизирован, что делает его потокобезопасным, хотя и менее производительным.

Hashtable<String, Integer> table = new Hashtable<>();

• List (9)

  1. На чем основана реализация ArrayList и LinkedList?

     ArrayList - на массиве. LinkedList - на связном списке.

  2. Разница между List и ArrayList?

     List — это интерфейс, представляющий упорядоченные коллекции, тогда как ArrayList — его реализация, основанная на массиве. ArrayList предоставляет динамический размер и методы для работы с элементами, а List — лишь общие контракты для различных реализаций списка.

  3. В чем разница между ArrayList и LinkedList?

     ArrayList хранит элементы в виде динамического массива, обеспечивая быстрый доступ по индексу O(1), но вставка и удаление элементов в середине списка может быть медленной O(n), так как требует сдвига элементов.

     LinkedList реализован как двусвязный список, где каждый элемент содержит ссылку на следующий и предыдущий. Это позволяет эффективно вставлять и удалять элементы O(1), но доступ к элементам по индексу медленный O(n), так как нужно последовательно проходить список.

  4. Где доступ к элементу быстрее в ArrayList или в LinkedList?

     Быстрее в ArrayList, так как он реализован на основе массива, и доступ к элементам осуществляется за O(1). В LinkedList доступ (кроме first и last) требует обхода списка и выполняется за O(n), так как это двусвязный список.

  5. Когда в Android удобнее применять LinkedList?

     • Когда требуется частое добавление и удаление элементов из середины списка.

     • Когда размер списка непредсказуем и необходимо минимизировать затраты на перераспределение памяти.

  6. Какова скорость базовых операций у ArrayList?

     • get O(1).

     • add в конец списка O(1). в начало или в середину O(n).

     • remove из конца списка O(1). из начала или середины O(n).

  7. Какова скорость базовых операций у LinkedList?

     • get O(n).

     • add в начало или конец списка O(1). в середину списка O(n).

     • remove из начала или конца списка O(1). из середины списка O(n).

  8. Как происходит вставка нового элемента в ArrayList?

     • Проверка размера: Если размер массива меньше capacity, элемент добавляется в следующую свободную позицию.

     • Увеличение емкости: Если размер равен capacity, создается новый массив с удвоенной емкостью, и элементы копируются в него.

     • Сдвиг элементов: При вставке не в конец сдвигаются элементы вправо.

     • Добавление элемента: Элемент помещается в нужную позицию, и размер списка увеличивается.

  9. Какая сложность поиска элемента в LinkedList по идексу?

     • 0(1) (константная)

     • 0(n) (линейная)

     • 0(log n) (логарифмическая)

     • 0 (n^2) (квадратичная)

• Set (8)

  1. Как устроен HashSet?

     HashSet реализован на основе HashMap, где каждый элемент хранится как ключ, а значение по умолчанию — это константа. Для хранения элементов используется хэширование, чтобы быстро определять их наличие. HashSet не допускает дубликатов, так как для каждого добавляемого элемента проверяется, существует ли уже такой ключ в соответствующем HashMap.

  2. Как HashSet выглядит под капотом?

     HashSet в исходниках Java представляет собой коллекцию, построенную на основе HashMap. Ключи хранятся в HashMap, а значения всегда равны фиксированной константе PRESENT (просто new Object()). Операции add(), remove() и другие опираются на методы HashMap.

  3. Как реализована TreeMap?

     Реализован на основе красно-черного дерева.

  4. Разница между HashSet и LinkedHashSet?

     HashSet не сохраняет порядок элементов и использует хэш-таблицу для хранения, что обеспечивает быструю проверку на наличие. LinkedHashSet сохраняет порядок вставки, используя связанный список, что делает его более подходящим, если важен порядок. Оба класса не допускают дубликатов, но LinkedHashSet обеспечивает предсказуемость итерации.

  5. Гарантирует ли HashSet порядок элементов?

     Нет, элементы в HashSet хранятся в произвольном порядке, который может изменяться при добавлении или удалении элементов. Если нужен порядок добавления элементов, следует использовать LinkedHashSet.

  6. Как разрешаются коллизии в HashSet?

     В HashSet коллизии разрешаются с помощью внутренней структуры данных — HashMap. Если два элемента имеют одинаковый хэшкод, они попадают в один и тот же бакет. Если ключи неравны по методу equals, оба элемента будут храниться в этом бакете в виде цепочки. Если ключи одинаковы, второй элемент заменит первый.

  7. Почему в HashSet одинаковые значения игнорируются а в HashMap перетираются?

     Потому что в HashSet хранятся только ключи, а они не перезаписываются.

  8. Нужно ли переопределять оба метода - equals и hashCode для объектов HashSet?

     Да, необходимо переопределять оба метода equals и hashCode для объектов, используемых в HashSet, чтобы гарантировать корректное поведение коллекции. Если два объекта считаются равными по методу equals, они должны иметь одинаковый хэш-код, чтобы избежать проблем с хранением и поиском в HashSet.

• Map (6)

  1. Как устроен Map?

     Это коллекция пар «ключ-значение», где каждому ключу соответствует одно значение. Наиболее распространённая реализация — это HashMap.

  2. Почему Map не наследуется от Collection?

     Map не наследуется от Collection потому, что оперирует парами «ключ-значение», а Collection работает с отдельными элементами, их структуры различны.

  3. Гарантирует ли Map порядок элементов?

     • HashMap не гарантирует порядок элементов.

     • LinkedHashMap сохраняет порядок вставки элементов.

     • TreeMap упорядочивает элементы по возрастанию ключей.

  4. Как расположить элементы в Map в порядке добавления?

     Использовать LinkedHashMap.

  5. Что такое TreeMap?

     TreeMap реализует интерфейс NavigableMap и представляет собой отсортированную по ключам структуру данных на основе красно-черного дерева. Он обеспечивает логарифмическую сложность для операций поиска, вставки и удаления. Ключи в TreeMap всегда находятся в отсортированном порядке, что позволяет легко выполнять операции диапазонных запросов.

  6. Разница между HashMap и Hashtable?

     Hashtable потокобезопасен, не допускает null, наследуется от Dictionary, синхронизирован.

• Stack (3)

  1. Как устроен стек?

     Это структура данных с принципом «последний пришёл — первый вышел» (LIFO), где операции добавления (push) и удаления (pop) выполняются только с верхним элементом. Он хранит указатель на верхний элемент и может быть реализован с помощью массива или связного списка. Стек используется для управления памятью, например, в рекурсии, и для реализации алгоритмов.

  2. Стек это LIFO или FIFO?

     Стек — это структура данных, работающая по принципу LIFO (Last In, First Out), то есть последний добавленный элемент будет извлечён первым.

  3. Сколько стеков может быть в процессе?

     В процессе может быть только один стек вызовов. Он используется для отслеживания активных функций, методов и объектов, а также для управления памятью.

• Queue (2)

  1. Как устроена очередь?

     Это структура данных, работающая по принципу «первый пришёл — первый вышел» (FIFO). В очереди элементы добавляются в конец (enqueue) и удаляются из начала (dequeue). Она поддерживает два основных указателя: один на начало, другой на конец. Очередь может быть реализована с помощью массива или связного списка. Эта структура часто используется в задачах, связанных с управлением задачами, обработкой данных и реализацией алгоритмов, таких как обход графов.

  2. Какие типы очередей бывают?

     • ArrayDeque двусторонняя очередь.

     • PriorityQueue приоритетная очередь.

• Другие (5)

  1. Какие коллекции есть в Java?

     • List ArrayList LinkedList

     • Set HashSet

     • Map HashMap

  2. Какие методы есть у Collection?

     • add(E e) добавляет элемент в коллекцию.

     • remove(Object o) удаляет элемент, если он присутствует.

     • size() возвращает количество элементов.

     • clear() удаляет все элементы.

     • contains(Object o) проверяет наличие элемента.

     • isEmpty() проверяет, пуста ли коллекция.

     • iterator() возвращает итератор для обхода элементов.

     • toArray() преобразует коллекцию в массив.

     • addAll(Collection<? extends E> c) добавляет все элементы другой коллекции.

  3. Чем между собой отличаются Set, Map и List?

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

     • Set хранит уникальные элементы без дубликатов, порядок не гарантирован (в некоторых реализациях, как LinkedHashSet, сохраняется порядок).

     • Map хранит пары «ключ-значение», где ключи уникальны, а значения могут повторяться.

  4. Расскажи про паттерн Iterator?

     Паттерн Iterator предоставляет способ последовательного доступа к элементам коллекции без раскрытия ее внутренней структуры. В этом паттерне используется объект-итератор, который реализует методы для перебора элементов (например, hasNext() и next()) и отделяет логику обхода от структуры данных, позволяя абстрагироваться от конкретного типа коллекции.

  5. Являются ли деревья и графы одним семейством структур данных?

     Да, деревья и графы относятся к одному семейству структур данных. Деревья являются частным случаем графов с ограничениями, такими как отсутствие циклов и единственный корень. Оба типа структур помогают организовать данные в виде узлов и рёбер.