Collection framework java что это

Обновлено: 12.05.2024

Collections

25. Что имеется в виду под Collections в Java?

поиск;
сортировка;
манипуляция;
добавление;
удаление.

26. Какие классы и интерфейсы доступны в Collection фреймворке?

Collection;
List;
Set;
Map;
Sorted Set;
Sorted Map;
Queue.

Lists:
1. ArrayList;
2. LinkedList;
3. Vector(deprecated).
Sets:
1. HashSet;
2. LinkedHashSet;
3. TreeSet.
Maps:
1. HashMap
2. TreeMap
3. HashTable (deprecated)
4. LinkedHashMap
Queue
1. Priority Queue.

27. Что подразумевается под sorted и ordered в коллекциях?

Ordered (упорядочивание):

Это означает, что элементы, которые хранятся в коллекции, основаны на значениях, добавленных в коллекцию. Таким образом, мы можем перебирать значения из коллекции в определенном порядке. Другими словами это значит, что у элементов коллекции есть свой специфический порядок, согласно которому они расположены. Для лучшего понимания, коллекция, которая не упорядочена (ordered), хранит элементы в произвольном порядке. Например, Set.

Sorted (отсортированный):

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

28. Какие есть коллекции с List интерфейсом? Как происходит работа с List?

Значения элементов в лист базируются на их индексе — они упорядочены по индексу. Повторения элементов разрешены (то есть можно добавить один и тот же объект в коллекцию несколько раз, и это будет нормально).

ArrayList:

быстрый перебор и быстрый поиск по индексу;
коллекция упорядочена по индексу, но не сортирована;
реализует RandomAccess интерфейс;
медленное добавление в середину списка.

Linked List:

элементы связаны друг с другом, то есть реализован двусвязный список;
общая скорость работы заметно ниже, чем в ArrayList;
отличный выбор для большого количества вставок и удалений в середину массива;
реализует интерфейсы списков Queue и Deque, поэтому и имеет их методы для работы.

29. Расскажите о коллекции Map и ее реализациях?

Map — это коллекция ключ-значение (key-value). Есть уникальный ключ и значение, которое соответствует этому значению. Используется equals() и hashcode() методы для определения уникальности ключа.

HashMap:

не отсортирован и не упорядочен;
используют если не важны порядок и сортировка;
поддерживает null ключ.

LinkedHashMap:

поддерживает порядок вставки;
медленнее, чем HashMap;
ожидается, что итерация быстрее, чем в HashMap.

TreeMap:

30. Расскажите о коллекции Set и ее реализациях?

Set — это множество уникальных элементов, и это ее главная особенность. То есть Set не допускает повторения одних и тех же элементов. Здесь важно, чтобы у объектов, которые добавляются, был реализован метод equals .

HashSet:

не отсортирован и не упорядочен. Под капотом там HashMap с заглушкой для значения. Посмотрите сами ;)
использует hashCode для добавления объектов;
стоит использовать, когда нужно иметь уникальные объекты и их порядок не важен.

LinkedHashSet:

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

TreeSet:

одна из двух сортированных коллекций;
использует структуру красно-черного дерева и гарантирует, что элементы будут в возрастающем порядке;
под капотом это TreeMap с заглушкой на значениях. А элементами TreeSet являются ключи к TreeMap (также посмотрите ;)).

Заключение

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

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

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

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

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

На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: Collection и Map . Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» (словари).

Collection — этот интерфейс находится в составе JDK c версии 1.2 и определяет основные методы работы с простыми наборами элементов, которые будут общими для всех его реализаций (например size() , isEmpty() , add(E e) и др.). Интерфейс был слегка доработан с приходом дженериков в Java 1.5. Также, в версии Java 8, было добавлено несколько новых методов для работы с лямбдами (такие как stream() , parallelStream() , removeIf(Predicate<? super E> filter) и др.).

Важно также отметить, что эти методы были реализованы непосредственно в интерфейсе как default -методы.

