Занятие 6

Классы-коллекции

Понятие коллекции

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

В программировании давно и эффективно используются такие структуры данных как стек, очередь, список, множество и т.д., объединенные общим названием коллекция. Коллекция — это группа элементов с операциями добавления, извлечения и поиска элемента. Механизм работы операций существенно различается в зависимости от типа коллекции. Например, элементы стека упорядочены в последовательность, добавление нового элемента может происходить только в конец этой последовательности, и получить можно только элемент, находящийся в конце (то есть, добавленный последним). Очередь, напротив, позволяет получить лишь первый элемент (элементы добавляются в один конец последовательности, а «забираются» с другого). Другие коллекции (например, список) позволяют получить элемент из любого места последовательности, а множество вообще не упорядочивает элементы и позволяет (помимо добавления и удаления) только узнать, содержится ли в нем данный элемент.

Язык Java предоставляет библиотеку стандартных коллекций, которые собраны в пакете java.util, поэтому нет необходимости программировать их самостоятельно.

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

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

Классы-коллекции

Коллекции в библиотеке java.util представлены набором классов и интерфейсов.

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

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

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

Например, у вас есть объект класса String (обычная строка) и вы хотите добавить его в стек stack с помощью метода push(Object item):

String str = "Ценная строка"; stack.push(str);

Коллекция, хранящая элементы типа Object, сразу же «забывает», что ваш объект — строка, поскольку при его добавлении было осуществлено автоматическое приведение типа String к типу Object. Вы можете извлечь ваш объект методом pop(), но чтобы вернуть ему прежний тип (а без этого вы не сможете воспользоваться ни одним из его методов), придется осуществить явное преобразование оператором (String):

str = (String)stack.pop();

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

Но если попытаться привести объект к неправильному типу, возникнет ошибка в программе:

stack.push(new Dog("Шарик", 12)); // помещаем в стек собаку str = (Mouse)stack.pop(); // вынимаем собаку и пытаемся объявить ее мышью, но эти классы не связаны наследованием и программа выдаст ошибку во время выполнения

Так что, возможностью помещать в коллекцию любые объекты, воспользоваться скорее всего не получится. Представьте себе, что ваша программа должна «помнить», что первый элемент списка — строка, второй — число, третий — собака, четвертый — опять число. И обработать их все в цикле она, наверное, не сможет, поскольку у этих объектов нет общих методов. В результате теряются все преимущества использования коллекции. Поэтому в каждую коллекцию следует помещать объекты только одного класса (и производных от него).

Интерфейсы-коллекции

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

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

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

Список представлен в пакете java.util интерфейсом List. Вы можете создавать переменные этого типа и объявлять функции с таким параметром. Например, класс Game в программе игры в шашки (см. задание 16) имеет поле checkers типа List, хранящее все черные и белые шашки (объекты типа Checker). Когда шашку съедают, ее надо просто удалить из списка с помощью одного из удобных методов, определенных в интерфейсе List:

checkers.remove(check); // удаляем из списка checkers съеденную шашку check

Когда программе понадобится узнать обо всех оставшихся шашках (например, чтобы нарисовать их на экране), метод getCheckers() класса Game передаст ей список:

List ch = currentGame.getCheckers(); // здесь currentGame — объект класса Game

Теперь программа может работать с переменной ch как со списком (например, по очереди получить все его объекты).

В момент создания новой игры (т.е. в конструкторе класса Game) надо, очевидно, создать 24 шашки, расположенные на стандартных позициях и добавить их в список checkers. Но список тоже необходимо создать, а мы не можем воспользоваться конструкцией

checkers = new List();

поскольку List не является классом и не имеет конструктора. Нам нужно выбрать любой класс, реализующий интерфейс List и создать объект этого класса. Например, класс Vector

checkers = new Vector();

или класс ArrayList*:

checkers = new ArrayList();

