Лекция
Привет, сегодня поговорим про классы-коллекции, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое классы-коллекции , настоятельно рекомендую прочитать все из категории ООП и практические JAVA.
Для хранения большого количества однотипных данных могут использоваться массивы, но они не всегда являются идеальным решением. Во-первых, длина массива задается заранее и в случае, если количество элементов заранее неизвестно, придется либо выделять память «с запасом», либо предпринимать сложные действия по переопределению массива. Во-вторых, элементы массива имеют жестко заданное размещение в его ячейках, поэтому, например, удаление элемента из массива не является простой операцией.
В программировании давно и эффективно используются такие структуры данных как стек, очередь, список, множество и т.д., объединенные общим названием коллекция. Коллекция — это группа элементов с операциями добавления, извлечения и поиска элемента. Механизм работы операций существенно различается в зависимости от типа коллекции. Например, элементы стека упорядочены в последовательность, добавление нового элемента может происходить только в конец этой последовательности, и получить можно только элемент, находящийся в конце (то есть, добавленный последним). Очередь, напротив, позволяет получить лишь первый элемент (элементы добавляются в один конец последовательности, а «забираются» с другого). Другие коллекции (например, список) позволяют получить элемент из любого места последовательности, а множество вообще не упорядочивает элементы и позволяет (помимо добавления и удаления) только узнать, содержится ли в нем данный элемент.
Язык 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 как со списком (например, по очереди получить все его объекты).
В момент создания новой игры (т.е. Об этом говорит сайт https://intellect.icu . в конструкторе класса Game) надо, очевидно, создать 24 шашки, расположенные на стандартных позициях и добавить их в список checkers. Но список тоже необходимо создать, а мы не можем воспользоваться конструкцией
checkers = new List();
поскольку List не является классом и не имеет конструктора. Нам нужно выбрать любой класс, реализующий интерфейс List и создать объект этого класса. Например, класс Vector
checkers = new Vector();
или класс ArrayList*:
checkers = new ArrayList();
Независимо от того, какой именно класс мы выберем, поле checkers будет иметь тип List и на дальнейшую работу с ним наш выбор не повлияет. Мы будем добавлять шашки в список, удалять их из него, возвращать хранящиеся в списке шашки и т.д. посредством методов интерфейса List.
Интерфейс Collection содержит набор общих методов, которые используются в большинстве коллекций. Рассмотрим основные из них.
add(Object item) — добавляет в коллекцию новый элемент. Метод возвращает true, если добавление прошло удачно и false — если нет*. Если элементы коллекции каким-то образом упорядочены, новый элемент добавляется в конец коллекции.
clear() — удаляет все элементы коллекции.
contains(Object obj) — возвращает true, если объект obj содержится в коллекции и false, если нет.
isEmpty() — проверяет, пуста ли коллекция.
remove(Object obj) — удаляет из коллекции элемент obj. Возвращает false, если такого элемента в коллекции не нашлось.
size() — возвращает количество элементов коллекции.
Существуют разновидности перечисленных методов, которые в качестве параметра принимают любую другую коллекцию. Например, метод addAll(Collection coll) добавляет все элементы другой коллекции coll в конец данной, метод removeAll(Collection coll) удаляет из коллекции все элементы, которые присутствуют также в коллекции coll, а метод retainAll(Collection coll) поступает наоборот, удаляя все элементы, кроме содержащихся в coll.
Метод toArray() возвращает все элементы коллекции в виде массива.
Интерфейс 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 унаследован от интерфейса Collection, но никаких новых методов не добавляет. Изменяется только смысл метода add(Object item) — он не станет добавлять объект item, если он уже присутствует во множестве.
Интерфейс Queue описывает очередь. Элементы могут добавляться в очередь только с одного конца, а извлекаться с другого (аналогично очереди в магазине). Интерфейс Queue так же унаследован от интерфейса Collection. Специфические для очереди методы:
poll() — возвращает первый элемент и удаляет его из очереди.
peek() — возвращает первый элемент очереди, не удаляя его.
offer(Object obj) — добавляет в конец очереди новый элемент и возвращает true, если вставка удалась.
Методы element() и remove() работают аналогично методам poll() и peek(), но если очередь пуста, возбуждают исключение.
Классы-коллекции, реализующие описанные выше интерфейсы, являются наследниками абстрактного классаAbstractCollection. Иерархия этих классов приведена на рисунке (синим цветом показаны интерфейсы). Мы рассмотрим те из них, которые представляют наибольший практический интерес.
Vector (вектор) — набор упорядоченных элементов, к каждому из которых можно обратиться по индексу. По сути эта коллекция представляет собой обычный список.
Особенность вектора в том, что помимо текущего размера, определяемого количеством элементов в нем и возвращаемого методом size(), он имеет емкость, возвращаемую методом capacity() — размер выделенной под элементы памяти, которая может быть больше текущего размера. Ее можно увеличить методом ensureCapacity(int minCapacity) или сравнять с размером вектора методом trimToSize(). Каждый раз, когда нужно добавить в полностью «заполненный» вектор новый элемент, емкость увеличивается с запасом.
В классе Vector четыре конструктора:
Vector() — создает пустой вектор с емкостью в 10 элементов;
Vector(int capacity) — создает пустой вектор указанной емкости;
Vector(int capacity, int increment) — создает пустой вектор указанной емкости, а также задает число, на которое будет увеличиваться емкость при необходимости;
Vector(Collection c) — создает вектор и заполняет его элементами другой коллекции.
Класс Vector реализует интерфейс List, основные методы которого названы выше. К этим методам добавляется еще несколько. Например, метод firstElement() позволяет обратиться к первому элементу вектора, метод lastElement()— к его последнему элементу. Метод removeElementAt(int pos) удаляет элемент в заданной позиции, а методremoveRange(int begin, int end) удаляет несколько подряд идущих элементов. Все эти операции можно было бы осуществить комбинацией базовых методов интерфейса List, так что функциональность принципиально не меняется.
Класс ArrayList — аналог класса Vector. Он представляет собой список и может использоваться в тех же ситуациях. Основное отличие в том, что он не синхронизирован и одновременная работа нескольких параллельных процессов с объектом этого класса не рекомендуется. В обычных же ситуациях он работает быстрее. *
Stack — коллекция, объединяющая элементы в стек. Стек работает по принципу LIFO (последним пришел — первым ушел). Элементы кладутся в стек «друг на друга», причем взять можно только «верхний» элемент, т.е. тот, который был положен в стек последним. Для стека характерны операции, реализованные в следующих методах класса Stack:
push(Object item) — помещает элемент на вершину стека;
pop() — извлекает из стека верхний элемент;
peek() — возвращает верхний элемент, не извлекая его из стека;
empty() — проверяет, не пуст ли стек;
search(Object item) — ищет «глубину» объекта в стеке. Верхний элемент имеет позицию 1, находящийся под ним — 2 и т.д. Если объекта в стеке нет, возвращает -1.
Класс Stack является наследником класса Vector, поэтому имеет все его методы (и, разумеется, реализует интерфейсList). Однако если в программе нужно моделировать именно стек, рекомендуется использовать только пять вышеперечисленных методов*.
Преимущество использования массивов и коллекций заключается не только в том, что можно поместить в них произвольное количество объектов и извлекать их при необходимости, но и в том, что все эти объекты можно комплексно обрабатывать. Например, вывести на экран все шашки, содержащиеся в списке 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 для обхода данного списка.
Напишите класс Student, предоставляющий информацию об имени студента методом getName() и о его курсе методомgetCourse().
Напишите метод printStudents(List students, int course), который получает список студентов и номер курса и печатает в консоль имена тех студентов из списка, которые обучаются на данном курсе. Для обхода списка в этом методе используйте итератор.
Протестируйте ваш метод (для этого предварительно придется создать десяток объектов класса Student и поместить их в список).
LinkedList — двунаправленный список, реализующий интерфейсы List и Queue.
Класс HashSet реализует интерфейс Set. Он применяется в тех случаях, когда надо хранить только одну копию каждого элемента. Одинаковые объекты «вычисляются» с помощью метода hashCode() класса Object, который должен возвращать разные значения для разных объектов.
Класс LinkedHashSet — множество, элементы которого хранятся в виде двунаправленного списка. Его наследник, классTreeSet является упорядоченным множеством, которое хранится в виде бинарного дерева, что обеспечивает быстроту поиска нужного элемента. TreeSet реализует интерфейс SortedSet.
Интерфейс SortedSet описывает множество, элементы которого могут быть упорядочены по некоторому принципу, например в соответствии с естественным порядком его элементов. Элементы множества не проиндексированы, но существует понятие большего и меньшего элемента.
first() и last() возвращают первый и последний элементы множества.
subSet(Object fromElement, Object toElement) возвращает подмножество упорядоченного множества, содержащее элементы, большие fromElement (включая его самого) и меньше toElement. У этого метода есть две простые разновидности headSet(Object toElement) и tailSet(Object fromElement), возвращающие подмножество, состоящее из всех элементов, меньших и больших данного соответственно.
Способ упорядочения элементов описывает интерфейс Comparator. Он имеет два метода:
compare(Object obj1, Object obj2) — возвращает отрицательное число, если obj1 считается меньшим obj2, ноль, если они равны и положительное число, если obj1 больше obj2
equals(Object obj1, Object obj2) — возвращает true, если объекты считаются равными
Можно создать свой собственный способ сравнения элементов, написав класс, реализующий интерфейс Comparator и переопределив методы compare() и equals(). Класс TreeSet, например, имеет конструктор с параметром типаComparator, в который можно передать объект этого нового класса. В результате элементы множества будут отсортированы угодным нам способом.
Напишите методы union(Set set1, Set set2) и intersect(Set set1, Set set2), реализующих операции объединения и пересечения двух множеств. Протестируйте работу этих методах на двух предварительно заполненных множествах. (Вам понадобится написать вспомогательный метод, выводящий все элементы множества в консоль).
Приступайте к написанию основного метода вашей программы, над набросками которого вы уже работали с использованием массивов. На этот раз вы должны получить «настоящий» метод, использующий там, где это необходимо, классы-коллекции.
На этом все! Теперь вы знаете все про классы-коллекции, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое классы-коллекции и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории ООП и практические JAVA
Комментарии
Оставить комментарий
ООП и практические JAVA
Термины: ООП и практические JAVA