Работа с коллекциями в Java 7

1 Теоретическая часть

1.1 Обзор стандартных контейнерных интерфейсов и классов

1.1.1 Общие сведения

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

Библиотека классов и интерфейсов для поддержки коллекций называется Java collections framework (JCF) . Он появился начиная с версии Java 1.2. В версии 1.5 в JCF добавлена поддержка обобщений.

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

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

• интерфейсы
• стандартные реализации интерфейсов
• алгоритмы
• утилиты для работы с массивами

Кроме того, поддерживаются контейнеры Java 1.1, не обеспечивающие стандартизированного интерфейса, и вследствие этого считающиеся устаревшими и не рекомендованы для использования. Это Vector, Enumeration, Stack, BitSet и некоторые другие. Например, класс Vector предоставляет функциональность, аналогичную ArrayList. Сейчас эти контейнеры считаются устаревшими и не рекомендованы к применению. Вместо них следует использовать соответствующие обобщенные контейнеры Java 5.

Стандартные контейнеры Java позволяют хранить ссылки на объекты классов, производных от java.lang.Object. Контейнерные интерфейсы и классы представлены в пакете java.util, а также во вложенных в него пакетах (например, java.util.concurrent). Начиная с Java 5, все контейнерные классы реализованы как обобщенные.

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

Интерфейс List (список) описывает пронумерованную коллекцию (последовательность), элементы которой могут повторяться. Существует стандартная абстрактная реализации списка - класс AbstractList. Этот класс, производный от AbstractCollection, предоставляет ряд полезных средств. Практически в той или иной форме реализованы все методы, кроме get() и size(). Тем не менее, для конкретной реалзации списка большинство функций следует перекрыть. В качестве вложенного размещен класс, реализующий интерфейс Iterator. класс AbstractList - базовый для ArrayList. Класс AbstractSequentialList, производный от AbstractList, является базовым для класса LinkedList.

Интерфейс Set реализован классами HashSet и LinkedHashSet. Интерфейс SortedSet, производный от Set, предоставляет производный интерфейс NavigableSet, реализованный классом TreeSet. Интерфейс Map реализован классом HashMap. Интерфейс SortedMap, производный от Map, реализован классом TreeMap.

Классы HashSet, LinkedHashSet и HashMap используют для идентификации элементов так называемые хеш-коды. Хэш-код - это уникальная последовательность битов фиксированной длины. Для каждого объекта эта последовательность считается уникальной. Хэш-коды обеспечивают быстрый доступ к данным по некоторому ключу. Все объекты Java могут генерировать хэш-коды: метод hashCode() определен для класса Object.

Для большинства коллекций присутствуют как "обычные" реализации, так и реализации, безопасные с точки зрения потоков управления, например CopyOnWriteArrayList, ArrayBlockingQueue и т. д. Соответствующие интерфейсы и реализации будут рассмотрены позже.

1.1.2 Интерфейс Collection

Интерфейс Collection является базовым для многих интерфейсов Collection Framework и объявляет наиболее общие методы коллекций:

Примечание: в таблице не указаны методы с реализацией по умолчанию, добавленные в Java 8.

Следующий пример демонстрирует работу методов интерфейса. В примере используется класс ArrayList как самая простая реализация интерфейса Collection:

package ua.inf.iwanoff.collections;

import java.util.*;

public class CollectionDemo {

    public static void main(String[] args) {
        Collection<Integer> c = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
        System.out.println(c.size());      // 5
        System.out.println(c.isEmpty());   // false
        System.out.println(c.contains(4)); // true
        c.add(6);
        System.out.println(c);             // [1, 2, 3, 4, 5, 6]
        c.remove(1);
        System.out.println(c);             // [2, 3, 4, 5, 6]
        Collection<Integer> c1 = new ArrayList<>(Arrays.asList(3, 4));
        System.out.println(c.containsAll(c1));// true
        c.addAll(c1);
        System.out.println(c);             // [2, 3, 4, 5, 6, 3, 4]
        Collection<Integer> c2 = new ArrayList<>(c); // копия 
        c.removeAll(c1);
        System.out.println(c);             // [2, 5, 6]
        c2.retainAll(c1);
        System.out.println(c2);            // [3, 4, 3, 4]
        c.clear();
        System.out.println(c);             // []       
    }

}

1.2 Использование списков

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

Существует стандартная абстрактная реализации списка - класс AbstractList. Этот класс, производный от AbstractCollection, предоставляет ряд полезных средств. Практически в той или иной форме реализованы все методы, кроме get() и size(). Тем не менее, для конкретной реалзации списка большинство функций следует перекрыть. В качестве вложенного размещен класс, реализующий интерфейс Iterator. класс AbstractList - базовый для ArrayList. Класс AbstractSequentialList, производный от AbstractList, является базовым для класса LinkedList.

Создать пустой список ссылок на объекты некоторого типа (SomeType) можно с помощью конструктора по умолчанию:

List<SomeType> al = new ArrayList<SomeType>();

Можно сразу описать ссылку на ArrayList:

ArrayList<SomeType> al = new ArrayList<SomeType>();

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

Реализация Класс ArrayList содержит в качестве поля массив elementData элементов типа Object. Физический размер массива (capacity), если не вызывать конструктор с явным указанием этого размера, по умолчанию равен 10. При каждом добавлении элемента вызывается внутренний метод ensureCapacity(), который в случае заполнения массива осуществляет создание нового массива с переписыванием в него имеющихся элементов. Размер нового массива вычисляется по формуле (старый_размер * 3) / 2 + 1.

При удалении элементов физический размер массива не уменьшается. Для экономии памяти после многократного удаления элементов целесообразно вызывать метод trimToSize().

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

List<String> al = new ArrayList<String>();
al.add("abc");
al.add("def");
al.add("xyz");
al.add(2, "ghi"); // Вставка новой строки перед "xyz"

Можно создать новый список с использованием существующего. Новый список содержит ссылку на копии элементов. Например:

List<String> a1 = new ArrayList<String>(al);    

С помощью статической функции asList() класса java.util.Arrays можно создать список из существующего массива. Массив можно создать непосредственно в списке параметров функции. Например:

String[] arr = {"one", "two", "three"};
List<String> a2 = Arrays.asList(arr);
List<String> a3 = Arrays.asList("four", "five");    

Для списков перегружена функция toString(), которая позволяет вывести все элементы списка на экран без использования циклов. Элементы выводятся в квадратных скобках:

System.out.println(a3); // [four, five]    

Списки допускают работу с отдельными элементами. Метод size() возвращает количество элементов, содержащихся в списке. Метод get() возвращает элемент с указанным индексом (позиция в списке). Как и элементы массивов, элементы списков пронумерованы с нуля. В следующем примере строки выводятся с помощью функции println():

List<String> al = new ArrayList<String>();
al.add("abc");
al.add("def");
al.add("xyz");
for (int i = 0; i < al.size(); i++) {
    System.out.println(al.get(i));
}

Функция subList(fromIndex, toIndex) возвращает список, составленный из элементов начиная с элемента с индексом fromIndex и не включая элемент с индексом toIndex. Например:

System.out.println(al.subList(1, 3)); // [def, xyz]    

Метод set() позволяет изменить объект, хранящийся в указанной позиции. Метод remove() удаляет объект в указанной позиции:

al.set(0, "new");
al.remove(2);
System.out.println(al); // [new, def]

Функция contains() возвращает true, если список содержит указанный элемент. Например:

if (al.contains("abc")) {
    System.out.println(al);
}    

Функция toArray() возвращает ссылку на массив копий объектов, ссылки на которые хранятся в списке.

Object [] a = al.toArray();
System.out.println(a[1]);    // def
(al.toArray()) [2] = "text"; // Изменение элементов нового массива

Для сохранения целых и действительных значений в коллекциях часто используют классы-оболочки Integer и Double соответственно.

Можно удалять элементы с помощью метода remove(индекс_удаляемого_элемента). При удалении элементов текущая величина capacity не уменьшается, что может привести к своеобразным утечкам памяти. Поэтому для экономии памяти есть смысл вызывать метод trimToSize() .

В тех случаях, когда операции добавления и удаления элементов в произвольных местах применяют чаще, чем выбор произвольного элемента, целесообразно использовать класс LinkedList, который сохраняет объекты с помощью связанного списка. Для удобной работы добавлены также методы addFirst(), addLast(), removeFirst() и removeLast().

LinkedList<String> list = new LinkedList<String>();
list.addLast("last"); // То же, что list.add("last");
list.addFirst("first");
System.out.println(list); // [first, last]
list.removeFirst();
list.removeLast();
System.out.println(list); // []

Эти специфические функции добавлены именно в LinkedList, поскольку они не могут быть эффективно реализованы в ArrayList с применением массивов.

Связный список – это одна из так называемых динамических структур данных. Другие примеры таких структур – очереди, стеки и бинарные деревья. Связный список представляет собой линейную структуру данных, построенную из отдельных элементов, содержащих непосредственно данные и ссылки (указатели) на соседние элементы. Обычно для представления отдельного элемента (узла) используется отдельный класс (структура, запись, в зависимости от языка).

Связные списки могут быть односвязными и двусвязными. В односвязном списке элементы содержат ссылки только на следующий элемент (или на null, если элемент – последний). Каждый элемент двусвязного списка, кроме непосредственно данных, содержит ссылки на предыдущий и последующий элементы. Для крайних элементов соответствующие ссылки также равны null.

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

Связный список, реализованный в Java контейнером LinkedList, представляет собой двунаправленный список, где каждый элемент содержит ссылки на предыдущий и следующий элементы. Отдельный элемент списка представлен следующим внутренним классом:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }

}

Для прохождения по списку объектов используется итератор - специальный вспомогательный объект. Интерфейс Iterator, определенный в пакете java.util. Любой итератор имеет три метода:

boolean hasNext(); // проверяет, есть ли еще элементы в контейнере,
                   // и возвращает true, если еще есть элементы последовательности
Object  next();    // возвращает ссылку на следующий элемент
void    remove();  // удаляет последний выбранный элемент (на который ссылается итератор)

Первое обращение к методу next() возвращает ссылку на начальный элемент последовательности. Коллекции Java возвращают объект-итератор с помощью метода iterator():

List<String> s = new ArrayList<String>();
s.add("First");
s.add("Second");
for (Iterator<String> i = s.iterator(); i.hasNext(); ) {
    System.out.println(i.next());
}

Как видно из приведенного примера, итератор тоже является обобщенным типом. Новая форма цикла for позволяет обойти список без явного создания итератора:

List<Integer> a = new ArrayList<Integer>();
a.add(1);
a.add(2);
a.add(3);
a.add(4);
for (Integer i : a) {
    System.out.print(i + " ");
}

Специальный вид итератора списка, ListIterator, предоставляет дополнительные возможности итерации, в частности, проход по списку в обратном порядке. В следующем примере для проверки, является ли слово палиндромом используется список символов и ListIterator, обеспечивающий проход в обратном порядке:

package ua.inf.iwanoff.collections;

import java.util.*;

public class ListIteratorTest {

    public static void main(String[] args) {
        String palStr = "racecar";
        List<Character> palindrome = new LinkedList<Character>();
        for (char ch : palStr.toCharArray()) {
            palindrome.add(ch);
        }
        System.out.println("Input string is: " + palStr);
        ListIterator<Character> iterator = palindrome.listIterator();
        ListIterator<Character> revIterator = palindrome.listIterator(palindrome.size());
        boolean result = true;
        while (revIterator.hasPrevious() && iterator.hasNext()) {
            if (iterator.next() != revIterator.previous()) {
                result = false;
                break;
            }
        }
        if (result) {
            System.out.print("Input string is a palindrome");
        }
        else {
            System.out.print("Input string is not a palindrome");
        }
    }

}

1.3 Работа с множествами

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

Внутренняя организация множеств основана на использовании ассоциативных массивов и будет рассмотрена ниже.

Метод add() добавляет элемент к множеству и возвращает true если элемент ранее отсутствовал. В противном случае элемент не добавляется, а метод add() возвращает false. Все элементы множества удаляются с помощью метода clear().

Set<String> s = new HashSet<String>();
System.out.println(s.add("First"));  // true
System.out.println(s.add("Second")); // true
System.out.println(s.add("First"));  // false
System.out.println(s);               // [First, Second]
s.clear();
System.out.println(s);               // []

Метод remove() удаляет указанный элемент множества, если таковой имеется. Метод contains() возвращает true, если множество содержит указанный элемент.

В приведенном ниже примере к множеству целых чисел добавляется десять случайных значений в диапазоне от -9 до 9:

package ua.inf.iwanoff.collections;

import java.util.*;

public class SetOfIntegers {

    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<Integer>();
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            Integer k = random.nextInt() % 10;
            set.add(k);
        }
        System.out.println(set);
    }

}

Результирующее множество, как правило, содержит менее 10 цифр, поскольку отдельные значения могут повторяться. Поскольку мы используем TreeSet, числа хранятся и выводятся в упорядоченном виде (по умолчанию - по возрастанию). Для того, чтобы добавить именно десять различных чисел, программу можно модифицировать, например, с применением цикла while вместо for:

while (set.size() < 10) {
    . . .
}

Можно создать массив, содержащий копии елементов множества. Например, так можно вывести элементы в обратном порядке:

for (int i = set.size() - 1; i >= 0; i--) {
    System.out.println(set.toArray()[i]);
}

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

Порядок указания порядка элементов TreeSet можно задать, реализовав интерфейс Comparable, либо передав в конструктор TreeMap ссылку на объект класса, реализующий интерфейс Comparator . Например, так можно отсортировать дерево в обратном порядке:

package ua.inf.iwanoff.collections;

import java.util.*;

public class CompTest {

    public static void main(String args[]) {
        TreeSet<String> ts = new TreeSet<String>(new Comparator<String>() 
        { 
            @Override
            public int compare(String s1, String s2) {
                return s2.compareTo(s1);
            }
        });
        ts.add("C");
        ts.add("E");
        ts.add("D");
        ts.add("B");
        ts.add("A");
        ts.add("F");
        for (String element : ts)
            System.out.print(element + " ");
        }
    }
}

1.4 Работа с очередями и стеками

Очередь в широком смысле представляет собой структуру данных, заполняемую поэлементно, и позволяющую извлекать объекты по определенному правилу. В узком смысле этим правилом является "первый пришёл - первый вышел" (FIFO, First In — First Out). В очереди, организованной по принципу FIFO, добавление элемента возможно лишь в конец очереди, извлечение - только из начала очереди.

В библиотеке контейнеров очередь представлена интерфейсом Queue. Методы, объявленные в этом интерфейсе, представлены в следующей таблице:

Метод offer() возвращает false, если не удалось добавить элемент, например, если реализована очередь с ограниченным количеством элементов. В этом случае метод add() генерирует исключение. Аналогично remove() и element() генерируют исключение, если очередь пустая, а poll() и peek() в этом случае возвращают null.

Для реализации очереди удобнее всего использовать класс LinkedList, реализующий интерфейс Queue. Например:

package ua.inf.iwanoff.collections;

import java.util.LinkedList;
import java.util.Queue;

public class SimpleQueueTest {
 
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.add("First");
        queue.add("Second");
        queue.add("Third");
        queue.add("Fourth");
        String s;
        while ((s = queue.poll()) != null) {
            System.out.print(s + " "); // First Second Third Fourth
        }
    }

}

Класс PriorityQueue упорядочивает элементы в соответствии с компаратором (объектом класса, реализующим интерфейс Comparator), заданным в конструкторе в качестве параметра. Если объект создать с помощью конструктора без параметров, элементы будут упорядочены в естественном порядке (для чисел - по возрастанию, для строк - по алфавиту). Например:

package ua.inf.iwanoff.collections;

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueTest {
 
    public static void main(String[] args) {
        Queue<String> queue = new PriorityQueue<>();
        queue.add("First");
        queue.add("Second");
        queue.add("Third");
        queue.add("Fourth");
        String s;
        while ((s = queue.poll()) != null) {
            System.out.print(s + " "); // First Fourth Second Third
        }
    }

}

Интерфейс Deque (дек, double-ended-queue) предоставляет возможность добавлять и удалять элементы с обоих концов. Методы, объявленные в этом интерфейсе, представлены в следующей таблице:

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

Для реализации интерфейса можно использовать специальный класс ArrayDeque, либо связный список (LinkedList).

Стек представляет собой структуру данных, организованную по принципу "последний пришёл - первый вышел" (LIFO, last in - first out). Возможны три операции со стеком: добавление элемента (push), удаление элемента (pop) и чтение головного элемента (peek).

В JRE 1.1 стек представлен классом Stack. Например:

package ua.inf.iwanoff.collections;

import java.util.Stack;

public class StackTest {
  
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("First");
        stack.push("Second");
        stack.push("Third");
        stack.push("Fourth");
        String s;
        while (!stack.isEmpty()) {
            s = stack.pop();
            System.out.print(s + " "); // Fourth Third Second First
        }
    }

}

Этот класс в настоящее время не рекомендован к использованию. Вместо него можно использовать интерфейс Deque, который объявляет аналогичные методы. Например:

package ua.inf.iwanoff.collections;

import java.util.ArrayDeque;
import java.util.Deque;

public class AnotherStackTest {

    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("First");
        stack.push("Second");
        stack.push("Third");
        stack.push("Fourth");
        String s;
        while (!stack.isEmpty()) {
            s = stack.pop();
            System.out.print(s + " "); // Fourth Third Second First
        }
    }

}

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

1.5 Статические методы класса Collections. Алгоритмы

1.5.1 Создание специальных контейнеров с использованием класса Collections

Как класс Arrays для массивов, для коллекций существует вспомогательный класс Collections. Этот класс предоставляет ряд статических функций для работы с коллекциями, в частности со списками. Большая группа функций предназначена для создания коллекций различных типов. Следующий пример демонстрирует создание списков и просто некоторой коллекции с помощью статических методов класса Collections, соответственно, пустого списка, "одиночки" и немодифицируемого списка из обычного:

package ua.inf.iwanoff.collections;

import java.util.*;

public class CollectionsCreationDemo {
    public static void main(String[] args) {
        List<Integer> emptyList = Collections.emptyList();
        System.out.println(emptyList); // []
        List<Integer> singletonList = Collections.singletonList(10);
        System.out.println(singletonList); // [10]
        List<Integer> list = new ArrayList<>(Arrays.<Integer>asList(1, 2, 3));
        List<Integer> unmodifiableList = Collections.unmodifiableList(list);
        Collection<Integer> collection = Collections.unmodifiableCollection(list);
    }
}

Все приведенные выше функции создают немодифицируемые наборы данных.

Аналогично работают методы, создающие соответствующие множества - emptySet(), singleton(), unmodifiableSet().

Имеется также возможность создания коллекций, осуществляющих проверку типов во время выполнения программы и недопущение добавления элементов несоответсвтующего типа. Это соответственно методы checkedCollection, checkedList(), checkedSet(), checkedSortedSet(), checkedMap(), checkedSortedMap(), создающие проверяемые коллекции из обычных.

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

1.5.2 Алгоритмы

Под алгоритмом в библиотеке коллекций следует понимать некоторую функцию, реализующую работу с коллекцией (получение некоторого результата либо преобразование элементов колекции). В Java Collections API эта функция как правило, статическая и обобщенная.

Как и класс Arrays, класс Collections содержит реализацию статических функций sort() и fill().Кроме того, есть большое количество статических функций, которые позволяют обрабатывать списки без применения циклов. Это, например, такие функции, как max() (поиск максимального элемента), min() (поиск минимального элемента), indexOfSubList() (поиск индекса первого полного вхождения подсписков в список), frequency() (определение количества раз вхождения определенного элемента в список), reverse() (замена порядка элементов на противоположный), rotate() (циклический сдвиг списка на заданное количество элементов), shuffle() ("перемешивание" элементов), nCopies() (создание нового списка с определенным количеством одинаковых элементов). Использование этих функции можно проиллюстрировать на следующем примере:

List<Integer> a = Arrays.asList(0, 1, 2, 3, 3, -4);
System.out.println(Collections.max(a)); // 3 
System.out.println(Collections.min(a)); // -4
System.out.println(Collections.frequency(a, 2)); // 1 раз
System.out.println(Collections.frequency(a, 3)); // 2 раза
Collections.reverse(a);   // меняем порядок элементов на противоположный
System.out.println(a);    // [-4, 3, 3, 2, 1, 0]
Collections.rotate(a, 3); // сдвигает список циклически на 3 элемента
System.out.println(a);    // [2, 1, 0, -4, 3, 3]
List<Integer> sublist = Collections.nCopies(2, 3); // Новый список содержит 2 тройки 
System.out.println(Collections.indexOfSubList(a, sublist)); // 4
Collections.shuffle(a);   // "тасуем" элементы
System.out.println(a);    // элементы в произвольном порядке
Collections.sort(a);
System.out.println(a);    // [-4, 0, 1, 2, 3, 3]
List<Integer> b = new ArrayList<Integer>(a);
Collections.fill(b, 8);
System.out.println(b);    // [8, 8, 8, 8, 8, 8]
Collections.copy(b, a);
System.out.println(b);    // [-4, 0, 1, 2, 3, 3]
System.out.println(Collections.binarySearch(b, 2)); // 3
Collections.swap(b, 0, 5);
System.out.println(b);    // [3, 0, 1, 2, 3, -4]
Collections.replaceAll(b, 3, 10);
System.out.println(b);    // [10, 0, 1, 2, 10, -4]

Класс Collections также предоставляет методы специально для работы со списками, получение первого и последнего индекса начала вхождения подсписка в список (indexOfSubList(), lastIndexOfSubList()) и т. д.

Начиная с версии JDK 1.8, некоторые алгоритмы реализованы как нестатические методы интерфейса Collection и других базовых интерфейсов с реализацией по умолчанию. Например, removeIf(Predicate<? super E> filter), replaceAll(UnaryOperator<E> operator), sort(Comparator <? super E> c).

1.6 Ассоциативные массивы

Ассоциативные массивы могут хранить пары ссылок на объекты. Ассоциативные массивы тоже являются обобщенными типами. Ассоциативные массивы в Java представлены обобщенным интерфейсом Map, который реализован, в частности, классом HashMap. Интерфейс SortedMap, производный от Map, требует упорядоченного по ключу хранения пар. Интерфейс NavigableMap, появившийся в java SE 6, расширяет SortedМap и добавляет новые возможности поиска по ключу. Этот интерфейс реализован классом TreeMap.

Каждое значение (объект), которое хранится в ассоциативном массиве, связывается с конкретным значением другого объекта (ключа). Метод put(key, value) добавляет значение (value) и ассоциирует с ним ключ (key). Если ассоциативный массив ранее содержал пары с указанным ключом, новое значение замещает старое. Метод put() возвращает предыдущее значение, связанное с ключом, или null, если ключ отсутствовал. Метод get(Object key) возвращает объект по заданному ключу. Для проверки нахождения ключа и значения применяются методы containsKey() и containsValue().

На логическом уровне можно представить ассоциативный массив через три вспомогательных коллекции:

• keySet - множество значений ключа;
• values - список значений;
• entrySet - множество пар ключ-значение.

Через соответствующие функции keySet(), values() и entrySet() можно осуществлять определенные действия, в первую очередь последовательное прохождение элементов.

В приведенном ниже примере вычисляется количество вхождений различных слов в предложение. Слова и соответствующие количества хранятся в ассоциативном массиве. Использование класса TreeMap гарантирует алфавитный порядок слов (ключей).

import java.util.*;

public class WordsCounter {
    public static void main(String[] args) {
        Map<String, Integer> m = new TreeMap<String, Integer>();
        String s = "the first men on the moon";
        StringTokenizer st = new StringTokenizer(s);
        while (st.hasMoreTokens()) {
            String word = st.nextToken();
            Integer count = m.get(word);
            m.put(word, (count == null) ? 1 : count + 1);
        }
        for (String word : m.keySet()) {
            System.out.println(word + " " + m.get(word));
        }
    }

}

Использование keySet() предусматривает отдельный поиск каждого значения по ключу. Более рекомендуемым является обход ассоциативного массива через множество пар:

    for (Map.Entry<?, ?> entry : m.entrySet()) {
        System.out.println(entry.getKey() + " " + entry.getValue());
    }    

Здесь метод entrySet() позволяет получить представление ассоциативного массива в виде коллекции Set.

Порядок сортировки элементов TreeMap также можно изменить, указав в качестве параметра конструктора TreeMap объект класса, реализующий интерфейс Comparator, либо задав ключ как объект класса, реализующий интерфейс Comparable:

package ua.inf.iwanoff.collections;

import java.util.*;

public class TreeMapKey implements Comparable<TreeMapKey> {
    String name;

    public String getName() {
        return name;
    }

    private TreeMapKey(String name) {
        super();
        this.name = name;
    }

    @Override
    public int compareTo(TreeMapKey o) {
        return name.substring(getName().indexOf(" ")).trim()
          .compareToIgnoreCase(o.getName().substring(o.getName().indexOf(" ")).trim());
    }

    public static void main(String args[]) {
        TreeMap<TreeMapKey, Integer> tm = new TreeMap<TreeMapKey, Integer>();
        tm.put(new TreeMapKey("Петр Иванов"), new Integer(1982));
        tm.put(new TreeMapKey("Иван Петров"), new Integer(1979));
        tm.put(new TreeMapKey("Василий Сидоров"), new Integer(1988));
        tm.put(new TreeMapKey("Сидор Васильев"), new Integer(1980));
        for (Map.Entry<TreeMapKey, Integer> me : tm.entrySet()) {
            System.out.print(me.getKey().getName() + ": ");
            System.out.println(me.getValue());
        }
        System.out.println();
    }

}

Класс WeakHashMap<K,V> позволяет сборщику мусора удалять из ассоциативного массива значения по ключу, ссылка на который вышла из области видимости приложения. Класс LinkedHashMap<K,V> запоминает порядок добавления объектов в ассоциативный массив и образует при этом двусвязный список ключей.

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

Класс Properties, производный от Hashtable вместо пар произвольных объектов сохраняет пару строк. Если в конкретной задаче и ключи и значения элементов ассоциативного массива имеют тип String, удобнее воспользоваться классом Properties. В классе Properties определены методы getProperty(String key) и setProperty(String key, String value).

1.7 Внутренняя организация множеств и ассоциативных контейнеров

1.7.1 Реализация множеств и ассоциативных контейнеров с использованием хеширования

Для хранения данных в HashSet и HashMap используется хеширование.

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

Организация хранения данных в классах HashSet и HashMap аналогична. Рассмотрим организацию представления данных на примере контейнера HashMap. Вложенный класс представляет Entry пару ключ-значение:

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    // ...Далее следует конструктор и ряд вспомогательных методов
}

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

Эффективность операций добавления, поиска и удаления зависит от реализации хеш-функции. Если она выдает постоянное значение, контейнер превращается в связный список с низкой эффективностью.

1.7.2 Реализация контейнеров на базе двоичных деревьев

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

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

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

Обычно для двоичных деревьев поиска реализуют следующие основные операции

• добавление элемента
• получение (поиск) элемента
• удаление элемента (узла)
• обход дерева

Двоичное дерево называется идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1. У несбалансированного дерева это правило не соблюдается. Простейшая реализация дерева дает несбалансированное дерево. В зависимости от порядка добавления элементов дерево может быть сбалансированным или совсем несбалансированным. Допустим, что двоичное дерево хранит целые значения. Если числа от 1 до 7 добавлять в определенном порядке (например, 4, 2, 3, 1, 6, 7, 5), может получиться идеально сбалансированное дерево:

Если же числа добавлять в порядке возрастания, получится сильно несбалансированное дерево:

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

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

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

Например, можно получить такое красно-черное дерево (с сайта ru.wikipedia.org):

При добавлении нового узла (всегда красного) иногда приходится перекрашивать дерево и "оборачивать" его. Добавление вершин с учетом ограничений и "оборачивание" с переносом узлов делает дерево самосбалансированным. Красно-черные деревья используются для построения контейнеров TreeSet и TreeMap.

1.8 Создание собственных контейнеров

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

В некоторых случаях необходимо только обходить элементы некоторой последовательности с помощью альтернативной формы цикла for. Для этого достаточно реализовать интерфейс Iterable<>. Он требует реализации функции, возвращающей итератор. Чаще всего для реализации итератора создают внутренний нестатический класс. В следующем примере создается класс "Предложение" с итератором, который перемещается по отдельным словам. В результате программа выводит слова введенного предложения в отдельных строках:

package ua.inf.iwanoff.collections;

import java.util.Iterator;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Sentence implements Iterable<String> {
    private String text;

    public Sentence(String text) {
        this.text = text;
    }

    private class WordsIterator implements Iterator<String> {
        StringTokenizer st = new StringTokenizer(text);

        @Override
        public boolean hasNext() {
            return st.hasMoreTokens();
        }

        @Override
        public String next() {
            return st.nextToken();
        }

        @Override
        public void remove() {
            throw new RuntimeException("Not implemented!");     
        }

    }

    public Iterator<String> iterator() {
        return new WordsIterator();
    }

    public static void main(String[] args) {
        String text = new Scanner(System.in).nextLine();
        Sentence sentence = new Sentence(text);
        for (String word : sentence) {
            System.out.println(word);
        }
    }

}

В большинстве случаев для создания итераторов необходимо описание так называемого курсора – переменной, которая ссылается на текущий элемент последовательности. В этом случае реализация метода next() предполагает перемещение курсора и возвращение ссылки на текущий элемент. Например:

public class SomeArray<E> implements Iterable<E> {
    private E[] arr;

    ...

    private class InnerIterator implements Iterator<E> {
        int cursor = -1;

        @Override
        public boolean hasNext() {
            return cursor < arr.length - 1;
        }

        @SuppressWarnings("unchecked")
        @Override
        public E next() {   
            return arr[++cursor];
        }

        @Override
        public void remove() {
            throw new RuntimeException("Not implemented");   
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new InnerIterator();
    }
  ...
}

Для создания полноценных собственных контейнеров лучше всего воспользоваться имеющимися абстрактными классами. Это AbstractCollection<E>, AbstractList<E>, AbstractMap<K,V>, AbstractQueue<E>, AbstractSet<E>, а также некоторые абстрактные вспомогательные классы. Например, для того, чтобы создать собственный список (только для чтения), формально достаточно перекрыть два абстрактных метода – get() и size(). При работе со списками только для чтения методы типа add(), set(), remove() и прочие, предназначенные для изменения списка, генерируют исключение UnsupportedOperationException(). В следующем примере создается простейший список (только для чтения):

package ua.inf.iwanoff.collections;

import java.util.AbstractList;

public class MyList extends AbstractList<String> {
    String[] arr = { "one", "two", "three" };

    @Override
    public String get(int index) {
        return arr[index];
    }

    @Override
    public int size() {
        return arr.length;
    }

    public static void main(String[] args) {
        MyList list = new MyList();
        for (String elem : list) {
            System.out.println(elem); {
        }
        System.out.println(list.subList(0, 2));  // [one, two]
        System.out.println(list.indexOf("two")); // 1
        list.add("four"); // Исключение "UnsupportedOperationException"
    }
}

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

2 Примеры программ

2.1 Сумма элементов типа Double

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

package ua.inf.iwanoff.collections;

import java.util.*;

public class SumOfElements {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Double> a = new ArrayList<Double>();
        double d = 1; // начальное значение не должно быть 0
        while (d != 0) {
            d = scanner.nextDouble();
            a.add(d);
        }
        double sum = 0;
        for (double x : a) { // неявный итератор
            sum += x;
        }
        System.out.println("Сумма: " + sum);
    }

}    

Чтение чисел с клавиатуры осуществляется до тех пор, пока пользователь не введет значение 0.

2.2 Индекс максимального элемента

Следующая программа находит номер максимального элемента в списке целых чисел. Для заполнения списка можно использовать массив с начальными значениями элементов. Массив неявно создается во время выполнения функции asList().

package ua.inf.iwanoff.collections;

import java.util.*;

public class MaxElement {

    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(2, 3, -7, 8, 11, 0);
        int indexOfMax = 0;
        for (int i = 1; i < a.size(); i++) {
            if (a.get(i) > a.get(indexOfMax)) {
                indexOfMax = i;
            }
        }
        System.out.println(indexOfMax + " " + a.get(indexOfMax));
    }

}

2.3 Реализация класса для представления массива точек с помощью списка

Еще одна возможная реализация представления массива точек, определенного в предыдущем занятии, основана на использовании списка точек. В проекте, содержащем класс AbstractArrayOfPoints, создаем новый пакет и в нем - класс ListOfPointObjects. Для обеспечения возможности использования классов AbstractArrayOfPoints и Point добавляем соответствующие утверждения импорта.

Исходный код класса будет иметь следующий вид:

package ua.inf.iwanoff.collections;

import java.util.ArrayList;
import lesson105.AbstractArrayOfPoints;
import lesson105.Point;

public class ListOfPointObjects extends AbstractArrayOfPoints {
    ArrayList<Point> p = new ArrayList<>();

    @Override
    public void setPoint(int i, double x, double y) {
        p.get(i).setPoint(x, y);
    }

    @Override
    public double getX(int i) {
        return p.get(i).getX();
    }

    @Override
    public double getY(int i) {
        return p.get(i).getY();
    }

    @Override
    public int count() {
        return p.size();
    }

    @Override
    public void addPoint(double x, double y) {
        p.add(new Point(x, y));
    }

    @Override
    public void removeLast() {
        p.remove(count() - 1);
    }

    public static void main(String[] args) {
        new ListOfPointObjects().test();
    }
}

Результаты должны быть идентичными полученным ранее.

2.4 Буквы предложения в алфавитном порядке

В приведенном ниже примере вводится предложение и выводятся все различные буквы предложения (не считая разделителей) в алфавитном порядке:

package ua.inf.iwanoff.collections;

import java.util.*;

public class Sentence {
  
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // Функция nextLine() читает строку до конца:
        String sentence = scanner.nextLine();
        // Создаем множество разделителей:
        Set<Character> delimiters = new HashSet<Character>(
            Arrays.asList(' ', '.', ',', ':', ';', '?', '!', '-', '(', ')', '\"'));
        // Создаем множество букв:
        Set<Character> letters = new TreeSet<Character>();
        // Добавляем все буквы кроме разделителей:
        for (int i = 0; i < sentence.length(); i++) {
            if (!delimiters.contains(sentence.charAt(i))) {
                letters.add(sentence.charAt(i));
            }
        }
        System.out.println(letters);
    }
  
}

2.5 Произведение вводимых чисел

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

package ua.inf.iwanoff.collections;

import java.util.*;

public class Product {

    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityQueue<>(100, new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return -Double.compare(i1, i2);
            }
        });
        Scanner scanner = new Scanner(System.in);
        Integer k;
        do {
            k = scanner.nextInt();
            if (k != 0) {
                queue.add(k);
            }
        }
        while (k != 0);
        int p = 1;
        while ((k = queue.poll()) != null) {
            p *= k;
            System.out.print(k + " "); 
        }
        System.out.println();
        System.out.println(p);
    }

}

2.6 Проверка корректности скобок

В приведенном ниже примере вводится строка и проверяется корректность открытия и закрытия скобок:

package ua.inf.iwanoff.collections;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Brackets {

    public static void main(String[] args) {
        try {
            Deque<Character> brackets = new ArrayDeque<>();
            String s = new Scanner(System.in).nextLine();
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    brackets.push('(');
                }
                if (s.charAt(i) == ')')
                  brackets.pop();
            }
            if (!brackets.isEmpty()) {
                throw new Exception();
            }
            System.out.println("Строка корректна");
        }
        catch (Exception e) {
            System.out.println("Строка некорректна");
        }
    }

}

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

package ua.inf.iwanoff.collections;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class BracketsWithoutExceptions {

    public static void main(String[] args) {
        Deque<Character> brackets = new ArrayDeque<>();
        String s = new Scanner(System.in).nextLine();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                brackets.push('(');
            }
            if (s.charAt(i) == ')') {
                if (brackets.poll() == null) {
                    System.out.println("Строка некорректна: " + 
                                  "лишние закрывающиеся скобки");
                    return;
                }
            }
        }
        if (!brackets.isEmpty()) {
            System.out.println("Строка некорректна: не все скобки закрыты");
        }
        else {
            System.out.println("Строка корректна");
        }
    }

}

Последний вариант позволяет отдельно диагностировать различные ошибки.

2.7 Данные о странах в ассоциативном массиве

Данные о странах (название и территория) можно хранить в ассоциативном массиве. Вывод осуществляется по алфавиту стран:

package ua.inf.iwanoff.collections;

import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

public class Countries {

    public static void main(String[] args) {
        SortedMap<String, Double> countries = new TreeMap<>();
        countries.put("Украина", 603700.0);
        countries.put("Германия", 357021.0);
        countries.put("Франция", 547030.0);
        for (Map.Entry<?, ?> entry : countries.entrySet())
            System.out.println(entry.getKey() + " " + entry.getValue());  
    }

}

2.8 Создание однонаправленного списка

В приведенном ниже примере создается и заполняется однонаправленный список:

package ua.inf.iwanoff.collections;

public class SinglyLinkedList<E> {

    private class Node {
        E    data;
        Node next;
        Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node first = null;
    private Node last  = null;
    private int  count = 0;

    public void add(E elem) {
        Node newNode = new Node(elem, null);
        if (last == null) {
            first = newNode;
        }
        else {
            last.next = newNode;
        }
        last = newNode;
        count++;
    }

    public void removeFirstOccurrence(E value) {
        // Отдельно проверяем первый элемент
        if (first != null && first.data.equals(value) { 
            first = first.next; 
            count--; 
        }
        else {
            Node link = first;
            while (link.next != null) {
                if (link.next.data.equals(value)) {
                    link.next = link.next.next;
                    count--;
                }
                if (link.next == null) {
                    last = link;
                    break; // удалили последний элемент
                }
                link = link.next;
            }
        }
    }

    public final int size() {
        return count;
    }

    @Override
    public String toString() {
        String s = "size = " + size() + "\n[";
        Node link = first;
        while (link != null) {
            s += link.data;
            link = link.next;
            if (link != null) {
                s += ", ";
            }
        }
        s += "]\n";
        return s;
    }

    public static void main(String[] args) {
        SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println(list);
        // Удаляем средний элемент
        list.removeFirstOccurrence(3); 
        System.out.println(list);
        // Удаляем первый элемент:
        list.removeFirstOccurrence(1);
        System.out.println(list);
        // Удаляем последний элемент:
        list.removeFirstOccurrence(4);
        System.out.println(list);
    }
}

2.9 Создание двоичного дерева

В приведенном ниже примере создается и заполняется обычное (несбалансированное) двоичное дерево, содержащее пары целое / строка:

package ua.inf.iwanoff.collections;

public class BinaryTree {

    // Класс для представления узла
    public static class Node {
        int    key;
        String value;
        Node   leftChild;
        Node   rightChild;
        
        Node(int key, String name) {
            this.key = key;
            this.value = name;
        }

        @Override
        public String toString() {
            return "Key: " + key + " Value:" + value;
        }
    }

    private Node root;

    public void addNode(int key, String value) {
        // Создаем новый узел:
        Node newNode = new Node(key, value);
        if (root == null) { // первый добавленный узел
            root = newNode;
        }
        else {
            // Начинаем обход:
            Node currentNode = root;
            Node parent;
            while (true) {
                parent = currentNode;
                // Проверяем ключи:
                if (key < currentNode.key) {
                    currentNode = currentNode.leftChild;
                    if (currentNode == null) {
                        // Помещаем узел в нужное место:
                        parent.leftChild = newNode;
                        return;
                    }
                }
                else { 
                    currentNode = currentNode.rightChild;
                    if (currentNode == null) {
                        // Помещаем узел в нужное место:
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }

    // Обход узлов в порядке возрастания ключей
    public void traverseTree(Node currentNode) {
        if (currentNode != null) {
            traverseTree(currentNode.leftChild);
            System.out.println(currentNode);
            traverseTree(currentNode.rightChild);
        }
    }

    public void traverseTree() {
        traverseTree(root);
    }

    // Поиск узла по ключу
    public Node findNode(int key) {
        Node focusNode = root;
        while (focusNode.key != key) {
            if (key < focusNode.key) {
                focusNode = focusNode.leftChild;
            }
            else {
                focusNode = focusNode.rightChild;
            }
            // Не нашли:
            if (focusNode == null) {
                return null;
            }
        }
        return focusNode;
    }

    // Тест:
    public static void main(String[] args) {
        BinaryTree continents = new BinaryTree();
        continents.addNode(1, "Европа");
        continents.addNode(3, "Африка");
        continents.addNode(5, "Австралия");
        continents.addNode(4, "Америка");
        continents.addNode(2, "Азия");
        continents.addNode(6, "Антарктида");
        continents.traverseTree();
        System.out.println("\nКонтинент с ключом 4:");
        System.out.println(continents.findNode(4));
    }
}

2.10 Создание собственного контейнера на базе списка ArrayList

В приведенном ниже примере реализован класс для представления массива, индексация которого начинается с 1. Необходимо перекрыть все операции, связанные с индексом. Внутри можно использовать ArrayList:

package ua.inf.iwanoff.collections;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

@SuppressWarnings("unchecked")
public class ArrayFromOne<E> extends AbstractList<E> {
    ArrayList<Object> arr = new ArrayList<>();

    @Override
    public E get(int index) {
        return (E)arr.get(index - 1);
    }

    @Override
    public int size() {
        return arr.size();
    }

    @Override
    public void add(int index, E element) {
        arr.add(index - 1, element);
    }

    @Override
    public boolean add(E e) {
        return arr.add(e);
    }

    @Override
    public E set(int index, E element) {
        return (E)arr.set(index - 1, element);
    }

    @Override
    public E remove(int index) {
        return (E)arr.remove(index - 1);
    }

    @Override
    public int indexOf(Object o) {
        return arr.indexOf(o) + 1;
    }

    @Override
    public int lastIndexOf(Object o) {
        return arr.lastIndexOf(o) + 1;
    }

    @Override
    public Iterator<E> iterator() {
        return (Iterator<E>)arr.iterator();
    }

    public static void main(String[] args) {
        ArrayFromOne<Integer> a = new ArrayFromOne<>();
        a.add(1);
        a.add(2);
        System.out.println(a.get(1) + " " + a.get(2)); // 1 2
        System.out.println(a.indexOf(2));              // 2
        a.set(1, 3);
        for (Integer k : a) {
            System.out.print(k + " ");                   // 3 2
        }
        System.out.println();
        a.remove(2);
        System.out.println(a);                         // [3]
        a.addAll(Arrays.asList(new Integer[]{ 4, 5 }));
        System.out.println(a.get(3));                  // 5
    }

}

Аннотация @SuppressWarnings("unchecked") перед классом нужна для подавления предупреждений, связанных с явным приведением типов.

3 Задания на самостоятельную работу

3.1 Реализация массива точек списком вещественных чисел

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

3.2 Слова в алфавитном порядке*

Ввести предложение и вывести все различные слова предложения в алфавитном порядке. Использовать множество.

3.3 Среднее арифметическое*

Реализовать программу, в которой вводятся вещественные числа, выводятся в порядке возрастания модулей, а также вычисляется их среднее арифметическое. Использовать PriorityQueue.

3.4 Буквы в обратном порядке

Ввести слово и вывести его буквы в обратном порядке. Использовать стек.

3.5 Проверка корректности скобок с учетом кавычек*

Дополнить пример 2.6 проверкой, не находятся ли скобки в кавычках. В этом случае они должны игнорироваться.

3.6 Данные о пользователях*

Представить данные о пользователях в виде ассоциативного массива (имя / пароль) с предположением, что все имена пользователей разные. Вывести данные о пользователях с длиной пароля более 6 символов.

3.7 Определение частоты вхождения букв*

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

3.8 Реализация двухсвязного списка*

Реализовать обобщенный класс, представляющий двусвязный список

3.9 Реализация функции удаления элемента из дерева*

Добавить к примеру 2.9 функцию удаления заданного элемента из дерева.

3.10 Реализация красно-черного дерева (задача повышенной трудности)

Самостоятельно реализовать ассоциативный массив на базе красно-черного дерева.

3.11 Создание собственного контейнера на базе массива*

Создать обобщенный класс для представления одномерного массива, индекс элементов которого меняется от определенного значения From до значения To включительно. Эти значения могут быть как положительными, так и отрицательными. Класс должен реализовывать интерфейс Collection. Рекомендуется использовать класс AbstractList в качестве базового.

3.12 "Гибкий" массив*

Создать обобщенный класс для представления одномерного массива, который автоматически расширяется, когда пользователь обращается к несуществующему элементу. Например, если создан пустой массив a, первое обращение (для чтения или записи) к элементу по индексу обеспечит расширение массива так, чтобы он содержал n + 1 элемент с индексами от 0 до n-го включительно. Если определенные элементы уже существовали, они сохраняются и массив дополняется новыми элементами. Если элемент с индексом уже существует, осуществляется обычное обращение.

Создать метод получения количества элементов, методы доступа по индексу, метод предоставления итератора, а также перекрыть функцию ToString(). Осуществить тестирование всех возможностей класса.

4 Контрольные вопросы

1. Что такое коллекция?
2. Почему в контейнерном классе нельзя хранить целые и действительные числа непосредственно, а можно только ссылки?
3. Как из массива получить список?
4. Как сохранить в списке целые и действительные значения?
5. Когда целесообразнее использовать ArrayList по сравнению с LinkedList?
6. Когда целесообразнее использовать LinkedList по сравнению с ArrayList?
7. В чем преимущество использования итераторов по сравнению с индексами элементов списка?
8. Какие базовые интерфейсы описаны в пакете java.util?
9. Какие контейнеры считаются устаревшими?
10. Какая структура данных используется для реализации LinkedList?
11. Чем множество отличается от списка?
12. Как определить очередь в широком и узком смысле?
13. Какие методы интерфейса Queue используются для добавления элементов?
14. С какой целью методы работы с очередью продублированы в двух вариантах - с генерацией исключения и без?
15. Для чего используется класс PriorityQueue?
16. Можно ли с помощью ArrayDeque реализовать очередь?
17. Для чего используются стеки?
18. Какие есть стандартные способы реализации стека?
19. Какие алгоритмы предоставляет класс Collections?
20. Чем множество отличается от ассоциативного массива?
21. Приведите примеры использования ассоциативных массивов.
22. В чем отличия интерфейсов Map и SortedMap?
23. Для чего используется класс Properties?
24. Что такое хеширование?
25. Как используются "корзины" для хранения данных в хеш-таблице?
26. Что такое двоичное дерево?
27. Что такое сбалансированное и несбалансированное дерево?
28. Что такое красно-черное дерево и какие у него преимущества?
29. Как создать собственный контейнер?
30. Как реализовать контейнер только для чтения?