Лекция 13

Вид материала

Содержание

Подобный материал:

ЛЕКЦИЯ 13

Контейнеры (коллекции)

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

Для решения этой насущной проблемы Java имеет несколько способов хранения объектов (или скорее, ссылок на объекты). Встроенным типом является массив, который уже обсуждался ранее. Также библиотека утилит Java имеет набор так называемых контейнерных классов.

Массивы - это просто один способ хранить объекты, т.е. наиболее простой вид контейнера. Есть два момента, которые отличают массивы от других типов контейнеров: эффективность и тип.

Массив является наиболее эффективным способом, из тех, которые обеспечивает Java, для хранения объектов и доступа к ним в случайном порядке (на самом деле, речь идет о ссылках на объекты). Массив - это простая линейная последовательность, которая делает быстрым доступ к элементам, но вы расплачиваетесь за эту скорость: когда вы создаете массив объектов, его размер фиксирован и не может изменяться в течение всей продолжительности жизни этого массива объектов.

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

Другие основные контейнерные классы List, Set и Map имеют дело с объектами, как будто они не имеют определенного типа. То есть, они трактуются как тип Object - корневой класс для всех классов в Java. С одной точки зрения, это работает прекрасно: вам необходимо построить только один контейнер и все объекты будут подходить для этого контейнера. Это второй момент, когда массив лучше общих контейнеров: когда вы создаете массив, вы создаете его для содержания данных определенного типа. Это значит, что вы имеете проверку типа во время компиляции для предотвращения помещения неправильного типа или ошибку типа при извлечении. Конечно, Java предохранит вас от посылки объекту неподходящего сообщения и во время компиляции и во время выполнения. Так что вы, так или иначе, не рискуете, это даже лучше, что компилятор направляет вас, это быстрее при выполнении и при этом меньше вероятность, что конечный пользователь будет удивлен, получив исключение.

Резюме. Для того, чтобы обеспечить эффективность и обязательную проверку типов, если это возможно, необходимо использовать массивы. Однако, когда вы пробуете решить более общую проблему хранения множества объектов в некотором едином хранилище, возможности массива могут быть слишком ограничены.

Контейнеры примитивов

Как мы знаем, массивы могут создаваться для хранения примитивных типов так же, как и для хранения объектов. Контейнерные классы могут хранить только ссылки на объекты. Возможно, использовать классы-оболочки, такие как Integer, Double и т.п., для помещения примитивных значений в контейнер, но классы-оболочки для примитивов не всегда удобно использовать. Очевидно, что, более эффективно создавать и пользоваться массивом примитивов, чем контейнером для оболочек примитивов.

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

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

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

Библиотека контейнеров Java 2 принимается за проблему “хранения ваших объектов” и делит ее на две отдельные концепции:

Коллекция (Collection): группа индивидуальных элементов, часто с определенными правилами, применяемыми к элементам. Список (List) должен хранить элементы в определенной последовательности, а Набор (Set) не может иметь дублирующиеся элементы.
Карта (Map): группа объектных пар ключ - значение. Карта может возвращать Набор своих ключевых значений, Коллекцию своих значений или Набор своих пар. Карты, как и массивы, могут иметь несколько измерений без добавления новой концепции: вы просто создаете Карту, чьими значениями являются другие карты (а значениями этих Карт тоже могут быть Карты и т.д.).

Иерархия контейнеров

Map

Collection

List

Set

HashMap

TreeMap

ArrayList

LinkedList

HashSet

TreeSet

Как упомянуто ранее, есть две основных категории в библиотеке контейнеров Java. Различие основывается на числе элементов, содержащихся в каждой ячейке контейнера. Категория Collection (коллекция) хранит только один элемент в каждой ячейке. Сюда включается List (список), который хранит группы элементов в указанном порядке, и Set (набор), который позволяет добавление одного элемента каждого типа. ArrayList - это тип List, а HashSet - это тип Set. Для добавление элементов в любой из Collection существует метод add( ).

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

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

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

Collection содержит единичные элементы, а Map содержит ассоциированные пары.
Как и массив, List также ассоциирует с объектом цифровые индексы — вы можете думать и о массивах, и о List, как об упорядоченных контейнерах. List автоматически сам изменяет размер, когда вы добавляете дополнительные элементы. Но List может хранить только ссылки на Object, поэтому он не может хранить примитивные типы и вы должны всегда выполнять приведение, когда вытягиваете ссылку на Object из контейнера.
Используйте ArrayList, если вы выполняете много обращений в случайном порядке, а LinkedList, если будете выполнять много вставок и удалений из середины списка.
Поведение очереди, двойной очереди и стека организуется через LinkedList.
Map - это способ ассоциации не чисел, а объектов с другими объектами. Дизайн HashMap фокусируется на повторном доступе, а TreeMap хранит свои ключи в упорядоченном виде и поэтому не так быстр, как HashMap.
Set принимает объекты только одного типа. HashSet обеспечивает максимально быстрый поиск, а TreeSet хранит свои элементы в упорядоченном виде.

