�

Березнь, 2016

Лекція 9. Колекції

��

�

• Що таке Колекції?

​

• Колекції - це сховища або контейнери, групи елементів, які являють собою єдине ціле, які підтримують різні способи накопичення і впорядкування об'єктів з ціллю забезпечення ефективного доступу до них.

​

• Наприклад: банку цукерок, список імен і т.д.
• Колекції використовуються майже в кожній мові програмування і Java не є винятком. Як тільки колекції з'явилися в Java, то налічували всього кілька класів: Vector, Stack, Hashtable, Array. Але вже в Java 1.2 з'явився повноцінний Java Collections Framework, з яким ми і будемо сьогодні знайомитися.

�

Інтерфейси колекцій

У мові Java визначено декілька інтерфейсів, які визначають фундаментальну природу класів колекцій.

�

Інтерфейс Collection

Інтерфейс Collection – це узагальнений інтерфейс, який оголошується наступним чином:

​

interface Collection <E>

​

Елемент «Е» колекції вказує на тип об'єктів, які може містити колекція.

Інтерфейс Collection розширює інтерфейс Iterable. Це означає, що елементи колекцій, які реалізують інтерфейс Collection, можна перебирати за допомогою циклу for у стилі «for-each».

The List Interface

​

​

Інтерфейс List може містити дублікати елементів.

​

Додатково до методів Collection має

​

Позиційний доступ - маніпулює елементами, за їх позицією (індексом). Це включає в себе такі методи, як get, set, add, addAll, remove.

​

Пошук - шукає певний об'єкт у списку та повертає його позицію. Методи пошуку включають indexOf і lastIndexOf.

​

Ітерація - розширює семантику ітератора, щоб скористатися послідовним характером списку. Метод listIterator забезпечує таку поведінку.

Діапазонний вигляд – метод sublist операції довільного діапазону в списку.

Платформа Java містить такі

реалізації List: ArrayList і LinkedList.

​

ArrayList – найшвидший клас.

LinkedList – подвійно-зв’язаний список.

​

List strList = new ArrayList<>();

//добавити в кінець

strList.add(0, "0");

//добавити елемент в певне місце

strList.add(1, "1");

//замінити елемент

strList.set(1, "2");

//видалити елемент

strList.remove("1");

The Set Interface��

Інтерфейс Set містить лише методи, успадковані від Collection, і додає обмеження, що дублікати елементів заборонені.

Платформа Java містить три реалізації Set: HashSet, TreeSet і LinkedHashSet.

HashSet – найшвидший клас. Не гарантує порядок елементів.

TreeSet – найповільніший клас. Сортує елементи по значенню. LinkedHashSet – чуть повільніший за HashSet. Сортує елементи за порядком додавання.

Інтерфейс SortedSet

Інтерфейс SortedSet розширює інтерфейс Set і визначає поведінку наборів, відсортованих в порядку їх зростання. Інтерфейс SortedSet – це узагальнений інтерфейс, який оголошується наступним чином:

interface SortedSet <E>

Інтерфейс NavigableSet

Інтерфейс NavigableSet розширює інтерфейс SortedSet і визначає поведінку колекції, яка дозволяє витягувати елементи на основі найближчої відповідності заданому значенню або значенням.

interface NavigableSet <E>

�

Колекції Queue

Класи, що реалізують черги – перший зайшов, перший вийшов

LinkedList – стандартна реалізація PriorityQueue – об’єкт, що зберігає елементи сортовано

Створення об’єкта

Queue<String> queueA = new LinkedList<>(); Queue<String> queueB = new PriorityQueue<>();

Додавання та отримання елемента

public interface Queue<E> extends Collection<E> {

E element();

boolean offer(E e);

E peek();

E poll();

E remove(); }

�

Колекції Deque

Класи, що реалізують Deque

LinkedList – більш гнучкий, оскільки має методи List

ArrayDeque – більш ефективний для додавання та видалення елементів

ArrayDeque<String> aDeque = new ArrayDeque<>();

Класи колекцій

Самі по собі інтерфейси колекцій визначають тільки методи доступні із стандартних класів, що їх реалізують.

