Структуры данных java это

В закладки: подборка статей о структурах данных — лекции и вопросы на собеседованиях

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

Материалы о структурах данных

Статьи и лекции

Структуры данных — стек и очередь

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

Структуры данных: пирамида (двоичная куча) в Java

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

Структуры данных: двоичное дерево в Java

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

Ответы на самые популярные вопросы об интерфейсе Map

Map — это структура данных, которая содержит набор пар “ключ-значение”. По своей структуре данных напоминает словарь, поэтому ее часто так и называют. В то же время, Map является интерфейсом, и в стандартном jdk содержит основные реализации: Hashmap , LinkedHashMap , Hashtable , TreeMap . В статье отвечают на самые популярные вопросы о Map .

Массивы в Java

Это подробная “энциклопедия” расскажет обо всем, что нужно знать о массивах со старта: что это такое, как объявлять, создавать массив, что такое длина массива, а также о том, как инициализировать массив и вывести его на экран.

HashMap в Java — что за карта такая?

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

Особенности TreeMap

Лекция для тех, кто уже знаком с интерфейсом Map и вариантами его применения. В ней рассказывается об особенностях реализации TreeMap , а конкретнее — чем она отличается от HashMap и как правильно ее использовать.

ArrayList в Java

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

LinkedList

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

Видеоролики

Префиксные деревья в Java

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

Самый частый вопрос на собеседованиях — коллекции, hashCode и equals

Изучение структуры данных в Java невозможно представить без классов HashMap , TreeMap и LinkedHashMap . В этом видео Java- и Kotlin-разработчик Илья Никсан провел детальный анализ различий между этими классами, их свойств и вариантов применения.

Структуры данных в “вопросах и ответах на собеседованиях”

Что могут спросить на собеседовании: структуры данных в Java. Часть 1

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

Что могут спросить на собеседовании: структуры данных в Java. Часть 2

В продолжение предыдущего текста о вопросах, которые могут спросить по теме структур данных, автор разбирает темы Map , List , HashMap и другие.

Бонус

Рецензия на книгу: «Структуры данных и алгоритмы Java», Роберт Лафоре

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

Источник

Что могут спросить на собеседовании: структуры данных в Java. Часть 1

Привет! Как ни крути, вам не стать разработчиком без успешного прохождения входного технического собеседования. Технологий, связанных с Java, очень много, и выучить все невозможно. Что-то специфическое, как правило, на собеседованиях спрашивают только в том случае, если ищут разработчика с хорошим опытом в каком-то важном для проекта фреймворке. Если это так, вас будут гонять по этому фреймворку во весь рост, вы уж не сомневайтесь.Но мы сейчас говорим о базе, которую должен знать каждый Java developer. О тех классических знаниях, с которых все и начинается. Сегодня хотелось бы затронуть одну из основополагающих тем любого собеседования — структуры данных в Java . Итак, вместо хождения вокруг да около, мы начнем. Ловите список вопросов, которые могут вам задать по этой теме на собеседовании.

1. Расскажите немного о структурах данных

• массивы,
• стеки,
• очереди,
• связанные списки,
• графы,
• деревья,
• префиксные деревья,
• хэш таблицы.

2. Что вы знаете о Массивах?

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

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

Так, для массива с элементами типа boolean начальные ( default ) значения будут равны false , для массивов с числовыми значениями — 0, с элементами типа char — \u0000 . Для массива типа класса (объекты) — null (не пустые строки — “” а именно null ). То есть, в примере выше все значения массива arr будут равны 0 до тех пор, пока они не будут непосредственно заданы. В отличие от коллекций, массивы не являются динамическими. После объявления массива определенного размера сам размер нельзя изменить. Чтобы добавить новый элемент в массив, необходимо создать новый массив большего размера и скопировать в него все элементы со старого (это принцип работы ArrayList). Есть один момент, который знают не все и на котором вас могут неплохо подловить. В Java есть два вида переменных — простые типы и ссылки на полноценные объекты. К какому из них относятся массивы? Например, вот:

Вроде бы все просто — это 10 элементов int . Получается, можно сказать, что это простой тип? Как бы не так. В Java массивы являются объектами, динамически создаются и могут быть назначены переменным типа Object. Все методы класса Object можно вызвать в массиве. Поэтому мы можем даже написать:

 Object arr = new int[]; System.out.println(arr.toString()); 

Подробнее об особенностях массивов в Java рассказывается в этой статье o Java Array. Чтобы закрепить знания, можно решить несколько задач из этой подборки.

3. Расскажите об иерархии коллекций