==================================================================================

Неудобство контейнеров: неизвестный тип

“Неудобство” при использовании контейнеров Java в том, что вы теряете информацию о типе, когда помещаете объект в контейнер. Контейнер содержит ссылки на Object, который является корнем всех классов, кроме примитивных типов, которые не наследуются ни от чего.

Так как информация о типе отбрасывается, когда вы помещаете ссылку на объект в контейнер, нет ограничений на тип объекта, который может быть помещен в контейнер, даже если вы предназначаете его только для хранения, скажем, объектов типа «Кот». Кто-либо может так же легко поместить в этот же контейнер объект типа «Собака».
Так как информация о типе теряется, есть только одна вещь, которую контейнер знает, он хранит ссылки на объекты. Вы должны выполнить приведение к правильному типу перед использованием объекта.

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

Для начала вы можете думать об ArrayList, как о “массиве, который автоматически растягивает себя”. Использование ArrayList достаточно простое: создание, помещение в него объектов с помощью add( ), и, позже, получение их с помощью get( ) и индекса, так же как будто вы имеете дело с массивом, но без квадратных скобок. ArrayList также имеет метод size( ), который позволяет вам узнать сколько элементов было добавлено, так что вы по невнимательности не выйдете за пределы и не получите исключение.

Создание сознающего тип ArrayList

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

//: c09:MouseList.java

// Сознающий тип ArrayList.

import java.util.*;

public class MouseList {

private ArrayList list = new ArrayList();

public void add(Mouse m) {

list.add(m);

}

public Mouse get(int index) {

return (Mouse)list.get(index);

}

public int size() { return list.size(); }

} ///:~

================================================================================

Итераторы

В любом контейнерном классе вы должны иметь способ поместить вещь внутри и способ достать вещь наружу. Кроме этого, первичная задача контейнера — хранить вещи. В случае ArrayList: add( ) - способ, который вставляет объекты, а get( ) - один из способов получит вещи наружу. ArrayList достаточно гибок, вы можете выбрать все что угодно в любое время и выбирать различные элементы одновременно, используя разные индексы.

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

Концепция итераторов может быть использована для достижения этой абстракции. Итератор - это объект, чья работа заключается в перемещении по последовательности объектов и выборе каждого объекта в такой последовательности, чтобы клиентский программист не знал или не заботился о подлежащей структуре этой последовательности. Кроме того, итераторы это обычно то, что называется “легковесными” объектами: объекты, дешевые в создании.

Java Iterator позволяет:

Просить контейнер передать вам Iterator, используя метод, называемый iterator( ). Этот Iterator будет готов к возврату первого элемента последовательности при первом вызове метода next( ).
Получать следующий объект в последовательности с помощью next( ).
Проверять есть ли еще объекты в последовательности с помощью hasNext( ).
Удалять последний элемент, возвращенный итератором, с помощью remove( ).

Однако в общем случае вы захотите сделать что-то большее, нежели вызов методов Object, так что вы вновь будете применять приведение типов. Вы должны принимать во внимание, что вам интереснее получить Iterator для последовательности определенного типа и приводить результирующие объекты к этому типу (если вы ошиблись, получите исключение времени выполнения).

================================================================================

Функциональность Collection

Приведенная ниже таблица показывает все, что вы можете делать с Collection (за исключением тех методов, которые автоматически приходят от Object), и таким образом, все, что вы можете делать с Set или List. (List также имеет дополнительную функциональность). Map не наследуются от Collection, о нем будет рассказано отдельно.

