Java. Урок 31. Коллекции

Уроки для начинающих   10 февраля 2013  Автор статьи:  

В языках программирования существуют различные структуры данных: стеки, очереди, множества и так далее. Они имеют различные принципы работы, например стек позволяет добавлять элемент в конец и получать только последний элемент, а очередь наоборот, позволяет получать первый элемент, а добавлять в конец. Для универсальности представления структур данных используют коллекции. Коллекция — абстрактная структура данных, скрывающая способ хранения и связи объектов некоторого типа, а так же методы работы с этими объектами и коллекцией в целом. Стандартные коллекции расположены в библиотеке java.util. Использование коллекций дает широкие возможности при программировании, так как каждая коллекция эффективно справляется со своей задачей, поэтому каждый программист должен знать все коллекции языка, который он изучает. Вы спросите почему нельзя реализовать коллекцию самому? Можно, но зачем, если она уже написана и отлажена, притом ее реализация максимально универсальна и подойдет для большинства задач. Как реализовать различные типы данных в коллекциях, если они создаются как обычные классы некоторой библиотеки? Для коллекций придумали параметризацию, т.е возможность указывать тип данных элементов в <> после названия класса, например:

public class TestClass {//объявляем параметризированный класс
public static void test(){
TestClass t = new TestClass();//создаем
}
}

Так как большинство коллекций параметризированны, то мы при описании интерфейсов и классов будем указывать T, что означает любой класс, которым вы параметризируете коллекцию.

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

Collection — самый общий интерфейс:

  • add(T e) — добавить элемент e
  • clear() — очистить
  • addAll(Collection col) — добавить все элементы другой коллекции, с схожим типом данных
  • contains(Object o) — содержит ли коллекция элемент
  • isEmpty() — возвращает пуста ли коллекция
  • remove(Object o) — удаляет элемент
  • removeAll(Collection col) — удаляет все элементы, которые есть в коллекции col.
  • size() — возвращает количество элементов в коллекции
  • containsAll(Collection col) — возвращает, содержатся ли все элементы col в коллекции.
  • toArray(T[] a) — возвращает массив, который содержит все элементы коллекции, на вход принимает массив, который будет заполнен ими.
  • retainAll(Collection col) — удаляет все элементы, не принадлежащие col
  • toArray() — возвращает массив Object-ов, который содержит все элементы коллекции.

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

  • get(int index) — получаем элемент по индексу
  • add(int index, T e) — вставляет элемент в позицию
  • indexOf(Object obj) — возвращает первое вхождение элемента в список
  • lastIndexOf(Object obj) — возвращает последнее вхождение
  • set(int index, T e) — заменяет элемент в позиции index
  • subList(int from, int to) — возвращает новый список, представляющий собой часть главного

Set — множество. Содержит все операции интерфейса Collection, но некоторые из них имеют другой смысл. например операция add добавляет только уникальные элементы, зато операции поиска элемента происходят быстрее чем в списке.
Queue — очередь. Реализует основные операции очереди:

  • poll() — возвращает первый элемент и удаляет его
  • peek() — возвращает первый элемент очереди, не удаляя его.
  • offer(T e) — добавляет элемент в конец очереди
Классы коллекций

Vector — класс реализующий обычный список, но лучше не использовать его в своих программах, а пользоваться аналогом ArrayList.
ArrayList — реализует интерфейс List, т.е в тех случаях, когда вам нужен упорядоченный список на основе массива вам следует использовать его.
LinkedList — двунаправленный список, который реализует интерфейс List и Queue. Если использовать его как List, то скорость операций вставки и удаления возрастет, а операций получения значения по индексу наоборот упадет. LinkedList является хорошей реализацией очереди, так как все операции интерфейса Queue в ней происходят за константу.
Stack — стек. Рассмотрим его операции:

  • push(T e) — добавляет элемент на вершину стека
  • pop() — удаляет и возвращает из стека верхний элемент
  • peek() — возвращает верхний элемент, не удаляя его
  • empty() — возвращает пуст ли стек
  • search(Object item) — возвращает на каком месте находится элемент в стеке

HashSet — реализует интерфейс Set на основе хешей.
TreeSet — реализует интерфейс Set на основе красно — черного дерева, что позволяет получить хорошую скорость операций.
В чем отличие между этими классами? Hashset не гарантирует время работы операций, но в среднем выполняет операцию вставки за константу, а TreeSet гарантирует выполнение любой операции пропорционально логарифму числа операций в нем. Используя интерфейс Set вы с легкостью сможете переключаться между этими классами, выбирая наиболее подходящий для вашей задачи.
На этом мы заканчиваем разговор о коллекциях, но для лучшего понимания я советую прочитать статью о паттерне Iterator в Java, в которой вы узнаете, что такое Iterator и как обращаться к элементам различных коллекций универсально.

  • al

    >>TreeSet — реализует интерфейс Set на основе —> красно — черного дерева <—, что позволяет получить хорошую скорость операций.

    ???

    • Красно-черное дерево — это такое сбалансированное дерево. Special for you публикую статью, которая уже пол года в черновиках ждет своего выпуска, про сбалансированные деревья. Почему она не публиковалась? Ну там картинок нужных нет… : http://cybern.ru/random-binary-search-tree.html Ну вообще это все связанно с алгоритмами, и если у тебя аналогичный вопрос возникнет, то придется лезть в них, так как в уроках для начинающих, я как бы про язык рассказываю, а не про них, так как все что с ними связанно отдельно сидит.

  • d

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

    А это где?

    • Временно не доступно=)Никто нас не финансирует и то что должно было выйти еще в прошлом году до сих пор не вышло=)

  • Ipman

    Stack основан на Vector и то и другое использовать можно и нужно . они внутри синхронизированы.

    • Vector — это устаревшее, не путайте народ=)

  • Алексей Константинов

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

Научиться программировать

  • на Delphi

  • на Java

  • на C++