Коллекции используются в ситуациях, когда нужна гибкость при работе с данными. Коллекции могут добавлять элемент, удалять элемент и выполнять множество других операций. В Java есть множество различных реализаций, а нам нужно всего лишь выбрать правильную коллекцию для текущей ситуации. Как правило, когда вы упоминаете интерфейс Collection , вас просят перечислить некоторые его реализации и отношение с Map . Что ж, давайте разбираться. Итак, Collection и Map — это две разные иерархии для структур данных. Как выглядит иерархия Collection :Интерфейс Collection является ключевым верховным звеном с перечнем базовых методов, от которого и берут начало три базовых вида структур данных — Set , List , Queue . Set — интерфейс, представляющий собой совокупность объектов, в которой каждый объект является уникальным. List — интерфейс, представляющий упорядоченную последовательность объектов, которая называется списком. Queue — интерфейс, отвечающий за структуры, которые организованы в виде очереди (последовательное хранение элементов). Как говорилось раньше, Map является отдельной иерархией: Map — интерфейс, представляющий словарь, в котором элементы содержатся в виде пар «ключ-значение». При этом все ключи (K) уникальные в пределах объекта Map . Данный вид коллекции облегчает поиск элемента, если нам известен ключ — уникальный идентификатор объекта.

4. Что вы знаете о Set?

Как говорилось ранее, данная коллекция представляет множество уникальных элементов. Иначе говоря, один и тот же объект не может встречаться в Java Set более одного раза. Также хотелось бы обозначить, что из Set мы не можем вытащить элемент по номеру (индексу) — только перебором. Важно то, что разные реализации Set имеют разный способ структуризации данных. Конкретные реализации мы и рассмотрим далее. Итак, основные реализации Set : HashSet — множество, которое основано на хеш-таблице, что в свою очередь помогает при поиске. Использует хеш-функцию, которая улучшает производительно при поиске и вставке. Независимо от количества элементов, в основном, вставка и поиск (иногда и удаление) выполняются за время, близкое к постоянному — O(1). Подробнее с хеш-функцией мы ознакомимся чуть позже. Также хотелось бы отметить, что HashSet содержит в себе HashMap , в котором и происходит вся магия. Вот подробная статья о HashSet в Java. LinkedHashSet — данный класс расширяет HashSet , при этом не добавляя никаких новых методов. Как и LinkedList , данный класс поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать необходимый порядок в данной реализации Set . Класс TreeSet создает множество, которое для организации структуры хранения элементов основано на красно-черном дереве. Другими словами, в данном множестве мы можем сортировать элементы в возрастающем порядке. Если мы используем некоторые стандартные объекты из “коробки”, например, Integer , то для выстраивания множества Integer в возрастающем порядке нам ничего и не нужно делать:

 TreeSet set = new TreeSet<>(); set.add(4); set.add(2); set.add(3); set.add(1); System.out.println(set);

То есть, в данном set числа хранятся в отсортированном виде. Если мы будем использовать элементы String в TreeSet , они будут отсортированы, но по алфавиту. Ну а что если у нас есть некоторый стандартный (пользовательский) класс? Каким образом объекты данного класса будет структуризировать TreeSet ? Если мы попробуем задать произвольный объект в данный Set :

 TreeSet set = new TreeSet<>(); set.add(new Cat(4, "Мурзик")); set.add(new Cat(2, "Барсик")); set.add(new Cat(3, "Гарфилд")); System.out.println(set); 

Мы получим ClassCastException , так как TreeSet не знает, как сортировать объекты данного типа. В таком случае нужно, чтобы наш кастомный объект реализовал интерфейс Comparable , и его метод compareTo :

 public class Cat implements Comparable  < int age; String name; public Cat(int age, String name) < this.age = age; this.name = name; >@Override public int compareTo(Cat cat) < return age >cat.age ? 1 : -1; > @Override public String toString() < return "Cat'; > > 

• 1, если текущий (this) объект считается большим;
• -1, если текущий объект считается меньшим, чем тот, который пришел аргументом;
• 0, если объекты равны (в данном случае мы это не используем).

Другой способ — создание отдельного класса, ответственного за сортировку, который реализует интерфейс comparator и его метод compare :

 public class CatComparator implements Comparator  < @Override public int compare(Cat o1, Cat o2) < return o1.age >o2.age ? 1 : -1; > > 

 TreeSet set = new TreeSet<>(new CatComparator()); 

После этого все объекты класса Cat , попавшие в TreeSet , будут отсортированы с помощью класса Cat Comparator . Больше о Comparator и Comparable в Java можно узнать из этой статьи.

5. Расскажите о Queue

• add и offer — вставляет элемент в конец очереди,
• remove — извлекает и удаляет заголовок этой очереди,
• peek — извлекает, но не удаляет заголовок очереди.

Источник