Map. Данный интерфейс также находится в составе JDK c версии 1.2 и предоставляет разработчику базовые методы для работы с данными вида «ключ — значение».Также как и Collection , он был дополнен дженериками в версии Java 1.5 и в версии Java 8 появились дополнительные методы для работы с лямбдами, а также методы, которые зачастую реализовались в логике приложения ( getOrDefault(Object key, V defaultValue) , putIfAbsent(K key, V value) ).

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

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

HashMap — коллекция является альтернативой Hashtable . Двумя основными отличиями от Hashtable являются то, что HashMap не синхронизирована и HashMap позволяет использовать null как в качестве ключа, так и значения. Так же как и Hashtable , данная коллекция не является упорядоченной: порядок хранения элементов зависит от хэш-функции. Добавление элемента выполняется за константное время O(1), но время удаления, получения зависит от распределения хэш-функции. В идеале является константным, но может быть и линейным O(n). Более подробную информацию о HashMap можно почитать здесь (актуально для Java < 8).

LinkedHashMap — это упорядоченная реализация хэш-таблицы. Здесь, в отличии от HashMap , порядок итерирования равен порядку добавления элементов. Данная особенность достигается благодаря двунаправленным связям между элементами (аналогично LinkedList ). Но это преимущество имеет также и недостаток — увеличение памяти, которое занимет коллекция. Более подробная информация изложена в этой статье.

TreeMap — реализация Map основанная на красно-чёрных деревьях. Как и LinkedHashMap является упорядоченной. По-умолчанию, коллекция сортируется по ключам с использованием принципа "natural ordering", но это поведение может быть настроено под конкретную задачу при помощи объекта Comparator , который указывается в качестве параметра при создании объекта TreeMap .

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

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

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

Vector — реализация динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Vector появился в JDK версии Java 1.0, но как и Hashtable , эту коллекцию не рекомендуется использовать, если не требуется достижения потокобезопасности. Потому как в Vector , в отличии от других реализаций List , все операции с данными являются синхронизированными. В качестве альтернативы часто применяется аналог — ArrayList .

Stack — данная коллекция является расширением коллекции Vector . Была добавлена в Java 1.0 как реализация стека LIFO (last-in-first-out). Является частично синхронизированной коллекцией (кроме метода добавления push() ). После добавления в Java 1.6 интерфейса Deque , рекомендуется использовать именно реализации этого интерфейса, например ArrayDeque .

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

LinkedList — ещё одна реализация List . Позволяет хранить любые данные, включая null . Особенностью реализации данной коллекции является то, что в её основе лежит двунаправленный связный список (каждый элемент имеет ссылку на предыдущий и следующий). Благодаря этому, добавление и удаление из середины, доступ по индексу, значению происходит за линейное время O(n), а из начала и конца за константное O(1). Так же, ввиду реализации, данную коллекцию можно использовать как стек или очередь. Для этого в ней реализованы соответствующие методы. На Хабре также есть статья с подробным анализом и описанием этой коллекции.

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

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

HashSet — реализация интерфейса Set , базирующаяся на HashMap . Внутри использует объект HashMap для хранения данных. В качестве ключа используется добавляемый элемент, а в качестве значения — объект-пустышка (new Object()). Из-за особенностей реализации порядок элементов не гарантируется при добавлении.

LinkedHashSet — отличается от HashSet только тем, что в основе лежит LinkedHashMap вместо HashMap . Благодаря этому отличию порядок элементов при обходе коллекции является идентичным порядку добавления элементов.

TreeSet — аналогично другим классам-реализациям интерфейса Set содержит в себе объект NavigableMap , что и обуславливает его поведение. Предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator , либо сохраняет элементы с использованием "natural ordering".

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

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