boolean add(Object)	Гарантирует, что контейнер содержит аргумент. Возвращает false, если не может добавить аргумент. (Это “необязательный” метод описывается позже в этой главе.)
boolean addAll(Collection)	Добавляет все элементы аргумента. Возвращает true, если любые элементы были добавлены. (“Необязательно”)
void clear( )	Удаляет все элементы контейнера. (“Необязательно”)
boolean contains(Object)	true, если контейнер содержит аргумент.
boolean containsAll(Collection)	true, если контейнер содержит все элементы аргумента.
boolean isEmpty( )	true, если контейнер не имеет элементов.
Iterator iterator( )	Возвращает Iterator, который вы можете использовать для обхода элементов контейнера.
boolean remove(Object)	Если аргумент присутствует в контейнере, один экземпляр этого элемента будет удален. Возвращает true, если произошло удаление. (“Необязательно”)
boolean removeAll(Collection)	Удаляет все элементы, содержащиеся в аргументе. Возвращает true, если произошло любое удаление. (“Необязательно”)
boolean retainAll(Collection)	Остаются только те элементы, которые содержатся в аргументе (в теории множеств называется “пересечением”). Возвращает true, если произошли любые изменения. (“Необязательно”)
int size( )	Возвращает число элементов контейнера.
Object[] toArray( )	Возвращает массив, содержащий все элементы контейнера.
Object[] toArray(Object[] a)	Возвращает массив, содержащий все элементы контейнера, чей тип, скорее массив, а не простой Object (вы должны привести массив к правильному типу).

Обратите внимание, что здесь нет функции get( ) для выбора элементов в случайном порядке. Это происходит потому, что Collection также включает Set, который содержит свой внутренний механизм упорядочивания (и это делает выборку в случайном порядке бессмысленной). Таким образом, если вы хотите проверить все элементы Collection, вы должны использовать итератор; это единственный способ получить вещи назад.

================================================================================

Функциональность List

Основной List достаточно прост для использования, по сравнению с ArrayList. Хотя большую часть времени вы будите просто использовать add( ) для вставление объектов, get( ) для получения их обратно в любое время и iterator( ) для получения Iterator последовательности, есть также набор других методов, которые также полезны.

Кроме того, на самом деле есть два типа List: основной ArrayList, выделяется доступом к элементам в случайном порядке, и более мощный LinkedList (который не предназначен для быстрого доступа в случайном порядке, но имеет более общий набор методов).

List (интерфейс)	Порядок - наиболее важная особенность для List; он обещает, что элементы будут храниться в определенной последовательности. List добавляет несколько методов к набору Collection, которые позволяют вставку и удаление элементов в середине списка List. (Это рекомендуется только для LinkedList.) List производит ListIterator, и, используя его, вы можете пройти весь List в обоих направлениях, а также вставлять и извлекать элементы из середины списка List.
ArrayList*	List реализуется массивом. Позволяет быстрый доступ в случайном порядке к элементами, но медленный, когда вставляются и удаляются элементы из середины списка. ListIterator должен использоваться только для прямого и обратного движения по ArrayList, но не для вставления и удаления элементов, что является очень дорогим, по сравнению с LinkedList.
LinkedList	Обеспечивает оптимальный доступ к последовательности, который недорогой при вставках и удаленьях из середины списка List. Относительно медленный при случайном выборе элементов. (Используйте для этого ArrayList.) Также имеются методы addFirst( ), addLast( ), getFirst( ), getLast( ), removeFirst( ) и removeLast( ) (которые не определены во всех интерфейсах или базовых классах), позволяющие использовать связанный список как стек, очередь и двойную очередь.

==================================================================================

Создание стека из LinkedList

Стек иногда называется контейнером, типа “последний вошел, первый вышел” (LIFO). То есть, то, что вы “втолкнете” в стек последним, то будет первым, что вы можете “вытолкнуть”. Как и все другие контейнеры Java, то, что вы можете втолкнуть и вытолкнуть - это Object, так что вы должны выполнить приведение типов для того, что вытолкните, если вы не используете черты поведения, присущие классу Object.

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

Если вам нужно только поведение стека, наследование не подойдет, так как при этом получится класс со всеми методами, имеющимися в LinkedList.

Создание очереди из LinkedList

Очередь - это контейнер, типа “первый вошел, первый вышел” (FIFO). То есть, вы помещаете вещь в конец, а получаете ее с другого конца. Таким образом, порядок, в котором вы помещаете вещи в контейнер, остается тем же самым, в котором они выходят. LinkedList имеет методы для поддержки поведения очереди, так что он может быть использован для создания соответствующего класса.

==================================================================================

Функциональность Set

Set имеет точно такой же интерфейс, как и Collection, но здесь нет дополнительной функциональности, как и в случае двух других списков. Вместо этого Set - это точно Collection, он имеет отличающееся поведение. (Это идеальное использование наследования и полиморфизма: для выражения разницы в поведении.) Set отклоняет хранение нескольких экземпляров одного значения объекта.

Set (интерфейс)	Каждый элемент, который вы добавляете в Set, должен быть уникальным; в противном случае Set не добавит дублирующий элемент. Object, добавляемый в Set, должен определить equals( ) для установления уникальности объектов. Set имеет точно такой же интерфейс, что и Collection. Интерфейс Set не гарантирует сохранение порядка следования элементов в определенной последовательности.
HashSet*	Для Set, в которых важно время поиска. Object должен определить hashCode( ).
TreeSet	Упорядоченный Set поддерживаемый деревом. Этим способом вы можете получить упорядоченную последовательность из Set.

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

