какие есть стандартные реализации интерфейса list и в каких ситуациях их нужно использовать

Готовимся к собеседованию: что нужно знать о коллекциях в Java

Освежаем знания о коллекциях в Java и закрепляем их на практике.

Коллекции в Java — одна из любимых тем на собеседованиях Java-разработчиков любого уровня. Без них не обходятся и экзамены на сертификат Java Professional.

Вспомним основные типы коллекций, их реализации в Java, проверим понимание на практике.

Что такое коллекции

Коллекции — это наборы однородных элементов. Например, страницы в книге, яблоки в корзине или люди в очереди.

Инструменты для работы с такими структурами в Java содержатся в Java Collections Framework. Фреймворк состоит из интерфейсов, их реализаций и утилитарных классов для работы со списками: сортировки, поиска, преобразования.

Фулстек-разработчик. Любимый стек: Java + Angular, но в хорошей компании готова писать хоть на языке Ада.

Галопом по Европам, или Кратко об интерфейсах

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

Например, мешочек с бочонками для игры в лото: каждый номер от 1 до 90 встречается в нём ровно один раз, и заранее неизвестно, в каком порядке бочонки вынут при игре.

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

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

Queue — очередь. В таком списке элементы можно добавлять только в хвост, а удалять — только из начала. Так реализуется концепция FIFO ( first in, first out) — «первым пришёл — первым ушёл». Вам обязательно напомнят это правило, если попробуете пролезть без очереди в магазине:

А ещё есть LIFO (last in, first out), то есть «последним пришёл — первым ушёл». Пример — стопка рекламных буклетов на ресепшене отеля: первыми забирают самые верхние (положенные последними). Структуру, которая реализует эту концепцию, называют стеком.

Deque может выступать и как очередь, и как стек. Это значит, что элементы можно добавлять как в её начало, так и в конец. То же относится к удалению.

Будет здорово, если на собеседовании вы назовёте Deque правильно: «дэк», а не «д экью», как часто говорят.

Map состоит из пар «ключ-значение». Ключи уникальны, а значения могут повторяться. Порядок элементов не гарантирован. Map позволяет искать объекты (значения) по ключу.

Пример: стопка карточек с иностранными словами и их значениями. Для каждого слова (ключ) на обороте карточки есть вариант перевода (значение), а вытаскивать карточки можно в любом порядке.

Не путайте интерфейс Collection и фреймворк Collections. Map не наследуется от интерфейса Collection, но входит в состав фреймворка Collections.

Соберём всё вместе

❌ для ключейСохраняется порядок добавления❌✅✅❌

Такие разные реализации

Реализаций интерфейсов так много, что при желании можно организовать вполне себе упорядоченный Map и даже отсортированное множество. Пройдёмся кратко по основным классам.

Реализации List

Класс ArrayList подойдёт в большинстве случаев, если вы уже определились, что вам нужен именно список (а не Map, например).

Строится на базе обычного массива. Если при создании не указать размерность, то под значения выделяется 10 ячеек. При попытке добавить элемент, для которого места уже нет, массив автоматически расширяется — программисту об этом специально заботиться не нужно.

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

При удалении элемента все остальные с бо́льшим индексом сдвигаются влево:

Класс LinkedList реализует одновременно List и Deque. Это список, в котором у каждого элемента есть ссылка на предыдущий и следующий элементы:

Благодаря этому добавление и удаление элементов выполняется быстро — времязатраты не зависят от размера списка, так как элементы при этих операциях не сдвигаются: просто перестраиваются ссылки.

На собеседованиях часто спрашивают, когда выгоднее использовать LinkedList, а когда — ArrayList.

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

В целом так и есть, но вы можете блеснуть эрудицией — рассказать, что под капотом. При добавлении элементов в ArrayList (или их удалении) вызывается нативный метод System.arraycopy. В нём используются ассемблерные инструкции для копирования блоков памяти. Так что даже для больших массивов эти операции выполняются за приемлемое время.

Реализации Queue

Про одну из них, LinkedList, мы рассказали выше.

Класс ArrayDeque — это реализация двунаправленной очереди в виде массива с переменным числом элементов.

Новые значения можно добавлять в начало или конец списка, и удалять оттуда же. Причём эти операции выполняются быстрее, чем при использовании LinkedList.