Независимо от того, какой именно класс мы выберем, поле checkers будет иметь тип List и на дальнейшую работу с ним наш выбор не повлияет. Мы будем добавлять шашки в список, удалять их из него, возвращать хранящиеся в списке шашки и т.д. посредством методов интерфейса List.

Интерфейс Collection

Интерфейс Collection содержит набор общих методов, которые используются в большинстве коллекций. Рассмотрим основные из них.

add(Object item) — добавляет в коллекцию новый элемент. Метод возвращает true, если добавление прошло удачно и false — если нет*. Если элементы коллекции каким-то образом упорядочены, новый элемент добавляется в конец коллекции.

clear() — удаляет все элементы коллекции.

contains(Object obj) — возвращает true, если объект obj содержится в коллекции и false, если нет.

isEmpty() — проверяет, пуста ли коллекция.

remove(Object obj) — удаляет из коллекции элемент obj. Возвращает false, если такого элемента в коллекции не нашлось.

size() — возвращает количество элементов коллекции.

Интерфейс List

Интерфейс List описывает упорядоченный список. Элементы списка пронумерованы, начиная с нуля и к конкретному элементу можно обратиться по целочисленному индексу. Интерфейс List является наследником интерфейса Collection, поэтому содержит все его методы и добавляет к ним несколько своих:

add(int index, Object item) — вставляет элемент item в позицию index, при этом список раздвигается (все элементы, начиная с позиции index, увеличивают свой индекс на 1);

get(int index) — возвращает объект, находящийся в позиции index;

indexOf(Object obj) — возвращает индекс первого появления элемента obj в списке;

lastIndexOf(Object obj) — возвращает индекс последнего появления элемента obj в списке;

add(int index, Object item) — заменяет элемент, находящийся в позиции index объектом item;

subList(int from, int to) — возвращает новый список, представляющий собой часть данного (начиная с позиции from до позиции to-1 включительно).

Интерфейс Set

Интерфейс Set описывает множество. Элементы множества не упорядочены, множество не может содержать двух одинаковых элементов. Интерфейс Set унаследован от интерфейса Collection, но никаких новых методов не добавляет. Изменяется только смысл метода add(Object item) — он не станет добавлять объект item, если он уже присутствует во множестве.

Интерфейс Queue

Интерфейс Queue описывает очередь. Элементы могут добавляться в очередь только с одного конца, а извлекаться с другого (аналогично очереди в магазине). Интерфейс Queue так же унаследован от интерфейса Collection. Специфические для очереди методы:

poll() — возвращает первый элемент и удаляет его из очереди.

peek() — возвращает первый элемент очереди, не удаляя его.

offer(Object obj) — добавляет в конец очереди новый элемент и возвращает true, если вставка удалась.

Иерархия классов-коллекций

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

Класс Vector

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

Класс Vector реализует интерфейс List, основные методы которого названы выше. К этим методам добавляется еще несколько. Например, метод firstElement() позволяет обратиться к первому элементу вектора, метод lastElement() — к его последнему элементу. Метод removeElementAt(int pos) удаляет элемент в заданной позиции, а метод removeRange(int begin, int end) удаляет несколько подряд идущих элементов. Все эти операции можно было бы осуществить комбинацией базовых методов интерфейса List, так что функциональность принципиально не меняется.

Класс ArrayList

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

Класс Stack

Stack — коллекция, объединяющая элементы в стек. Стек работает по принципу LIFO (последним пришел — первым ушел). Элементы кладутся в стек «друг на друга», причем взять можно только «верхний» элемент, т.е. тот, который был положен в стек последним. Для стека характерны операции, реализованные в следующих методах класса Stack:

push(Object item) — помещает элемент на вершину стека;

pop() — извлекает из стека верхний элемент;

peek() — возвращает верхний элемент, не извлекая его из стека;

empty() — проверяет, не пуст ли стек;

search(Object item) — ищет «глубину» объекта в стеке. Верхний элемент имеет позицию 1, находящийся под ним — 2 и т.д. Если объекта в стеке нет, возвращает -1.

Класс Stack является наследником класса Vector, поэтому имеет все его методы (и, разумеется, реализует интерфейс List). Однако если в программе нужно моделировать именно стек, рекомендуется использовать только пять вышеперечисленных методов*.

Паттерн проектирования Iterator

Преимущество использования массивов и коллекций заключается не только в том, что можно поместить в них произвольное количество объектов и извлекать их при необходимости, но и в том, что все эти объекты можно комплексно обрабатывать. Например, вывести на экран все шашки, содержащиеся в списке checkers. В случае массива мы пользуемся циклом for:

for (int i = 1; i < array.length; i++){ // обрабатываем элемент array[i] }

Имея дело со списком, мы можем поступить аналогичным образом, только вместо array[i] писать array.get(i). Но мы не можем поступить так с коллекциями, элементы которых не индексируются (например, очередью или множеством). А в случае индексированной коллекции надо хорошо знать особенности ее работы: как определить количество элементов, как обратиться к элементу по индексу, может ли коллекция быть разреженной (т.е. могут ли существовать индексы, с которыми не связано никаких элементов) и т.д.

В программировании существует несколько испытанных временем и детально проработанных приемов структурной организации программы, называемых паттернами (шаблонами) проектирования. Один из таких паттернов называется Iterator. Идея заключается в том, что к коллекции «привязывается» объект, единственное назначение которого — выдать все элементы этой коллекции в некотором порядке, не раскрывая ее внутреннюю структуру.

В пакете java.util описан интерфейс Iterator, воплощающий этот паттерн проектирования. Он имеет всего три метода:

next() возвращает очередной элемент коллекции, к которой «привязан» итератор (и делает его текущим). Порядок перебора определяет сам итератор.

hasNext() возвращает true, если перебор элементов еще не закончен

remove() удаляет текущий элемент

Интерфейс Collection помимо рассмотренных ранее методов, имеет метод iterator(), который возвращает итератор для данной коллекции, готовый к ее обходу. С помощью такого итератора можно обработать все элементы любой коллекции следующим простым способом:

Iterator iter = coll.iterator(); // coll — коллекция, элементы которой мы хотим обработать while (iter.hasNext()) { // обрабатываем объект, возвращаемый методом iter.next() }

Для коллекций, элементы которых проиндексированы, определен более функциональный итератор, позволяющий двигаться как в прямом, так и в обратном направлении, а также добавлять в коллекцию элементы. Такой итератор имеет интрефейс ListIterator, унаследованный от интерфейса Iterator и дополняющий его следующими методами:

previous() — возвращает предыдущий элемент (и делает его текущим);

hasPrevious() — возвращает true, если предыдущий элемент существует (т.е. текущий элемент не является первым элементом для данного итератора);

add(Object item) — добавляет новый элемент перед текущим элементом;

set(Object item) — заменяет текущий элемент;

nextIndex() и previousIndex() — служат для получения индексов следующего и предыдущего элементов соответственно.

В интерфейсе List определен метод listIterator(), возвращающий итератор ListIterator для обхода данного списка.

Класс LinkedList

LinkedList — двунаправленный список, реализующий интерфейсы List и Queue.

Классы-множества

Класс HashSet реализует интерфейс Set. Он применяется в тех случаях, когда надо хранить только одну копию каждого элемента. Одинаковые объекты «вычисляются» с помощью метода hashCode() класса Object, который должен возвращать разные значения для разных объектов.

Класс LinkedHashSet — множество, элементы которого хранятся в виде двунаправленного списка. Его наследник, класс TreeSet является упорядоченным множеством, которое хранится в виде бинарного дерева, что обеспечивает быстроту поиска нужного элемента. TreeSet реализует интерфейс SortedSet.

---

Задание

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