Порядок, содержащийся в HashSet, отличается от TreeSet, так как каждый из них имеет различные способы сортировки элементов, так чтобы они могли быть найдены позднее. (TreeSet хранит их отсортированными, а HashSet использует функцию хеширования, которая предназначена специально для многократного поиска.) Когда создаете свои собственные типы, запомните, что для Set необходим способ обработки порядка сортировки, что означает, что вы должны реализовать интерфейс Comparable и определить метод compareTo( ).

================================================================================

SortedSet

Если вы имеете SortedSet (для которого поддерживается только TreeSet), элементы будут гарантированно располагаться в упорядоченном виде, что позволяет использовать дополнительную функциональность, обеспечиваемую методами интерфейса SortedSet:

Comparator comparator(): Производит Comparator, используемый для этого Set, или null для естественного упорядочивания.

Object first(): Производит низший элемент.

Object last(): Производит высший элемент.

SortedSet subSet(fromElement, toElement): Производит вид этого Set с элементами от fromElement, включительно, по toElement, исключительно.

SortedSet headSet(toElement): Производит вид этого Set с элементами, меньшими toElement.

SortedSet tailSet(fromElement): Производит вид этого Set с элементами большими, или равными fromElement.

=================================================================================

Функциональность Map

ArrayList позволяет вам выбирать из последовательности объектов, используя номер, другими словами, он ассоциирует номера с объектами. Но что, если вы хотите выбирать из последовательности объектов, используя какой-то другой критерий? Например, стек: его критерием выбора является “последняя вещь, втолкнутая в стек”. Мощными поворотными моментами этой идеи “выборки из последовательности” поочередно стали карта (map), словарь (dictionary) или ассоциативный массив (associative array). Концептуально они выглядят как ArrayList, но вместо поиска объектов по номерам вы ищете их, используя другой объект. Часто это является ключевым процессом в программе.

Эта концепция показана в Java как интерфейс Map. Метод put(Object key, Object value) добавляет значение (то, что вы хотите) и ассоциирует с ним ключ (то, по чему вы будете искать). get(Object key) производит значение по соответствующему ключу. Вы также можете проверить Map, узнав, содержится ли там ключ или значение с помощью containsKey( ) и containsValue( ).

Стандартная библиотека Java содержит два различных типа Map: HashMap и TreeMap. Оба они имеют один и тот же интерфейс (так как они оба реализуют Map), но они отличаются одним способом: эффективностью. Если вы думаете, что это должно выполнятся с помощью get( ), это выглядит приятно медленным, например, при поиске в ArrayList, содержащем ключи. HashMap - достаточно скоростной контейнер. Вместо медленного поиска ключа, он использует специальное значение, называемое хеш-код. Хэш-код - это способ получения определенной информации об объекте путем опроса и включения “относительно уникального” int для этого объекта. Все Java объекты могут производить хеш-код, а метод hashCode( ) - это метод корневого класса Object. HashMap берет hashCode( ) объекта и использует его для быстрого вылавливания ключа. В результате получаем ощутимое прибавление производительности [50].

Map (Интерфейс)	Содержит ассоциированные пары ключ-значение, так что вы можете производить поиск значения, используя ключ.
HashMap*	Реализация, основывающая на хеш-таблице. (Используйте это вместо Hashtable.) Обеспечивает постоянную по времени производительность при вставлении и поиске пар. Производительность может регулироваться конструктором, который позволяет вам устанавливать емкость и коэффициент загрузки хеш-таблицы.
TreeMap	Реализация, основывающаяся на красно-черном дереве. Когда вы просматриваете ключи или пары, они будут упорядочены (определяется Comparable или Comparator, будет обсуждаться позднее). Преимущество TreeMap в том, что вы получаете результат отсортированным. TreeMap - это просто Map с методом subMap( ), который позволяет вам возвращать часть дерева.

==================================================================================

SortedMap

Если у вас есть SortedMap (из которых поддерживается только один TreeMap), то гарантируется, что ключи будут храниться упорядоченными, что позволяет получить дополнительную функциональность, которая обеспечивается методами интерфейса SortedMap:

Comparator comparator(): Производит сравниватель, используемый для этого Map, или null для естественного упорядочивания.

Object firstKey(): Производит низший ключ.

Object lastKey(): Производит высший ключ.