Класс PriorityQueue — упорядоченная очередь. По умолчанию элементы добавляются в естественном порядке: числа по возрастанию, строки по алфавиту и так далее, либо алгоритм сравнения задаёт разработчик.

Этот класс может быть полезен, например, для нахождения n минимальных чисел в большом неупорядоченном списке:

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

Реализации Set

Класс HashSet использует для хранения данных в хеш-таблице. Это значит, что при манипуляциях с элементами используется хеш-функция — hashCode() в Java.

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

Например, администратор в гостинице может класть ключ в коробку с номером от 1 до 9, вычисляя его по такому алгоритму: складывать все цифры номера, пока не получится одноразрядное число.

Здесь алгоритм вычисления — хеш-функция, а результат вычисления — хеш-код.

Тогда ключ от номера 356 попадёт в коробку 5 (3 + 5 + 6 = 14; 1 + 4 = 5), а ключ от номера 123 — в коробку с номером 6.

Добавление, поиск и удаление элементов при такой организации происходит за постоянное время, независимо от числа элементов в коллекции.

О классе TreeSet вспоминают в тех случаях, когда множество должно быть упорядочено. Каким образом упорядочивать — определяет разработчик при создании нового TreeSet. По умолчанию элементы располагаются в естественном порядке. Организованы они в виде красно-чёрного дерева.

Реализации Map

Класс HashMap хранит данные в виде хеш-таблицы, как и HashSet. Более того, HashSet внутри использует HashMap. При этом ключом выступает сам элемент.

Класс TreeMap строится тоже на базе красно-чёрного дерева. Элементы здесь упорядочены (в естественном или заданном при создании порядке) в каждый момент времени. При этом вставка и удаление более затратны, чем в случае с HashMap.

Класс LinkedHashMap расширяет возможности HashMap тем, что позволяет итерироваться по элементам в порядке их добавления. Как и в LinkedList, здесь каждая пара-значение содержит ссылку на предыдущий и последующий элементы.

Ещё один хитрый вопрос на собеседовании: в каких коллекциях допускаются null-элементы?

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

Обоснование: мух советуют отделять от котлет — иными словами, нельзя сравнивать принципиально разные, несопоставимые вещи. Так же и в Java невозможно понять, что больше: null или число 1, или null или строка «hello».

Поэтому null-значения запрещены в TreeMap и TreeSet.

Ещё они недопустимы в ArrayDeque, так как методы этого класса (например, poll() — удаление элемента из начала очереди) используют null как признак пустоты коллекции.

Попрактикуемся

Чтобы убедиться, что вы не просто вызубрили теорию, а хорошо понимаете предмет, на собеседовании вам могут предложить задания вроде «что произойдёт при выполнении кода»

Разберём типовые задачи на понимание коллекций.

Задачи для ArrayList

Что будет напечатано после выполнения кода ниже:

Правильный ответ: test2:test4:test1:test4:test2:test3:

Элементы в ArrayList нумеруются начиная с нуля. Поэтому элемент с номером 1 — это test2.

Следующим действием мы добавляем строку «test4» в ячейку с индексом 1. При этом элементы с бо́льшим индексом сдвигаются вправо.

Вторая часть вывода ( test4) показывает, что теперь по индексу 1 извлекается именно test4.

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

Что будет выведено при выполнении кода:

Правильный ответ: 2:2

Первая часть понятна: добавили два элемента, поэтому размер списка равен двум. Остаётся вопрос: почему не был удалён «test1»?

Перед удалением элемента его нужно найти в списке. ArrayList и остальные коллекции, которые не используют алгоритмы хеширования, применяют для поиска метод equals().

Строки сравниваются по значению, поэтому «test3» не эквивалентно «test1» и «test2». А раз ни один элемент не соответствует критерию поиска, ничего не удалится — размер списка останется прежним.

Проверьте себя: подумайте, что произойдёт, если вместо

Задачи для Set

Что выведет фрагмент кода ниже:

Правильный ответ: 3:, а дальше точно не известно.

Так как строки сравниваются по значению, а дубликаты во множествах недопустимы, второй «Иван» не станет частью множества. В итоге размер множества будет равен 3.

В каком порядке будут выведены элементы множества — определённо мы сказать не можем: во множествах порядок добавления не сохраняется.

Что выведет фрагмент кода:

Правильный ответ: 4.

Как же так, ведь во множество должны попадать уникальные элементы?

Прежде чем добавить новый элемент в множество, вычисляется его hashCode() — чтобы определить бакет, куда он может быть помещён.

Если бакет пуст, элемент будет добавлен. Иначе уже добавленные элементы с таким же значением хеша сравниваются с кандидатом при помощи метода equals(). Если дубликат не найден, новый элемент становится частью множества. Он попадёт в тот же бакет.

Мы добавляем в Set объекты типа Person — созданного нами класса. Этот класс, как и все ссылочные типы, наследуется от класса Object.

Так как мы не переопределили метод hashCode(), будет использована родительская реализация. В ней хеш вычисляется на основе данных адреса (реализация зависит от JVM).

Метод equals() тоже не переопределён. В классе-родителе этот метод просто сравнивает ссылки на объекты. Это значит, что даже если хеш случайно совпадёт для каких-то из четырёх элементов, equals() в любом случае вернёт false.

Таким образом, каждый из четырёх кандидатов попадёт в множество.

Проверьте себя: изменится ли что-нибудь, если переопределить hashCode() вот так:

А если ещё и equals() переопределить, как на фрагменте ниже:

Источник

Справочник по Java Collections Framework

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

Что такое Java Collections Framework?

Java Collection Framework — иерархия интерфейсов и их реализаций, которая является частью JDK и позволяет разработчику пользоваться большим количесвом структур данных из «коробки».

Базовые понятия

Интерфейс Map [doc]

Hashtable — реализация такой структуры данных, как хэш-таблица. Она не позволяет использовать null в качестве значения или ключа. Эта коллекция была реализована раньше, чем Java Collection Framework, но в последствии была включена в его состав. Как и другие коллекции из Java 1.0, Hashtable является синхронизированной (почти все методы помечены как synchronized ). Из-за этой особенности у неё имеются существенные проблемы с производительностью и, начиная с Java 1.2, в большинстве случаев рекомендуется использовать другие реализации интерфейса Map ввиду отсутствия у них синхронизации.

WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references. Другими словами, Garbage Collector автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элеметна нет жёстких ссылок.

Интерфейс List [doc]

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

ArrayList — как и Vector является реализацией динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Как можно догадаться из названия, его реализация основана на обычном массиве. Данную реализацию следует применять, если в процессе работы с коллекцией предплагается частое обращение к элементам по индексу. Из-за особенностей реализации поиндексное обращение к элементам выполняется за константное время O(1). Но данную коллекцию рекомендуется избегать, если требуется частое удаление/добавление элементов в середину коллекции. Подробный анализ и описание можно почитать в этом хабратопике.

Интерфейс Set [doc]

Представляет собой неупорядоченную коллекцию, которая не может содержать дублирующиеся данные. Является программной моделью математического понятия «множество».

Интерфейс Queue [doc]

Этот интерфейс описывает коллекции с предопределённым способом вставки и извлечения элементов, а именно — очереди FIFO (first-in-first-out). Помимо методов, определённых в интерфейсе Collection, определяет дополнительные методы для извлечения и добавления элементов в очередь. Большинство реализаций данного интерфейса находится в пакете java.util.concurrent и подробно рассматриваются в данном обзоре.

Заключение

Java Collections Framework содержит большое количество различных структур данных, доступных в JDK «из коробки», которые в большинстве случаев покрывают все потребности при реализации логики приложения. Сравнение временных характеристик основных коллекций, которые зачастую используются в разработке приложений приведено в таблице:

При необходимости, разработчик может создать собственную реализацию, расширив или переопределив существующую логику, либо создав свою собственную реализацию подходящего интерфейса с нуля. Также существует некоторое количество готовых решений, которые являются альтернативой или дополнением к Java Collections Framework. Наиболее популярными являются Google Guava и Commons Collections.

Источник

Списки на Java — методы интерфейса List

Интерфейс Java List, java.util.List, представляет упорядоченную последовательность объектов. Элементы, содержащиеся в списке Java, вставлять и удалять в соответствии с порядком их появления в списке.

Каждый элемент в списке Java имеет индекс. Первый элемент в имеет индекс 0, второй элемент имеет индекс 1 и т.д.