Деякі класи представляють повну реалізацію і можуть застосовуватися «як є». Інші є абстрактними, та представля-ють тільки шаблонні реалізації.

Класи колекцій (продовження)

Ієрархічні зв’язки між інтерфейсами та класами колекцій

Клас ArrayList

Клас ArrayList розширює клас AbstractList і реалізує інтерфейс List.

Клас ArrayList – це узагальнений клас, який оголошується наступним чином:

class ArrayList <Е>

import java.util.ArrayList;

 public class Main {

public static void main (String args[]) {

  // Створення масиву-списку

ArrayList<String> cars = new ArrayList<String>();

System.out.println("Початковий розмір cars: " + cars.size());

// Додавання елементів у масив-список

cars.add("Mercedes");

cars.add("Audi");

cars.add("BMW");

System.out.println("Розмір cars після додавання: " + cars.size());

// Відображення масиву-списку

System.out.println("Масив-список cars: " + cars);

// Видалення елементів із масиву-списку

cars.remove(“Audi");

cars.remove(1);

System.out.println ("Розмір cars після видалення: " + cars.size());

System.out.println("Масив-список cars: " + cars);

}}

void ensureCapacity(int розмір)

void trimToSize()

Клас ArrayList

Повернути всі елементи списку tоАггау(),

Існує дві версії методу tоАггау():

• Object[] toArray()
• <Т> Т[] toArray(Т масив[])

import java.util.ArrayList;

public class Main {

public static void main (String args[]) {

// Створення масиву-списку

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

// Додавання елементів у масив-список

al.add(1);

al.add(2);

al.add(3);

System.out.println("Масив-список al: " + al);

// Отримання масиву

Integer intarr[] = new Integer[al.size()];

intarr = al.toArray(intarr);

System.out.print("Елементи масиву: ");

for(int i=0; i<intarr.length; i++) {

System.out.print(intarr[i] + " ");

}

Масив-список al: [1, 2, 3]

Елементи масиву: 1 2 3

Клас LinkedList

Клас LinkedList розширює клас AbstractSequentalList і реалізує інтерфейси List, Deque та Queue. Він представляє структуру даних для реалізації зв'язного списку. Клас LinkedList – це узагальнений клас, який оголошується наступним чином:

class LinkedList <E>

import java.util.LinkedList;

public class Main {

public static void main (String args[]){

// Створення зв'язаного списку

LinkedList<String> cars = new LinkedList<String>();

// Додавання елементів у зв'язаний список

cars.add("Mercedes");

cars.add("Audi");

cars.add("BMW");

cars.addLast("Honda");

cars.addFirst("Ford");

cars.add(3, "Opel");

System.out.println("Зв'язаний список cars: " + cars);

// Видалення елементів із зв'язаного списку

cars.remove("Ford");

cars.remove(1);

System.out.println("Список cars після видалення: " + cars);

// Видалення першого і останнього елемента

cars.removeFirst();

cars.removeLast();

System.out.println("Список cars після видалення: "+ cars);

// Отримання і присвоєння значення

String str = cars.get(1);

cars.set(1, str + " модифіковано");

System.out.println("Список cars після модифікації: " + cars);}

Використання ітераторів для доступу до елементів колекції

Для перебору усіх елементів колекції або їх модифікації використовується ітератор, який є об'єктом, що реалізує один із двох інтерфейсів – Iterator або ListIterator.

• інтерфейс Iterator дає змогу організувати цикл для перебору колекції, із можливістю її модифікації;

• інтерфейс ListIterator розширює інтерфейс Iterator та забезпечує двонаправлений прохід по списку і модифікацією його елементів.

​

interface Iterator <E>

interface ListIterator <E>

​

Використання ітератора

У кожному класі колекцій визначено метод iterator(), який повертає ітератор на початок колекції. Перебір колекції за допомогою ітератора зводиться до виконання наступних дій:

• встановити ітератор на початок колекції, викликавши для цього метод iterator() доступний із класу, що реалізує колекцію;
• організувати цикл, який виконувати до тих пір, поки метод hasNext() повертає значення true;
• всередині циклу викликати метод next(), який дозволяє отримати поточне значення елемента колекції.

Для колекцій, що реалізують інтерфейс List, можна отримати ітератор, викликавши метод listIterator().

Приклад використання ітератора

ArrayList<String> cars = new ArrayList<String>();

. . .

// Використання ітераторів для масиву-списку

Iterator<String> itr = cars.iterator();

while(itr.hasNext()) {

String elem = itr.next();

System.out.print(" " + elem);

}

// Відображення масиву-списку у зворотному порядку

while(itr.hasPrevious()) {

String elem = itr.previous();

System.out.print(" " + elem);

}

Використання циклу for у стилі «for-each»

У випадку, якщо не має необхідності модифікувати вміст колекції або витягати елементи із неї у зворотному порядку, то для перебору елементів колекції можна використати версію циклу for у стилі «for-each».

Цикл for у стилі «for-each» може перебирати будь-яку колекцію об'єктів, що реалізовує інтерфейс Iterable.

ArrayList<String> cars = new ArrayList<String>();

. . .

for(String elem : cars) {

System.out.print(" " + elem);

}

�

• Лекція 9. Інтерфейси колекцій

​

Інтерфейс Ітератор (Iterator)

​

Колекції java.util.Collection розширює інтерфейс java.util.Iterable. Ітератор надає методи для перебору елементів будь-якої колекції. Ми можемо отримати екземпляр ітератора з колекції за допомогою методу iterator. Ітератори дозволяють видалити елементи з базової колекції під час виконання ітерації.

​

�

• Лекція 9. Інтерфейси колекцій

​

інтерфейс Map

​

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

​

Платформа Java містить три реалізації Map: HashMap, TreeMap і LinkedHashMap.

​

�

• Лекція 9. Інтерфейси колекцій

​

інтерфейс SortedSet

​

SortedSet це множина, в якій елементи зберігаються в порядку зростання.

​

інтерфейс SortedMap

​

SortedMap містить елементи в порядку зростання ключів. Ця Map є аналогом SortedSet. SortedMap використовуються для природно упорядкованих пар ключ / значення, наприклад, словників і довідників.

Лекція 9. Інтерфейси колекцій. Підсумок:

Основними інтерфейсами колекції і їх імплементаціями є:�Collection розширюють три інтерфейса List; Set; Queue.��List - зберігає впорядковані елементи (можуть бути однакові.) Має такі реалізації як ArrayList і LinkedList і Vector .�Vector - синхронізований, і тому в одному потоці, він працює повільніше від інших реалізацій.�ArrayList - аналог звичайного масиву, але з динамічно змінним розміром. Використовуйте, якщо потрібен доступ до елементу за індексом і додавання в кінець списку або видалення з кінця.�LinkedList - використовується, якщо необхідно додавання / видалення в довільному місці списку. Однак пошук повільніший, ніж в ArrayList.�� Set - колекції, які не містять повторюючих елементів.�Основні реалізації: HashSet, TreeSet і LinkedHashSet.�TreeSet - впорядковує елементи по їх значеннях,�HashSet - впорядковує елементи по їх хеш-ключах, хоча на перший погляд може здатися, що елементи зберігаються в випадковому порядку. �LinkedHashSet - зберігає елементи в порядку їх добавлення. Якщо такий елемент існує, це не змінює порядок.

Лекція 9. Інтерфейси колекцій. Підсумок:

Queue - інтерфейс для реалізації черги в джава.�Основні реалізації: LinkedList і PrioritiQueue�Черги працюють по принципу FIFO – first in first out��Map – інтерфейс для реалізації так названої карти, де елементи зберігаються з їх ключами.�Основні реалізації: HashTable, HashMap, TreeMap і LinkedHashMap.�HashTable - синхронізована, об'явлена як застаріла.�HashMap - порядок елементів розраховується по хеш ключу,�TreeMap - елементи зберігаються у відсортованому порядку�LinkedHashMap - елементи зберігаються в порядку вставки�Ключі в Map не можуть бути однаковими.�Синхронізувати несинхронізовані колекції і карти можна за допомогою класа Collections.synchronizedMap(MyMap)\synchronizedList(MyList)

• Лекція 9. Інтерфейси колекцій Отже: