Шпаргалка по структурам данных в Java01.08.2023 09:31

7a4eb92a8cb4aaf384d83f7cc1f399f5

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

Что такое структуры данных, для чего они и какие есть в Java?

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

Массив

Массив — это нумерованный набор переменных одного типа.

Объявляется следующем образом: 

int[] arr = new int[10];

  • Все массивы в Java одномерные. В случае с многомерными массивами каждый элемент содержит только ссылку на вложенный массив

  • Можно создать нулевого размера, может быть полезно если нужно вернуть пустой массив из какого-либо метода

  • Оператор new используется для создания ссылочного типа данных. Ссылка хранится на стеке, а объект в куче. Если на объект нет ссылок, то он будет удалён автоматически. Удаление объекта может быть осуществлено с задержкой

Список (Динамический массив)

Идея списка или же динамического массива заключается в автоматическом расширении емкости.

Объявляется следующем образом: 

ArrayList arr = new ArrayList();

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

  • Если не указать в конструктор начальную емкость, то будет создан пустой список с емкостью в 10 элементов

  • В случае, когда зарезервированной емкости не хватает, при достижении максимального количества элементов будет создан новый массив с емкостью: новая_емкость = (старая_емкость * 3) / 2 + 1. Существующие элементы списка будут скопированы в новый массив

  • Чтобы не тратить память напрасно, при удалении элементов следует вызывать метод trimToSize ()

Плюсы и минусы

+ доступ к элементам по индексу за O (1), к элементам по значению за O (n);
+ можно хранить любые значения и даже null.


— вставка или удаление элемента в середину списка вызывает перезапись всех элементов, работает за O (n);
— поиск за O (n);
— не синхронизирован.

Стек

Очередь работает по принципу LIFO. В Java наследуется от Vector, реализует следующие интерфейсы: Iterable, Collection, List, RandomAccess, Serializable, Cloneable.

Объявляется следующем образом: 

Stack arr = new Stack();

Основные методы

  • push () — добавляет в конец очереди;

  • peek () — возвращает последний элемент и не удаляет его;

  • pop () — удаляет последний элемент и возвращает его;

  • empty () — вернет true — если очередь пуста и false — в противном случае;

  • search () — возвращает номер позиции с конца очереди.

Очередь

Интерфейс Queue описывает одностороннюю очередь, а Deque — двухстороннюю. Прежде чем перейти к объявлению в Java, стоит отметить иерархию наследования. Иерархия следующая:

Интерфейсы Queue и Deque реализуют следующие классы:

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

  • LinkedList — связный список

  • PriorityQueue — очередь с приоритетами

Объявляется следующем образом: 

Queue arr = new ArrayDeque();
Deque arr1 = new ArrayDeque();
PriorityQueue arr2 = new PriorityQueue();
// Очередь на LinkedList'е
Queue arr = new LinkedList();
Deque arr = new LinkedList();

Разница между реализацией на листе и деку

  • ArrayDeque реализует дек на массиве, поэтому он эффективнее по памяти и работает быстрее, чем LinkedList

Пару слов о PriorityQueue.
Этот класс реализует следующие интерфейсы: Iterable, Collection, Queue, Serializable. У этого класса есть свои особенности:

  • Из очереди первым возвращается элемент с наибольшим приоритетом

  • Значение null добавить нельзя

Связный список

LinkedList реализует связный список, элементы которого хранят ссылки на предыдущий и следующий элементы.

Класс реализует следующие интерфейсы:
Iterable, Collection, List, Queue, Deque, Serializable, Cloneable.

Объявляется следующем образом: 

LinkedList arr = new LinkedList();

Сравнение ArrayList и LinkedList по сложности выполнения операций

Операция

ArrayList

LinkedList

add (E element)

O (1)
O (n) — при копировании

O (1)

add (int index, E element)

O (n/2) — с середины
O (n) — с начала
O (1) — с конца

O (n/4)
O (n) — в конец или начало

remove (int index)

O (n/2) — с середины
O (n) — с начала
O (1) — с конца

O (n/4)
O (n) — в конец или начало

get (int index)

O (1)

O (n/4)

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

HashTable и HashMap

HashTable считается устаревшей, поэтому приведена лишь разница между мапой и таблицей. HashMap используется для хранения пары «ключ-значение». В качестве примера использования хэш-мапы можно привести пациента больницы, у которого есть Ф.И. О.и номер медицинского полиса.

  • Если конструктору не передать никаких значений, то будет создан пустой словарь с емкостью в 16 элементов и коэффициентом заполнения 0.75

  • Если коэффициент заполнения достигает максимума, то число bucket’ов увеличивается в два раза

Класс HashMap реализует следующие интерфейсы:
Map, Serializable, Cloneable.

Объявляется следующем образом: 

HashMap map = new HashMap();

Разница между HashTable и HashMap

  • Хэш-Таблица не может хранить null, в отличии от Хэш-Мапы

  • В Хэш-Таблице все методы синхронизированы, что сказывается на скорости работы

  • Хэш-Таблица не рекомендуется к использования, так как считается устаревшей, Хэш-Мапа предпочтительнее

    P.S. Если требуется выбрать структуру, которая справится с параллельными вычислениями, то есть ConcurrentHashMap

Дерево

TreeMap и TreeSet описывают словари, в котором ключи хранятся в отсортированном порядке. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов.

Класс TreeSet реализует следующие интерфейсы:
Itearble, Collection, Set, SortedSet, NavigatbleSet, Serializable, Cloneable.

Класс TreeMap реализует следующие интерфейсы:
Map, SortedMap, NavigatbleMap, Serializable, Cloneable.

Преимущества иерархической организации данныхНедостатки

  • медленный доступ к данным нижних уровней;

  • склонность к избыточности;

  • на больших объёмах данных требуется индексация элементов.

Объявляется следующем образом: 

TreeSet set = new TreeSet();
TreeMap map = new TreeMap();

В чем разница между HashSet и TreeSet

  • Под капотом у TreeSet лежит красно-черное дерево и упорядочивание элементов происходит именно по принципу красно-черных деревьев. HashSet не поддерживает упорядочивание

  • Сложность TreeSet — O (log (n)), HashSet — O (1) (речь идет о методах add (), contains (), remove ())

Заключение

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


Желаю вам успехов и благодарю за интерес к моей публикации!

Источники

© Habrahabr.ru