PriorityQueue — является единственной прямой реализацией интерфейса Queue (была добавлена, как и интерфейс Queue, в Java 1.5), не считая класса LinkedList , который так же реализует этот интерфейс, но был реализован намного раньше. Особенностью данной очереди является возможность управления порядком элементов. По-умолчанию, элементы сортируются с использованием «natural ordering», но это поведение может быть переопределено при помощи объекта Comparator , который задаётся при создании очереди. Данная коллекция не поддерживает null в качестве элементов.

ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out). Интерфейс Deque и реализация ArrayDeque были добавлены в Java 1.6. Эта коллекция представляет собой реализацию с использованием массивов, подобно ArrayList , но не позволяет обращаться к элементам по индексу и хранение null . Как заявлено в документации, коллекция работает быстрее чем Stack , если используется как LIFO коллекция, а также быстрее чем LinkedList, если используется как FIFO.

Заключение

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

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

Collections

25. Что имеется в виду под Collections в Java?

поиск;
сортировка;
манипуляция;
добавление;
удаление.

26. Какие классы и интерфейсы доступны в Collection фреймворке?

Collection;
List;
Set;
Map;
Sorted Set;
Sorted Map;
Queue.

Lists:
1. ArrayList;
2. LinkedList;
3. Vector(deprecated).
Sets:
1. HashSet;
2. LinkedHashSet;
3. TreeSet.
Maps:
1. HashMap
2. TreeMap
3. HashTable (deprecated)
4. LinkedHashMap
Queue
1. Priority Queue.

27. Что подразумевается под sorted и ordered в коллекциях?

Ordered (упорядочивание):

Sorted (отсортированный):

28. Какие есть коллекции с List интерфейсом? Как происходит работа с List?

ArrayList:

быстрый перебор и быстрый поиск по индексу;
коллекция упорядочена по индексу, но не сортирована;
реализует RandomAccess интерфейс;
медленное добавление в середину списка.

Linked List:

элементы связаны друг с другом, то есть реализован двусвязный список;
общая скорость работы заметно ниже, чем в ArrayList;
отличный выбор для большого количества вставок и удалений в середину массива;
реализует интерфейсы списков Queue и Deque, поэтому и имеет их методы для работы.

29. Расскажите о коллекции Map и ее реализациях?

HashMap:

не отсортирован и не упорядочен;
используют если не важны порядок и сортировка;
поддерживает null ключ.

LinkedHashMap:

поддерживает порядок вставки;
медленнее, чем HashMap;
ожидается, что итерация быстрее, чем в HashMap.

TreeMap:

30. Расскажите о коллекции Set и ее реализациях?

HashSet:

не отсортирован и не упорядочен. Под капотом там HashMap с заглушкой для значения. Посмотрите сами ;)
использует hashCode для добавления объектов;
стоит использовать, когда нужно иметь уникальные объекты и их порядок не важен.

LinkedHashSet:

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

TreeSet:

одна из двух сортированных коллекций;
использует структуру красно-черного дерева и гарантирует, что элементы будут в возрастающем порядке;
под капотом это TreeMap с заглушкой на значениях. А элементами TreeSet являются ключи к TreeMap (также посмотрите ;)).

Карты (Map)

Закончить можно занимательным фактом, что коллекция Set внутри себя использует Map , где добавляемые значения — это ключи, а значение везде одинаковое. Занимательно это потому, что Map не является коллекцией и возвращает Set , который является коллекцией, но по факту реализован как Map . Немного сюр, но вот так вот вышло )

Очередь (Queue)

Очередь (Queue) — это структура, знакомая нам из жизни. Очереди в магазины, к врачам. Кто первее пришёл (First In), тот первее и выйдет из очереди (First Out). В Java очередь представлена интерфейсом java.util.Queue. Согласно Javadoc очереди, очередь добавляет следующие методы:

Как видите, есть методы-приказы (их невыполнение чревато исключением) и есть методы-просьбы (невозможность их выполнить не приводит к ошибкам). Кроме того, можно получить элемент без удаления (peek или элемент). У интерфейса очереди есть так же полезный наследник — Deque. Это так называемая "двусторонняя очередь". То есть такая очередь позволяет использовать эту структуру как с начала, так и с конца. В документации сказано, что "Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.", то есть вместо Stack рекомендуется использовать реализации Deque. В Javadoc показано, какие методы описывает интерфейс Deque:

Супер статья на хабре: "Структуры данных. Неформальный гайд"
Понятное объяснение про "кучу": "Фоксфорд: Информатика. Структуры данных: Куча (heap)"
Статья с хабра про Binary Heap: "Структуры данных: двоичная куча (binary heap)"
"Introduction to Binary Heaps (MaxHeaps)"

Давайте посмотрим на какие-нибудь примеры блокирующих очередей. А они ведь интересные. Например, BlockingQueue реализуют: PriorityBlockingQueue, SynchronousQueue, ArrayBlockingQueue, DelayQueue, LinkedBlockingQueue. А вот BlockingDeque реализуют из стандартного Collection Frameworks всего LinkedBlockingDeque . Каждая очередь — тема отдельного обзора. А в рамках данного обзора изобразим иерархию классов не только с List , но и с Queue :

Как мы видим из схемы, интерфейсы и классы Java Collections Framework сильно переплетены. Давайте добавим ещё одну ветвь иерархии — Set .

Set — переводится как "набор". От очереди и списка Set отличается большей абстракцией над хранением элементов. Set — как мешок с предметами, где неизвестно, как лежат предметы и в каком порядке они легли. В Java такой набор представлен интерфейсом java.util.Set. Как сказано в документации, Set — это "collection that contains no duplicate elements". Интересно, что сам интерфейс Set не добавляет новых методов к интерфейсу Collection , а лишь уточняет требования (про то, что не должно содержать дубликатов). Кроме того, из прошлого описания следует, что просто так из Set нельзя получить элемент. Для получения элементов используется Iterator. Set имеет ещё несколько связанных с собой интерфейсов. Первый это SortedSet . Как и следует из названия, SortedSet указывает на то, что такой набор отсортирован, а следовательно элементы реализуют интерфейс Comparable или указан Comparator . Кроме того, SortedSet предлагает несколько интересных методов:

Кроме того, есть методы first (самый маленький по значению элемент) и last (самый большой по значению элемент). У SortedSet есть наследник — NavigableSet . Цель этого интерфейса — описать методы навигации, которые нужны для более точного определения подходящих элементов. Из интересного — NavigableSet добавляет к привычному iterator (который идёт от меньшего к большему) итератор для обратного порядка — descendingIterator . Кроме того, NavigableSet позволяет при помощи метода descendingSet получить вид на себя (View), в котором элементы идут в обратном порядке. Это называется View , потому что через полученный элемент можно изменять элементы изначального Set . То есть по сути это представление изначальных данных другим способом, а не их копия. Интересно, что NavigableSet , подобно Queue , умеет pollFirst (минимальный) и pollLast (максимальный) элементы. То есть получает этот элемент и убирает из набора. Какие же есть реализации? Во-первых, самая известная реализация — на основе хэш-кода — HashSet. Другая не менее известная реализация — на основе красно-чёрного дерева — TreeSet. Давайте дорисуем нашу схему:

В рамках коллекций осталось разобрать иерархию — отшельников. Которая на первый взгляд стоит в стороне — java.util.Map .

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

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

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

Важно также отметить, что эти методы были реализованы непосредственно в интерфейсе как default -методы.

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

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

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

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

Заключение

Exceptions

31. Что такое Exception?

32. Как JVM обрабатывает исключения?

Как это работает? Как только где-то создается исключение, runtime создает Exception Object (обозначим как ExcObj). В нем хранится вся необходимая для работы информация — само исключение, которое вызывалось и место, где это произошло. Создание ExcObj и передача в runtime есть ничто иное как “выбрасывание исключения”. ExcObj содержит методы, по которым можно дойти до место создания исключения. Это множество методов называется Call Stack. Далее, runtime система ищет метод в Call Stack, который сможет обработать наше исключение. Если он таки находит соответствующий обработчик, то есть тип исключения совпадает с типом в обработчике, все хорошо. Если не находит, то runtime передает всё в default exception handler, который подготавливает ответ и завершает работу. Как это выглядит наглядно: В нашем случае CallStack схематично будет иметь вид: Есть две опции: случайным образом будет выброшено одно или другое исключение. Для IOException все ок, если будет сгенерировано оно, то результатом работы будет: "Caught IOException" . А вот если будет второе исключение, обработчика на которого нет, программа будет остановлена с таким выводом:

33. Как программистам обрабатывать исключения?

try
catch
throw
throws
finally

try-catch-finally — это конструкция, при помощи которой можно правильным образом перехватить и обработать исключение.
try — может быть только один раз, в нем и происходит логика;
catch — блок, который принимает какой-то тип исключения, их может быть множество. Например, в блоке try будет генерироваться несколько исключений, которые никак друг с другом не связаны;
finally — “наконец-то” и этот блок. Это блок, который выполнится в любом случае, независимо от того, что делается в try, catch.

34. throw и throws в Java

throw

throw используют в случае, когда нужно явно создать новое исключение. Применяют его для создания и выбрасывания пользовательских исключений. Например, исключения, связанные с валидацией. Обычно для валидации наследуются от RuntimeException . Пример: Важно, что использовать эту конструкцию можно только тем, что наследуется от Throwable . То есть, нельзя сказать так: Далее, работа потока обрывается и начинается поиск обработчика, который смог бы обработать его. Когда не находит, идет к методу, который вызвал его, и так поиск будет идти наверх по строке вызовов пока либо не найдет соответствующий обработчик, либо оставит работу приложения. Смотрим: Если запустить программу, получим такой результат:

throws

Написать try-catch с соответствующим и выше по наследованию исключением.
Использовать throws точно так же, чтобы эта проблема была уже у кого-то другого :D

35. Checked и Unchecked исключения в Java

B Java есть два типа исключений — checked и unchecked.

Checked исключения:

Это исключения, которые проверяются во время компиляции. Если какой-то код в методе во время исключения выдает checked исключение, метод обязан либо обработать его при помощи try-catch , либо пробросить его дальше На примере, который считывает картинку из пути "/users/romankh3/image.jpg", обновляет ее каким-то образом(для нас это не важно) и сохраняет ее обратно. Такой код компилироваться не будет, так как статические методы ImageIO.read() и ImageIO.write() выбрасывают исключение IOException, которое является checked (проверяемым) и должно соответственно быть обработанным. Здесь две опции, которые мы уже обсудили выше: или использовать try-catch , или пробросить дальше. Для лучшего усвоения сделаем и так, и эдак. То есть в методе updateAndSave просто пробросим, а уже в главном методе воспользуемся try-catch :

Unchecked исключения:

36. Что такое try-with-resources?

Это механизм, при помощи которого нужно правильно закрывать все ресурсы. Как-то не понятно, да?) Для начала, что такое ресурс. Ресурс — это объект, после работы с которым нужно закрыть его, то есть вызвать метод close() . Ресурсом называются все объекты, которые реализуют интерфейс AutoClosable , который, в свою очередь реализует интерфейс Closeable . Для нас важно понять, что все InputStream , OutpuStream являются ресурсами и их нужно правильно и успешно высвобождать. Вот как раз для этого и нужно нам использовать try-with-resource конструкцию. Вот как она выглядит: Вот этом примере ресурс — это ZipInputStream , после работы с которым нужно будет закрыть его. И чтоб не думать о том, что нужно вызвать метод close() , мы просто определяем эту переменную в блоке try, как показано в примере и в рамках этого блока выполняем все необходимое. Что делает пример? Он разархивирует zip архив. Для этого нужно воспользоваться InputStream ’ом. Определять можно больше одной переменной, разделяют их точкой с запятой. А в чем проблема? Но ведь можно использовать finally блок, — возможно, скажете вы. Вот статья, в которой подробно описываются проблемы с этим подходом. Также в ней описывается весь перечень неудач, которые могут постигнуть того, кто пренебрежет использованием этой конструкции. Рекомендую к прочтению ;) В завершающей части — вопросы/ответы по теме Multithreading. Мой профиль на GitHub

