3685 подписчиков

Шпаргалка по структурам данных в java

31 августа 202431 авг 2024

116

9 мин

Оглавление

1. Array (Массив)
2. ArrayList
3. LinkedList

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

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

1. Array (Массив)

Описание: Статическая структура данных, фиксированного размера. Элементы располагаются в памяти последовательно. Индексация начинается с 0.

Пример инициализации:

Получение элемента:

Удаление элемента:

Прямого способа удаления нет. Для удаления элемента нужно создать новый массив без этого элемента или сдвинуть элементы вручную.

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

Плюсы:

Быстрая индексация (O(1)).
Простота использования.

Минусы:

Фиксированный размер.
Удаление и вставка элементов требуют сдвига (O(n)).

Комментарий: Используется, когда размер данных известен заранее.

Используется для: Хранения набора однотипных данных.

Актуальность: Актуальна.

2. ArrayList

Описание: Динамический массив, позволяет изменять размер во время выполнения программы. Основан на массиве.

Пример инициализации:

Получение элемента:

Удаление элемента:

Комментарий: Удобен для динамических наборов данных.

Плюсы:

Динамическое изменение размера.
Быстрая индексация (O(1)).

Минусы:

Удаление и вставка элементов в середину (O(n)).
Может потребоваться увеличение размера, что требует копирования (амортизированное O(1)).

Комментарий: Применяется чаще, чем обычные массивы, благодаря гибкости в размере.

Используется для: Хранения изменяемого набора данных.

Актуальность: Актуальна.

3. LinkedList

Описание: Двунаправленный связанный список. Каждый элемент содержит ссылку на предыдущий и следующий элемент.

Пример инициализации:

Получение элемента:

Удаление элемента:

Комментарий: Быстрое удаление и добавление элементов в середине списка.

Плюсы:

Быстрое добавление и удаление элементов (O(1)) при известной позиции.
Нет необходимости в сдвиге элементов.

Минусы:

Медленный доступ по индексу (O(n)).
Повышенные требования к памяти из-за хранения ссылок.

Комментарий: Предпочтительна для операций вставки/удаления в середине списка.

Используется для: Очередей, деков, списков с частыми вставками/удалениями.

Актуальность: Актуальна.

4. HashMap

Описание: Хранение пар "ключ-значение". Использует хеширование для быстрого доступа к данным.

Пример инициализации:

Получение элемента:

Удаление элемента:

Плюсы:

Быстрый доступ к элементам по ключу (O(1) в среднем случае).
Позволяет хранить null-ключи и значения.

Минусы:

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

Комментарий: Отличный выбор для хранения и быстрого поиска данных по ключу.

Используется для: Словарей, карт, ассоциативных массивов.

Актуальность: Актуальна.

5. TreeMap

Описание: Реализация интерфейса Map на основе красно-черного дерева. Хранит элементы в отсортированном порядке.

Пример инициализации:

Получение элемента:

Удаление элемента:

Комментарий: Поддерживает сортировку ключей.

Плюсы:

Доступ к элементам в отсортированном порядке (O(log n)).
Быстрый поиск минимального и максимального элемента.

Минусы:

Медленнее HashMap (O(log n) против O(1)).

Комментарий: Подходит для случаев, когда необходимо поддерживать порядок элементов.

Используется для: Сортированных карт, диапазонных запросов.

Актуальность: Актуальна.

6. HashSet

Описание: Коллекция уникальных элементов. Основана на HashMap.

Пример инициализации:

Получение элемента:

Нет прямого метода получения. Можно проверить наличие элемента.

Удаление элемента:

Комментарий: Отлично подходит для работы с уникальными элементами.

Плюсы:

Быстрая проверка на наличие элемента (O(1) в среднем случае).

Минусы:

Неупорядоченность элементов.
Нет дублирующихся элементов.

Комментарий: Используется, когда важна уникальность элементов.

Используется для: Хранения уникальных данных, удаления дубликатов.

Актуальность: Актуальна.

7. TreeSet

Описание: Коллекция уникальных элементов, хранящая элементы в отсортированном порядке. Основана на TreeMap.

Пример инициализации:

Получение элемента:

Нет прямого метода получения. Можно проверить наличие элемента.

Удаление элемента:

Комментарий: Поддерживает сортировку элементов.

Плюсы:

Отсортированность элементов.
Поддержка диапазонных операций.

Минусы:

Медленнее HashSet (O(log n) против O(1)).

Комментарий: Используется, когда важен порядок элементов.

Используется для: Хранения уникальных и отсортированных данных.

Актуальность: Актуальна.

8. LinkedHashMap

Описание: Комбинация HashMap и двусвязного списка. Сохраняет порядок вставки элементов.

Пример инициализации:

Получение элемента:

Удаление элемента:

Комментарий: Сохраняет порядок вставки элементов.

Плюсы:

Сохраняет порядок вставки.
Быстрая вставка и удаление (O(1)).

Минусы:

Немного медленнее HashMap из-за использования связного списка.

Комментарий: Хороший выбор, когда важен порядок вставки элементов.

Используется для: Кэшей, карт с сохранением порядка элементов.

Актуальность: Актуальна.

9. PriorityQueue

Описание: Очередь с приоритетом на основе бинарной кучи. Элементы извлекаются по приоритету.

Пример инициализации:

Получение элемента:

Удаление элемента:

Комментарий: Элементы извлекаются в порядке приоритета.

Плюсы:

Быстрая вставка и удаление элементов по приоритету (O(log n)).

Минусы:

Нет прямого доступа к элементам, кроме самого приоритетного.

Комментарий: Используется в алгоритмах, где важен приоритет обработки элементов.

Используется для: Планировщиков задач, алгоритмов поиска с приоритетом.

Актуальность: Актуальна.

10. Deque (ArrayDeque)

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

Пример инициализации:

Получение элемента:

Удаление элемента:

Плюсы:

Быстрая вставка и удаление с обоих концов (O(1)).

Минусы:

Ограничен функционал по сравнению с LinkedList.

Комментарий: Используется для реализации стеков и очередей с двухсторонним доступом.

Используется для: Реализации стека, очереди, дека.

Актуальность: Актуальна.

11. Stack

Описание: Последовательность элементов, работающая по принципу LIFO (Last In, First Out).

Пример инициализации:

Получение элемента:

Удаление элемента:

Плюсы:

Простая реализация LIFO структуры.

Минусы:

Устаревшая, рекомендуется использовать Deque.

Комментарий: Stack устарел и не рекомендуется к использованию. Лучше использовать Deque.

Используется для: Реализации стека, обработки рекурсий.

Актуальность: Устарела, рекомендуется Deque.

12. Vector

Описание: Динамический массив, синхронизированный для потокобезопасности.

Пример инициализации:

Получение элемента:

Удаление элемента:

Плюсы:

Потокобезопасен.

Минусы:

Медленнее ArrayList из-за синхронизации.
Синхронизация не всегда необходима.

Комментарий: Vector устарел и редко используется. Лучше использовать ArrayList и синхронизировать его вручную, если нужно.

Используется для: Потокобезопасных динамических массивов.

Актуальность: Устарела, рекомендуется ArrayList.

13. ConcurrentHashMap

Описание: Потокобезопасная версия HashMap, оптимизированная для многопоточного доступа.

Пример инициализации:

Получение элемента:

Удаление элемента:

Плюсы:

Высокая производительность при многопоточном доступе.
Частично блокируемая, что снижает время ожидания блокировок.

Минусы:

Сложнее в понимании, чем обычные карты.

Комментарий: Отличный выбор для многопоточных приложений.

Используется для: Потокобезопасных карт в многопоточных приложениях.

Актуальность: Актуальна.

14. WeakHashMap

Описание: Реализация Map с использованием слабых ссылок на ключи. Элементы могут быть удалены сборщиком мусора.

Пример инициализации:

Получение элемента:

Удаление элемента:

Комментарий: Элементы могут быть удалены сборщиком мусора.

Плюсы:

Автоматическое удаление элементов, на которые нет сильных ссылок.

Минусы:

Меньшая надежность хранения данных, так как элементы могут быть удалены сборщиком мусора.

Комментарий: Используется для кэшей, где важна автоматическая очистка.

Используется для: Кэшей с автоматической очисткой.

Актуальность: Актуальна.

15. IdentityHashMap

Описание: Реализация Map, использующая сравнение по ссылкам (==) вместо метода equals().

Пример инициализации:

Получение элемента:

Удаление элемента:

Комментарий: Подходит для уникальных ситуаций, где нужно сравнивать объекты по ссылкам.

Плюсы:

Позволяет различать одинаковые объекты по ссылке.

Минусы:

Необычное поведение для большинства пользователей.

Комментарий: Используется в специфических случаях, когда нужно различать объекты по ссылке.

Используется для: Специфических задач, где важно сравнение по ссылке.

Актуальность: Актуальна.

16. EnumMap

Описание: Реализация Map, специально предназначенная для использования с перечислениями (enum).

Пример инициализации:

Получение элемента:

Удаление элемента:

Плюсы:

Высокая производительность для enum-ключей.
Низкое потребление памяти.

Минусы:

Ограничена использованием только с enum.

Комментарий: Идеально подходит для карт с enum в качестве ключей.

Используется для: Карт с ключами типа enum.

Актуальность: Актуальна.

17. BitSet

Описание: Массив битов, где каждый бит может быть 0 или 1.

Пример инициализации:

Получение элемента:

Удаление элемента:

Плюсы:

Экономия памяти для больших наборов битов.
Быстрая работа с битовыми операциями.

Минусы:

Ограничен использованием только для битов.

Комментарий: Используется для работы с булевыми массивами, битовыми масками.

Используется для: Булевых массивов, битовых масок.

Актуальность: Актуальна.

18. Queue(LinkedList)

Описание: Интерфейс для представления очереди, работающей по принципу FIFO (First In, First Out).

Пример инициализации:

Получение элемента:

Удаление элемента:

Плюсы:

Простой интерфейс для работы с очередями.

Минусы:

Реализации могут иметь различную производительность.

Комментарий: Используется для очередей задач, событий и других структур, где важен порядок обработки.

Используется для: Очередей задач, событий.

Актуальность: Актуальна.

19. Deque (LinkedList)

Описание: Двусторонняя очередь, основанная на двусвязном списке.

Пример инициализации:

Получение элемента:

Удаление элемента:

Плюсы:

Динамическое изменение размера.
Быстрая вставка и удаление с обоих концов.

Минусы:

Медленнее, чем ArrayDeque для некоторых операций.

Комментарий: Используется для реализации стеков и очередей с двухсторонним доступом.

Используется для: Стеков, очередей, деков.

Актуальность: Актуальна.

Итог:

Array и ArrayList подходят для статических и динамических массивов соответственно.
LinkedList хорош для частых вставок и удалений элементов.
HashMap, TreeMap, LinkedHashMap используются для хранения пар "ключ-значение" с различными требованиями к порядку и производительности.
HashSet и TreeSet - для хранения уникальных элементов.
PriorityQueue и Deque - для очередей с различными требованиями к приоритету и доступу.
Stack и Vector устарели, и их заменили Deque и ArrayList.
Специфические структуры, такие как ConcurrentHashMap, WeakHashMap, IdentityHashMap, EnumMap и BitSet, используются для специальных задач.