Вы можете добавить любой объект в список. Если список не типизирован с использованием Java Generics, то вы можете даже смешивать объекты разных типов (классов) в одном и том же списке.

Java List — это стандартный интерфейс, который является подтипом Java Collection, что означает, что означает, что List наследуется от Collection.

Учебное видео по спискам Java

Если вы предпочитаете смотреть видео вместо чтения текста, вот видео версия этого учебника по Java List:

Java List и Set

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

Первое различие между Java List и Java Set состоит в том, что один и тот же элемент может встречаться в списке более одного раза. Это отличается от набора, где каждый элемент может встречаться только один раз.

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

Реализация List

Будучи подтипом Collection, все методы в интерфейсе Collection также доступны в Listinterface.

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

Также есть параллельные реализации List в пакете java.util.concurrent.

Вот несколько примеров того, как создать экземпляр List:

Как вставить элементы в список Java

Вставить элементы (объекты) в список Java можно методом add (). Вот пример добавления элементов в список Java:

Первые три вызова add () добавляют экземпляр String в конец списка.

Вставить нулевые значения

На самом деле возможно вставить даже нулевые значения в список.

Добавить элементы по определенному индексу

Можно добавить элемент в список по определенному индексу. Интерфейс List имеет версию метода add(), которая принимает индекс в качестве первого параметра, и элемент для вставки в качестве второго параметра. Вот пример вставки элемента с индексом 0.

Если список уже содержит элементы, то теперь они будут перемещаться дальше во внутренней последовательности. Элемент, который имел индекс 0 до того, как новый элемент был вставлен в индекс 0, будет перемещен в индекс 1 и т.д.

Вставляем все элементы из одного списка в другой

Можно добавить все элементы из одного списка в другой. Сделаем это с помощью метода ListaddAll (). Результат представляет собой объединение двух списков.

Этот пример добавляет все элементы из listSource в listDest.

Метод addAll () принимает набор в качестве параметра, поэтому в качестве параметра можно передать список или набор.

Получить элементы из списка Java

Вы можете получить элементы из списка Java, используя индекс элементов. Методом get (int index). Вот пример доступа к элементам списка с использованием индексов элементов:

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

Как найти элементы в списке Java

Вы можете найти элементы в списке Java, используя один из этих двух методов:

Запуск этого кода приведет к следующему результату:

Найти последнее вхождение элемента в списке

Метод lastIndexOf () находит индекс последнего вхождения в списке данного элемента.

Результат, напечатанный при запуске приведенного выше примера будет таков:

Элемент 1 встречается 2 раза. Индекс последнего равен 2.

Проверка: содержит ли список элемент?

Вы можете проверить, содержит ли Java List данный элемент, используя метод List contains ().

Чтобы определить, содержит ли List этот элемент, List будет внутренне выполнять итерации своих элементов и сравнивать каждый элемент с объектом, переданным в качестве параметра.

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

Очевидно, что если входной параметр для contains () имеет значение null, метод contains () не будет использовать метод equals() для сравнения с каждым элементом, а вместо этого использует оператор ==.

Как удалить элементы из списка Java

Вы можете удалить элементы из списка Java с помощью этих двух методов:

remove (Object element) удаляет элемент в списке, если он присутствует. Все последующие элементы, затем перемещаются вверх по списку. Таким образом, их индекс уменьшается на 1.

Этот пример сначала добавляет элемент, а затем снова удаляет его.

Метод List remove (int index) удаляет элемент по указанному индексу.

После выполнения этого примера кода список будет содержать элементы 1 и 2 с индексами 0 и 1.

Очистить список

Интерфейс Java List содержит метод clear (), который удаляет все элементы из списка при вызове. Удаление всех элементов также называется очисткой.

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

Метод retainAll () способен сохранять все элементы из одного списка в другом. Другими словами, метод retain () удаляет все элементы, которые не найдены в другом списке.

Результатом является пересечение двух списков.

Узнать количество элементов

Вы можете получить количество элементов вызвав метод size (). Вот пример:

Подсписок списка

Метод subList () может создавать новый List с подмножеством элементов из исходного List.

Метод subList () принимает 2 параметра: начальный индекс и конечный индекс. Начальный индекс — это индекс первого элемента из исходного списка для включения в подсписок.

Конечный индекс является последним индексом подсписка, но элемент в последнем индексе не включается в подсписок. Это похоже на то, как работает метод подстроки Java String.

После выполнения list.subList (1,3) подсписок будет содержать элементы с индексами 1 и 2.

Помните, что исходный список содержит 4 элемента с индексами от 0 до 3. Вызов list.subList (1,3) будет включить индекс 1, но исключить индекс 3, сохраняя тем самым элементы с индексами 1 и 2.

Преобразовать list в set

Вы можете преобразовать список Java в набор(set), создав новый набор и добавив в него все элементы из списка. Набор удалит все дубликаты.

Таким образом, результирующий набор будет содержать все элементы списка, но только один раз.

Общие списки

По умолчанию вы можете поместить любой объект в список, но Java позволяет ограничить типы объектов, которые вы можете вставить в список.

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

Сортировка

Вы можете отсортировать список с помощью метода Collections sort ().

Если Список содержит объекты, которые реализуют интерфейс Comparable (java.lang.Comparable), тогда эти объекты можно сравнивать. В этом случае вы можете отсортировать список следующим образом:

Класс Java String реализует интерфейс Comparable, вы можете отсортировать их в естественном порядке, используя метод Collections sort ().

Сортировка списка с помощью Comparatorimplementation

Если объекты не реализуют интерфейс Comparable или если вы хотите отсортировать объекты в порядке, отличном от их реализации compare (), вам необходимо использовать Comparatorimplementation (java.util.Comparator).

Вот код сортировки:

Обратите внимание на реализацию Comparator в приведенном выше примере. Эта реализация сравнивает только поле марки автомобилей Car. Можно создать другую реализацию Comparator, которая сравнивает номерные знаки или даже количество дверей в автомобилях.

Возможно реализовать Comparator с использованием Java Lambda. Вот пример, который сортирует объекты List of Car с использованием трех различных реализаций интерфейса Comparator, каждая из которых сравнивает экземпляры Car по своему полю:

Итерации

Вы можете выполнить итерацию списка несколькими различными способами. Три наиболее распространенных способа:

Итерация списка с помощью итератора

Первый способ итерации списка — использовать итератор Java.

Вызывая метод iterator () интерфейса List.

Вызов hasNext () выполняется внутри цикла while.

Внутри цикла while вы вызываете метод Iterator next () для получения следующего элемента, на который указывает Iterator.

Если список задан с использованием Java Generics, вы можете сохранить некоторые объекты внутри цикла while.

Итерация списка с использованием цикла For-Each

Второй способ итерации List — использовать цикл for.

Цикл for выполняется один раз для каждого элемента. Внутри цикла for каждый элемент, в свою очередь, связан с переменной obj.

Можно изменить тип переменной внутри цикла for.

Итерация списка с помощью цикла For

Третий способ итерации List — использовать стандартный цикл for, подобный следующему:

Цикл for создает переменную int и инициализирует ее 0. Затем она зацикливается, пока переменная int i меньше размера списка. Для каждой итерации переменная i увеличивается.

Внутри цикла for обращаемся к элементам List с помощью метода get (), передавая в качестве параметра переменную i.

Опять же, если список напечатан с использованием Java Generics, например, для для строки, то вы можете использовать универсальный тип списка в качестве типа для локальной переменной, которая присваивается каждому элементу списка во время итерации.

Тип локальной переменной внутри цикла for теперь String. Поскольку список обычно типизируется как String, он может содержать только объекты String.

Следовательно, компилятор знает, что только метод String может быть возвращен из метода get (). Поэтому вам не нужно приводить элемент, возвращенный get (), в String.

Перебор списка с использованием API Java Stream

Четвертый способ итерации через API Java Stream. Для итерации вы должны сначала получить поток из списка. Получение потока из списка в Java выполняется путем вызова метода Liststream ().

Как только вы получили поток из списка, вы можете выполнить итерацию потока, вызвав его метод forEach ().

Вызов метода forEach () заставит Stream выполнить внутреннюю итерацию всех элементов потока.

Средняя оценка / 5. Количество голосов:

Или поделись статьей

Видим, что вы не нашли ответ на свой вопрос.

Источник