Коротко о главном — Java Collections Framework

Начать стоить с самого начала. Почему коллекции (Collection)? Сам термин берёт своё начало из таких вещей, как "Теория типов" и "Абстрактные типы данных". Но если не смотреть на какие-то высокие материи, то когда у нас несколько вещей, то мы можем назвать их "коллекция вещей". Те, кто собирают предметы. Вообще само слово коллекционировать происходит от лат. collectio «собирание, сбор». То есть коллекция — это сбор чего-то, контейнер для каких-то элементов. Итак, у нас есть коллекция элементов. Что мы можем захотеть с ней делать:

Как видно, мы можем захотеть довольно логичные вещи. А ещё мы понимаем, что мы можем захотеть что-то делать с несколькими коллекциями:

Соответственно, для описание такого общего поведения для всех коллекций написали разработчики Java интерфейс java.util.Collection. Интерфейс Collection — это то место, откуда берут начало все коллекции. Collection — это идея, это представление о том, как должны себя вести все коллекции. Поэтому, термин "Коллекция" выражена в виде интерфейса. Естественно, интерфейсу нужны реализации. Интерфейс java.util.Collection имеет абстрактный класс AbstractCollection , то есть некоторая "абстрактная коллекция", которая представляет собой скелет для остальных реализаций (о чём написано в JavaDoc над классом java.util.AbstractCollection ). Говоря о коллекциях вернёмся ещё раз вспомним, что мы хотим итерироваться по ним. Это значит, что мы хотим перебирать элементы один за другим. Это очень важная концепция. Поэтому, интерфейс Collection наследуется от Iterable . Это очень важно, т.к. во-первых, всё что Iterable должно уметь возвращать Iterator по своему содержимому. А во-вторых, всё что Iterable может использоваться в циклах for-each-loop . И именно при помощи итератора в AbstractCollection реализованы такие методы, как contains , toArray , remove . И путь к познанию коллекций начинается с одной из самых распространённых структур данных — списка, т.е. List .

Списки (List)

Итак, списки занимают важное место в иерархии коллекций:

Как мы видим, списки реализуют интерфейс java.util.List. Списки выражают то, что у нас есть коллекция элементов, которые расположены в некоторой последовательности друг за другом. Каждый элемент имеет индекс (как в массиве). Как правило, список позволяет иметь элементы с одинаковым значением. Как мы уже сказали выше, List знает про индекс элемента. Это позволяет получить ( get ) элемент по индексу или задать значением для определённого индекса ( set ). Методы коллекций add , addAll , remove позволяют указать индекс, с которого необходимо их выполнять. Кроме того, у List есть своя версия итератора, которая называется ListIterator . Этот итератор знает про индекс элемента, поэтому он умеет итерироваться не только вперёд, но и назад. Его даже можно создать от определённого места в коллекции. Среди всех реализаций можно выделить две самые часто используемые: ArrayList и LinkedList . Во-первых, ArrayList — это список ( List ) на основе массива ( Array ). Это позволяет добиться "Произвольного доступа" (Random Access) к элементам. Произвольный доступ — это возможность сразу достать элемент по индексу, а не перебирать все элементы, пока не найдём элемент с нужным индексом. Именно массив как основа позволяет этого достичь. Напротив, LinkedList — это связанный (Linked) список (List). Каждая запись в связанном списке представлена в виде Entry , которая хранит сами данные, а так же ссылку на следующую (next) и предыдущую (previous) Entry . Таким образом LinkedList реализует "Последовательный доступ" (Sequential Access). Понятно, что чтобы найти 5-тый элемент нам придётся пройти от первого элемента до последнего, т.к. у нас нет напрямую доступа к пятому элементу. Мы можем получить к нему доступ только от 4-го элемента. Разница в их концепции приведена ниже:

Разбор этой задачи можно посмотреть тут: "Implement A Queue Using Stacks — The Queue ADT ("Implement Queue Using Stacks" on LeetCode)". Вот мы плавно и переходим к новой структуре данных — очередь.

Читайте также: