Лабораторні роботи:

• 1 Робота з потоками введення-виведення
• 2 Робота з колекціями в Java
• 3 Робота з XML-документами
• 4 Створення програм графічного інтерфейсу користувача
• 5 Робота з графічними засобами JavaFX
• 6 Робота з потоками даних і потоками виконання у Java

 

Контрольні запитання з курсу

Лабораторна робота 2

Робота з колекціями в Java

1 Завдання на лабораторну роботу

1.1 Індивідуальне завдання

До ієрархії класів, створеної під час реалізації індивідуального завдання лабораторної роботи № 1 курсу "Об'єктно-орієнтоване програмування (перша частина)" додати похідні класи, які представляють першу з сутностей індивідуального завдання. Перший з них зберігає дані у за допомогою списку (ArrayList), другий за допомогою множини (SortedSet).

Для сортування списку скористатися засобами класу Collections. Працюючи з множиною, слід послідовно створювати варіанти множини, впорядковані за різними критеріями.

Здійснити тестування обох реалізацій. Результати виконання програм повинні збігатися.

1.2 Пошук різних слів у реченні

Увести речення, створити колекцію (SortedSet) різних слів речення та вивести ці слова в алфавітному порядку.

1.3 Середнє арифметичне

Реалізувати програму, в якій вводяться дійсні числа, виводяться в порядку зростання модулів, а також обчислюється їх середнє арифметичне. Використати PriorityQueue.

1.4 Дані про користувачів

Представити дані про користувачів у вигляді асоціативного масиву (ім'я / пароль) з припущенням, що всі імена користувачів різні. Вивести дані про користувачів з довжиною пароля більше 6 символів.

1.5 Створення власного контейнера на базі масиву

Створити узагальнений клас для представлення одновимірного масиву, індекс елементів якого змінюється від певного значення from до значення to включно. Ці значення можуть бути як додатними, так і від'ємними. Клас повинен реалізовувати інтерфейс Collection. Доцільно використати клас AbstractList як базовий.

1.6 Реалізація масиву точок за допомогою списку дійсних чисел (додаткове завдання)

Реалізувати функціональність абстрактного класу AbstractArrayOfPoints, наведеного в прикладі лабораторної роботи № 1 курсу "Об'єктно-орієнтоване програмування" (перша частина), через використання списку дійсних чисел. Кожна пара чисел у списку має відповідати точці.

1.7 Реалізація двобічно зв'язаного списку (додаткове завдання)

Реалізувати узагальнений клас, що представляє двобічно зв'язаний список.

1.8 Реалізація функції видалення елемента з дерева (додаткове завдання)

Додати до прикладу 3.8 функцію видалення заданого елемента з дерева.

1.9 Реалізація червоно-чорного дерева (завдання підвищеної складності, за вибором студента)

Самостійно реалізувати асоціативний масив на базі червоно-чорного дерева.

2 Методичні вказівки

2.1 Загальні відомості про контейнерні класи та інтерфейси

Засоби Java для роботи з колекціями надають уніфіковану архітектуру для представлення та управління наборами даних. Ця архітектура дозволяє працювати з колекціями незалежно від деталей їх внутрішньої організації. Засоби для роботи з колекціями включають більше десятка інтерфейсів, а також стандартні реалізації цих інтерфейсів і набір алгоритмів для роботи з ними.

Колекція – це об'єкт, який представляє групу об'єктів. Використання колекцій забезпечує підвищення ефективності програм завдяки використанню високоефективних алгоритмів, а також сприяє створенню коду, придатного для повторного використання. Основними елементами засобів роботи з колекціями є такі:

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

Крім того, Java 8 підтримує контейнери Java 1.1. Це Vector, Enumeration, Stack, BitSet і деякі інші. Наприклад, клас Vector надає функціональність, аналогічну ArrayList. Ці контейнери не забезпечують стандартизованого інтерфейсу, не дозволяють користувачеві відмовитися від надмірної синхронізації, яка актуальна лише в багатопотоковому оточенні, і отже, недостатньо ефективні. Внаслідок цього вони вважаються застарілими і не рекомендовані для використання. Замість них слід використовувати відповідні узагальнені контейнери Java 5.

Стандартні контейнерні класи Java дозволяють зберігати в колекції посилання на об'єкти, класи яких походять від класу Object. Контейнерні класи реалізовані в пакеті java.util. Починаючи з Java 5, усі контейнерні класи реалізовані як узагальнені. Java дозволяє створювати колекції без узагальнень, але такий підхід вважається застарілим і небажаним.

Існує два базових інтерфейси, в яких декларована функціональність контейнерних класів: Collection і Map. Інтерфейс Collection є базовим для інтерфейсів List (список), Set (множина), Queue (черга) і Deque (черга з двома кінцями).

Інтерфейс List (список) описує пронумеровану колекцію (послідовність), елементи якої можуть повторюватися.

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

Класи HashSet, LinkedHashSet і HashMap використовують для для ідентифікації елементів так звані хеш-коди. Хеш-код – це унікальна послідовність бітів фіксованої довжини. Для кожного об'єкта ця послідовність вважається унікальною. Хеш-коди забезпечують швидкий доступ до даних по деякому ключу. Механізм одержання хеш-кодів забезпечує їх майже повну унікальність. Усі об'єкти Java можуть генерувати хеш-коди: метод hashCode() визначений для класу Object.

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

2.2 Інтерфейс Collection

Інтерфейс Collection є базовим для багатьох інтерфейсів Collection Framework і оголошує найбільш загальні методи колекцій:

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

Наведений нижче приклад демонструє роботу методів інтерфейсу. В прикладі використовується клас ArrayList як найпростіша реалізація інтерфейсу Collection:

package ua.in.iwanoff.java.second;

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);             // []       
    }

}

2.3 Робота зі списками

Інтерфейс List описує упорядковану колекцію (послідовність). Цей інтерфейс реалізують стандартні класи ArrayList і LinkedList. Клас ArrayList реалізує список за допомогою масиву змінної довжини. Клас LinkedList зберігає об'єкти за допомогою так званого зв'язаного списку.

Існує також стандартна абстрактна реалізація списку – клас AbstractList. Цей клас, похідний від AbstractCollection, надає ряд корисних засобів. Практично в тій чи іншій формі реалізовані всі методи, крім get() і size(). Проте, для конкретної реалізації списку більшість функцій слід перекрити. Клас AbstractList – базовий для ArrayList. Класс AbstractSequentialList, похідний від AbstractList, є базовим для класу LinkedList.

Створити порожній список посилань на об'єкти деякого типу (SomeType) можна за допомогою конструктора за умовчанням:

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

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

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

Другий варіант іноді не є бажаним, оскільки в такому випадку знижується гнучкість програми. Перший варіант дозволить легко замінити реалізацію списку ArrayList на будь-яку іншу реалізацію інтерфейсу List, яка більше відповідає вимогам конкретної задачі. У другому випадку є спокуса викликати методи, специфічні для ArrayList, тому перехід на іншу реалізацію буде ускладнено.

Створивши порожній список, у нього можна додавати елементи за допомогою функції add(). Метод add() з одним аргументом типу-посилання додає елемент у кінець списку. Якщо ця функція викликається з двома аргументами, новий елемент вставляється в список у позиції, зазначеній першим параметром:

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

До списку можна додати всі елементи іншого списку (або іншої колекції) за допомогою функції addAll().

Можна створити новий список із використанням існуючого. Новий список містить посилання на копії елементів. наприклад:

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() і set(). Метод get() класу ArrayList повертає елемент із зазначеним індексом (позиція в списку). Як і елементи масивів, елементи списків пронумеровані з нуля. У наступному прикладі рядки виводяться за допомогою функції 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));
}

Метод set() дозволяє змінити об'єкт, що зберігається в зазначеній позиції. Метод remove() видаляє об'єкт у зазначеній позиції:

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

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

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

Метод removeRange(m, n) видаляє всі елементи, індекс яких між m включно та не включаючи n. Усі елементи колекцій віддаляються за допомогою методу clear(). Функція 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 відповідно.

У тих випадках, коли частіше, ніж вибір довільного елемента, застосовують операції додавання і видалення елементів у довільних місцях, доцільно використовувати клас LinkedList, що зберігає об'єкти за допомогою зв'язаного списку. Зв'язний список, реалізований у Java контейнером 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 із застосуванням масивів.

2.4 Ітератори

Для проходження по колекції (списку) об'єктів використовується ітератор – спеціальний допоміжний об'єкт. Як і самі контейнери, ітератори базуються на інтерфейсі. Інтерфейс Іterator, визначений у пакеті java.utіl. Будь-який ітератор має три методи:

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 (for each) дозволяє обійти список без явного створення ітератору:

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.in.iwanoff.java.second;

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");
        }
    }

}

2.5 Робота з множинами

Множина – це колекція, що не містить однакових елементів. Три основних реалізації інтерфейсу 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.in.iwanoff.java.second;

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) {
    . . .
}

Можна створити масив, який містить копії елементів множини. В такий спосіб можна звертатися до елементів за індексом. Наприклад, так можна вивести елементи множини в зворотному порядку:

Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 4));
Object[] arr = set.toArray();
for (int i = set.size() - 1; i >= 0; i--) {
    System.out.println(arr[i]);
}

Оскільки множина може містити тільки різні елементи, її можна використати для підрахунку різних слів, літер, цифр тощо – створюється множина та викликається метод size(). Застосовуючи TreeSet, можна виводити слова та літери в алфавітному порядку. У наступному прикладі вводиться речення та виводяться всі різні літери речення (не враховуючи роздільників) в алфавітному порядку:

package ua.in.iwanoff.java.second;

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);
    }
  
}

Порядок сортування елементів TreeSet можна задати, реалізувавши інтерфейс Comparable, або передавши в конструктор TreeSet посилання на об'єкт класу, який реалізує інтерфейс Comparator. Наприклад, так можна відсортувати дерево у зворотному порядку:

package ua.in.iwanoff.java.second;

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 + " ");
        }
    }
}

Примітка. У наведеному вище прикладі для визначення порядку елементів застосовано безіменний клас. Використання безіменних класів, лямбда-виразів і посилань на методи описано в методичних вказівках до лабораторної роботи № 3 курсу "Об'єктно-орієнтоване програмування".

2.6 Робота з чергами та стеками

Черга в широкому сенсі є структурою даних, яку заповнюють поелементно, та отримують з неї об'єкти за певним правилом. У вузькому сенсі цим правилом є "першим прийшов – першим вийшов" (FIFO, First In – First Out). У черзі, організованій за принципом FIFO, додавання елемента можливо лише в кінець черги, отримання – тільки з початку черги.

У бібліотеці контейнерів черга представлена інтерфейсом Queue. Методи, оголошені в цьому інтерфейсі, наведені в таблиці:

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

Для реалізації черги найзручніше використовувати клас LinkedList, який реалізує інтерфейс Queue. Наприклад:

package ua.in.iwanoff.java.second;

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.in.iwanoff.java.second;

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.in.iwanoff.java.second;

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.in.iwanoff.java.second;

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
        }
    }

}

Стеки часто використовуються в різних алгоритмах. Зокрема, за допомогою стеку часто можна позбутися рекурсії.

2.7 Статичні методи класу Collections. Алгоритми

2.7.1 Створення спеціальних контейнерів з використанням класу Collections

Як клас Arrays для масивів, для колекцій існує допоміжний клас Collections. Цей клас надає низку функцій для роботи з колекціями, зокрема зі списками. Велика група функцій призначена для створення колекцій різних типів. Наведений нижче приклад демонструє створення колекцій за допомогою статичних методів класу Collections: відповідно, порожнього списку (emptyList()), "одинака" (singletonList()) і списку тільки для читання зі звичайного (unmodifiableList()) або колекції тільки для читання (unmodifiableCollection()):

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().

2.7.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()) і т. д.

2.8 Асоціативні контейнери

Асоціативні масиви можуть зберігати пари посилань на об'єкти. Асоціативні масиви теж є узагальненими типами. Асоціативні масиви у 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 гарантує алфавітний порядок слів (ключів).

package ua.in.iwanoff.java.second;

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.in.iwanoff.java.second;

import java.util.*;

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

    public String getName() {
        return name;
    }

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

    @Override
    public int compareTo(TreeMapKey o) {
        return name.substring(o.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();
    }

}

Клас Hashtable – одна з реалізацій інтерфейсу Map. Hashtable крім розміру має ємність (розмір буфера, виділеного під елементи масиву). Крім цього він характеризується показником завантаженості – часткою буфера, після заповнення якої ємність автоматично збільшується. Конструктор Hashtable() без параметрів створює порожній об'єкт з ємністю в 101 елемент і показником завантаженості 0.75.

Клас Properties, похідний від Hashtable, замість пар довільних об'єктів зберігає пари рядків. Якщо в конкретній задачі і ключі і значення елементів асоціативного масиву мають тип String, зручніше скористатися класом Properties. У класі Properties визначені методи getProperty(String key) і setProperty(String key, String value).

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

2.9.1 Реалізація множин та асоціативних контейнерів з використанням хешування

Для зберігання даних в HashSet і HashMap використовують так зване хешування. Хешування (hashing) – це процес отримання з даних про об'єкт унікального коду з використанням деякого формального алгоритму. У широкому сенсі результатом є послідовність біт фіксованої довжини, в окремому випадку – просто ціле число. Це перетворення здійснює так звана хеш-функція, або функція хешування. Функція хешування повинна відповідати такій вимозі: хеш-функція повинна повертати однаковий хеш-код кожного разу, коли вона застосована до однакових або рівних об'єктів.

Всі об'єкти в Java успадковують стандартну реалізацію hashCode() функції, описаної в класі Object. Ця функція повертає хеш-код, отриманий шляхом конвертації внутрішньої адреси об'єкта в число, що забезпечує створення унікального коду для кожного окремого об'єкта.

Конкретні стандартні класи реалізують свої хеш-функції. Наприклад, для рядків значення хеш-функції обчислюється за формулою:

s[0]*31n-1 + s[1]*31n-2 + ... + s[n-1]

Тут s[0], s[1] і т.д. – коди відповідних символів.

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

Організація зберігання даних в класах 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). Під час додавання нової пари ключ-значення, за хеш-кодом ключа обчислюється номер кошику (номер комірки масиву), в яку потрапить новий елемент. При цьому здійснюється проекція значення хеш-коду на масив з урахуванням його реальних розмірів. Якщо кошик порожній, то в ньому зберігається посилання на доданий елемент, якщо ж там уже є елемент, то відбувається послідовний перехід за посиланнями по елементах ланцюжка в пошуках останнього елемента, в якому записується посилання на доданий елемент. Якщо в списку був знайдений елемент з таким же ключем, то значення замінюється.

Ефективність операцій додавання, пошуку і видалення залежить від реалізації хеш-функції. Якщо вона видає постійне значення, контейнер перетворюється в зв'язаний список з низькою ефективністю.

2.9.2 Реалізація контейнерів на базі бінарних дерев

Бінарне дерево являє собою деревоподібну структуру даних (граф без циклів), в якій кожна вершина (вузол) має не більше двох нащадків (спадкоємців). Їх називають відповідно лівим і правим спадкоємцем. У свою чергу, вони можуть виступати як вершини піддерев. Можна говорити про ліве та праве піддерево.

Бінарне дерево може бути використано для упорядкованого за певною ознакою зберігання об'єктів (впорядкування за ключем). У цьому випадку говорять про так зване бінарне дерево пошуку, що задовольняє таким правилам:

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

Зазвичай для бінарних дерев пошуку реалізують такі основні операції:

• додавання елемента
• отримання (пошук) елемента
• видалення елемента (вузла)
• обхід дерева

Бінарне дерево має назву ідеально збалансованого, якщо для кожної його вершини кількість вершин в лівому і правому піддереві розрізняються не більше ніж на 1. У незбалансованого дерева це правило не дотримується. Найпростіша реалізація дерева дає незбалансоване дерево. Залежно від порядку додавання елементів дерево може бути збалансованим або зовсім незбалансованим. Припустимо, бінарне дерево зберігає цілі значення. Якщо числа від 1 до 7 додавати в певному порядку (наприклад, 4, 2, 3, 1, 6, 7, 5), може вийти ідеально збалансоване дерево:

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

Можна казати про різний степінь збалансованості. Незбалансованість знижує продуктивність під час пошуку елемента. Разом з тим, створення ідеально збалансованих дерев обумовлює обчислювальні труднощі під час додавання і видалення. У реальній практиці найчастіше використовують частково збалансовані дерева.

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

• Корінь дерева повинен бути чорним
• Всі листові вузли – чорні
• Обидва нащадка кожного червоного вузла – чорні
• Кожен простий шлях від цього вузла до будь-якого листового вузла, що є його нащадком, містить однакове число чорних вузлів

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

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

2.10 Створення власних контейнерів

Незважаючи на велику кількість стандартних контейнерних класів, іноді виникає потреба в створенні власних контейнерів. Це можуть бути, наприклад, складні дерева, більш гнучкі списки, спеціалізовані колекції елементів і т.д.

У деяких випадках необхідно тільки обходити елементи деякої послідовності за допомогою альтернативної форми циклу for. Для цього достатньо реалізувати інтерфейс Iterable<>. Він вимагає реалізації функції, що повертає ітератор. Найчастіше для реалізації ітератора створюють внутрішній нестатичних клас. У наведеному нижче прикладі створюється клас "речення" з ітератором, який переміщається по окремих словах. Програма виводить слова введеного речення в окремих рядках:

package ua.in.iwanoff.java.second;

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();
    }

    @SuppressWarnings("resource")
    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.in.iwanoff.java.second;

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"
    }
}

Для того щоб реалізувати контейнер для читання і запису, необхідно перекрити відповідні методи. У прикладі 3.9 реалізований відповідний контейнер.

3 Приклади програм

3.1 Сума елементів типу Double

Наведена нижче програма читає дійсні числа, які вводить користувач, заносить їх у список та знаходить суму.

package ua.in.iwanoff.java.second;

import java.util.*;

public class SumOfElements {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Double> a = new ArrayList<>();
        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.

3.2 Індекс максимального елементу

Наведена нижче програма знаходить номер максимального елемента в списку цілих чисел. Для заповнення списку можна використати масив з початковими значеннями елементів. Масив неявно створюється під час виконання функції asList().

package ua.in.iwanoff.java.second;

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));
    }

}

Оскільки шукаємо індекс, не доцільно застосовувати ітератор.

3.3 Дані про країни в асоціативному масиві

Дані про країни (назва і територія) можна зберігати в асоціативному масиві. Виведення здійснюється за алфавітом країн:

package ua.in.iwanoff.java.second;

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());  
    }

}

3.4 Реалізація класу для представлення масиву точок за допомогою списку

Ще одна можлива реалізація представлення масиву точок, визначеного в прикладі до лабораторної роботи № 1 з курсу "Об'єктно-орієнтоване програмування", заснована на використанні списку точок. У проекті, що містить клас AbstractArrayOfPoints, створюємо новий пакет і в ньому - клас ListOfPointObjects. Для забезпечення можливості використання класів AbstractArrayOfPoints і Point додаємо відповідні твердження імпорту.

Вихідний код класу матиме такий вигляд:

package ua.in.iwanoff.java.second;

import java.util.ArrayList;
import ua.in.iwanoff.oop.first.AbstractArrayOfPoints;
import ua.in.iwanoff.oop.first.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();
    }
}

Результати повинні бути ідентичними отриманим раніше.

3.5 Літери речення в алфавітному порядку

У наведеному нижче прикладі вводиться речення і виводяться всі різні літери речення (за винятком роздільників) в алфавітному порядку:

package ua.in.iwanoff.java.second;

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);
    }
  
}

3.6 Добуток чисел, що вводяться

У наведеному нижче прикладі вводяться цілі числа, виводяться за зменшенням, а також обчислюється їх добуток. Введення завершується нулем:

package ua.in.iwanoff.java.second;

import java.util.*;

public class Product {

    @SuppressWarnings("resource")
    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);
    }

}

3.7 Створення однобічно зв'язаного списку

У наведеному нижче прикладі створюється і заповнюється однобічно зв'язаний список:

package ua.in.iwanoff.java.second;

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);
    }
}

3.8 Створення бінарного дерева

У наведеному нижче прикладі створюється і заповнюється звичайне (незбалансоване) бінарне дерево, що містить пари ціле / рядок:

package ua.in.iwanoff.java.second;

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));
    }
}

3.9 Створення власного контейнера на базі списку ArrayList

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

package ua.in.iwanoff.java.second;

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.10 Зберігання даних про переписи у списку і множині

Припустимо, необхідно створити класи для роботи з переписами. Перший з них зберігатиме дані у за допомогою списку, другий за допомогою множини. Можна додати такі класи до попередньо створеної ієрархії. Перший клас зберігатиме дані в списку. Для сортування доцільно використати метод sort() класу Collections. Код класу буде таким:

package ua.in.iwanoff.java.second;

import ua.in.iwanoff.oop.first.AbstractCensus;
import ua.in.iwanoff.oop.first.AbstractCountry;
import ua.in.iwanoff.oop.first.CensusWithData;
import ua.in.iwanoff.oop.first.CompareByComments;

import java.util.*;

public class CountryWithList extends AbstractCountry {
    private String name;
    private double area;
    private List<AbstractCensus> list = new ArrayList<>();

    @Override
    public String getName() {
        return name;
    }

    @Override
    public void setName(String name) {
        this.name = name;
    }

    @Override
    public double getArea() {
        return area;
    }

    @Override
    public void setArea(double area) {
        this.area = area;
    }

    @Override
    public AbstractCensus getCensus(int i) {
        return list.get(i);
    }

    @Override
    public void setCensus(int i, AbstractCensus census) {
        list.set(i, census);
    }

    @Override
    public boolean addCensus(AbstractCensus census) {
        return list.add(census);
    }

    @Override
    public boolean addCensus(int year, int population, String comments) {
        return list.add(new CensusWithData(year, population, comments));
    }

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

    @Override
    public void clearCensuses() {
        list.clear();
    }

    @Override
    public void sortByPopulation() {
        Collections.sort(list);
    }

    @Override
    public void sortByComments() {
        Collections.sort(list, new CompareByComments());
    }

    @Override
    public void setCensuses(AbstractCensus[] censuses) {
        list = new ArrayList<>(Arrays.asList(censuses));
    }

    @Override public AbstractCensus[] getCensuses() {
        return list.toArray(new AbstractCensus[0]);
    }

    public static void main(String[] args) {
        new CountryWithList().createCountry().testCountry();
    }
}

Тепер можна створити клас, який забезпечує зберігання даних у множині. Оскільки множина одразу впорядкована за певною ознакою і здійснити її сортування немає можливості, для отримання відсортованих послідовностей можна створювати різні варіанти наборів даних.

Від початку переписи повинні бути розташовані за зростанням року. Тому слід створити окремий клас для відповідного порівняння:

package ua.in.iwanoff.java.second;

import ua.in.iwanoff.oop.first.AbstractCensus;
import java.util.Comparator;

public class CompareByYear implements Comparator<AbstractCensus> {

    public int compare(AbstractCensus c1, AbstractCensus c2) {
        return Integer.compare(c1.getYear(), c2.getYear());
    }

}

Код класу CountryWithSet буде таким:

package ua.in.iwanoff.java.second;

import ua.in.iwanoff.oop.first.AbstractCensus;
import ua.in.iwanoff.oop.first.AbstractCountry;
import ua.in.iwanoff.oop.first.CensusWithData;
import ua.in.iwanoff.oop.first.CompareByComments;

import java.util.Arrays;
import java.util.SortedSet;
import java.util.TreeSet;

public class CountryWithSet extends AbstractCountry {
    private String name;
    private double area;
    private SortedSet<AbstractCensus> set = new TreeSet<>(new CompareByYear());

    @Override
    public String getName() {
        return name;
    }

    @Override
    public void setName(String name) {
        this.name = name;
    }

    @Override
    public double getArea() {
        return area;
    }

    @Override
    public void setArea(double area) {
        this.area = area;
    }

    @Override
    public AbstractCensus getCensus(int i) {
        return set.toArray(new AbstractCensus[0])[i];
    }

    @Override
    public void setCensus(int i, AbstractCensus census) {
        AbstractCensus oldCensus = getCensus(i);
        set.remove(oldCensus);
        set.add(census);
    }

    @Override
    public boolean addCensus(AbstractCensus census) {
        return set.add(census);
    }

    @Override
    public boolean addCensus(int year, int population, String comments) {
        return set.add(new CensusWithData(year, population, comments));
    }

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

    @Override
    public void clearCensuses() {
        set.clear();
    }

    @Override
    public void sortByPopulation() {
        SortedSet<AbstractCensus> newSet = new TreeSet<>();
        newSet.addAll(set);
        set = newSet;
    }

    @Override
    public void sortByComments() {
        SortedSet<AbstractCensus> newSet = new TreeSet<>(new CompareByComments());
        newSet.addAll(set);
        set = newSet;
    }

    @Override
    public void setCensuses(AbstractCensus[] censuses) {
        set = new TreeSet<>(new CompareByYear());
        set.addAll(Arrays.asList(censuses));
    }

    @Override
    public AbstractCensus[] getCensuses() {
        return set.toArray(new AbstractCensus[0]);
    }

    public static void main(String[] args) {
        new CountryWithSet().createCountry().testCountry();
    }
}

Результати роботи програм повинні бути ідентичними.

4 Вправи для контролю

1. Прочитати з клавіатури значення елементів списку цілих чисел. Знайти добуток елементів.
2. Проініціалізувати список дійсних чисел масивом зі списком початкових значень. Знайти суму додатних елементів.
3. Проініціалізувати список цілих чисел масивом зі списком початкових значень. Знайти добуток ненульових елементів.
4. Проініціалізувати список цілих чисел масивом зі списком початкових значень. Створити новий список, складений з парних елементів вихідного списку.
5. Проініціалізувати список дійсних чисел масивом зі списком початкових значень. Створити новий список, складений з додатних елементів вихідного списку.
6. Проініціалізувати список рядків масивом зі списком початкових значень. Знайти та вивести рядок з найбільшою довжиною.
7. Проініціалізувати список рядків масивом зі списком початкових значень. Знайти та вивести індекс рядка з найменшою довжиною.
8. Увести кількість елементів майбутньої множини цілих чисел та діапазон чисел. Сформувати цю множину з випадкових значень. Вивести елементи множини, відсортовані за збільшенням.
9. Увести кількість елементів майбутньої множини дійсних чисел та діапазон чисел. Сформувати цю множину з випадкових значень. Вивести елементи множини у порядку зменшення.
10. Заповнити множину цілих випадковими додатними парними значеннями (не більше визначеного числа). Вивести результат.
11. Увести слово та вивести всі різні літери слова в алфавітному порядку.
12. Увести речення та обчислити кількість різних літер, з яких речення складається. Не враховувати пропусків та розділових знаків.
13. Увести речення та обчислити кількість різних слів у реченні.
14. Проініціалізувати список цілих чисел масивом зі списком початкових значень. Знайти суму максимального і мінімального елементів. Застосувати функції класу Collections.
15. Проініціалізувати список рядків масивом зі списком початкових значень. Змінити порядок елементів на зворотний. Застосувати функцію класу Collections.

5 Контрольні запитання

1. Що таке колекція?
2. Які базові інтерфейси описані в пакеті java.util?
3. Які контейнери вважають застарілими?
4. Чому в колекції не можна зберігати цілі і дійсні числа безпосередньо, а можна тільки посилання?
5. Як з масиву отримати список?
6. Як зберегти у списку цілі і дійсні значення?
7. У чому перевага опису посилання на інтерфейс контейнера (наприклад, List) у порівнянні з описом посилання на клас, що реалізує контейнер (наприклад, ArrayList)?
8. У чому перевага використання ітераторів у порівнянні з індексами елементів контейнера?
9. Коли доцільніше використовувати ArrayList у порівнянні з LinkedList?
10. Коли доцільніше використовувати LinkedList у порівнянні з ArrayList?
11. Яку структуру даних використовують для реалізації LinkedList?
12. Які методи інтерфейсу Queue використовують для додавання елементів?
13. З якою метою методи роботи з чергою реалізовані в двох варіантах – з генерацією винятку і без?
14. Для чого використовують клас PriorityQueue?
15. Чи можна за допомогою ArrayDeque реалізувати чергу?
16. Для чого використовують стеки?
17. Які є стандартні способи реалізації стеку?
18. Які алгоритми надає клас Collections?
19. Чим множина відрізняється від списку?
20. Наведіть приклади використання асоціативних масивів.
21. У чому відміни інтерфейсів Map та SortedMap?
22. Що таке хешування?
23. Як використовують "кошики" для зберігання даних в хеш-таблиці?
24. Що таке бінарне дерево?
25. Що таке збалансоване і незбалансоване дерево?
26. Що таке червоно-чорне дерево і які у нього переваги?
27. Як створити власний контейнер?
28. Як реалізувати контейнер тільки для читання?