SortedMap subMap(fromKey, toKey): Производит вид этого Map с ключами от fromKey, включительно, по toKey, исключительно.

SortedMap headMap(toKey): Производит вид этого Map с ключами, меньшими toKey.

SortedMap tailMap(fromKey): Производит вид этого Map с ключами, большими или равными fromKey.

=================================================================================

Выбор реализации

Теперь вы должны понимать, что на самом деле есть только три компоненты контейнера: Map, List и Set, и только два из трех реализуют каждый интерфейс. Если вам необходимо использовать функциональность, предлагаемую определенным интерфейсом, как вам решить какую именно реализацию использовать?

Различия между контейнерами часто исходят из того, что они “обслуживают”; то есть, структуры данных, которые физически реализуют необходимый интерфейс. Это означает, например, что ArrayList и LinkedList реализуют интерфейс List, поэтому ваша программа будет выдавать одинаковый результат независимо от того, что вы используете. Однако ArrayList обслуживается массивом, а LinkedList реализован обычным способом для списков с двойным связыванием, в котором есть индивидуальные объекты, каждый из которых содержит данные наряду со ссылками на предыдущий и следующий элемент списка. По этой причине, если вы хотите выполнять много вставок и удалений в середину списка, наиболее подходящим выбором будет LinkedList. (LinkedList также имеет дополнительную функциональность, которая основывается на AbstractSequentialList.) Если это не нужно, то ArrayList обычно быстрее.

В качестве другого примера, Set может быть реализован либо как TreeSet, либо как HashSet. TreeSet основывается на TreeMap и предназначается для производства постоянно упорядоченного множества. Однако, если вы будете использовать большой набор данных для вашего Set, производительность вставки в TreeSet уменьшится. Когда вы пишите программу, в которой нужен Set, вы должны выбрать по умолчанию HashSet и изменить на TreeSet, если более важной задачей является получение постоянного упорядочивания множества.

Как и ожидалось, массивы быстрее контейнеров при доступе в случайном порядке и итерациях. Вы можете видеть, что случайный доступ (get( )) дешевле для ArrayList и дороже для LinkedList. (Странно, но итерации быстрее для LinkedList, чем для ArrayList, что немного противоречит интуиции.) С другой стороны, вставка и удаление из середины списка значительно дешевле для LinkedList, чем для ArrayList — особенно удаление. Лучший подход, вероятно, это выбор по умолчанию ArrayList и замена его на LinkedList, если вы обнаружите проблемы производительности при многочисленных вставках и удалениях из середины списка. И, конечно, если вы работаете с группой элементов фиксированного размера, используйте массив.

==================================================================================

Сортировка и поиск в списках

Утилиты для выполнения сортировки и поиска для списков (List) имеют те же имена и сигнатуры, что и для отсортированных массивов, но это статические методы класса Collections, а не Arrays.

Метод shuffle( ) класса Collections смешивает порядок в List.

Утилиты

Есть несколько других полезных утилит в классе Collections:

enumeration(Collection)	Производит Enumeration старого стиля для аргумента.
max(Collection) min(Collection)	Производит максимальный или минимальный элемент для аргумента, используя естественный метод сравнения для объектов Collection.
max(Collection, Comparator) min(Collection, Comparator)	Производит максимальный или минимальный элемент Collection, используя Comparator.
reverse( )	Переворачивает все элементы на местах.
copy(List dest, List src)	Копирует элементы из src в dest.
fill(List list, Object o)	Заменяет все элементы списка на o.
nCopies(int n, Object o)	Возвращает неизменный List размера n, чьи ссылки будут указывать o.

Обратите внимание, что min( ) и max( ) работают с объектами Collection, а не с List, так что вам нет необходимости беспокоится о том, отсортирован Collection или нет.

Blog

Лекция 13

Содержание

ЛЕКЦИЯ 13

Контейнеры (коллекции)

Контейнеры примитивов

Иерархия контейнеров

Map

Collection

List Set

HashMap TreeMap

ArrayList LinkedList HashSet TreeSet

==================================================================================

Неудобство контейнеров: неизвестный тип

Создание сознающего тип ArrayList

================================================================================

Итераторы

================================================================================

Функциональность Collection

================================================================================

Функциональность List

==================================================================================

Создание стека из LinkedList

Создание очереди из LinkedList

==================================================================================

Функциональность Set

================================================================================

SortedSet

=================================================================================

Функциональность Map

==================================================================================

SortedMap

=================================================================================

Выбор реализации

==================================================================================

Сортировка и поиск в списках

Утилиты

List

Set

HashMap

TreeMap

ArrayList

LinkedList

HashSet

TreeSet