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

1. Список колекцій

Як ти можеш пам’ятати, Java має зручний інструмент для зберігання об’єктів однакових типів – колекції.

Спробуймо згадати основні інтерфейси колекцій:

List, Set, Map и Queue.

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

1. List

Давай почнемо з найчастіше використовуваної колекції.

List максимально схожий на звичайнісінький масив. Назва ж нам говорить про те, що це список (list).

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

2. Set

Set (множина) має зовсім іншу структуру.

Насамперед, Set варто використовувати, коли нам потрібно зберігати унікальні об’єкти. Припустимо, це набір авторів у бібліотеці, де кожен автор унікальний. Але ми не можемо просто так звернутися до нашого набору авторів і дістати з нього конкретного автора. Функціонал Set-а дає нам можливість швидко перевірити, чи представлений конкретний автор у нашій бібліотеці, наприклад, перевірити його наявність у колекції Set. Також є можливість пройтися всією колекцією, кожним елементом, але це не оптимально.

Тобто в нашій бібліотеці Set може бути чимось на кшталт набору всіх авторів для швидкої перевірки, чи представлений цей автор у бібліотеці.

3. Map

Map (словник) більше схожа на картотеку, де кожна комірка підписана, і в ній ми можемо зберігати як окремі об’єкти, так і цілі структури. Map варто використовувати у випадках, коли потрібно зберегти відповідність одного значення до іншого.

У Map це називається відповідність ключ-значення.

З такою структурою в нашій бібліотеці ми зможемо використовувати об’єкт автора як ключ, а список (List) книг – як значення. Отже, перевіривши в Set наявність автора в бібліотеці, ми зможемо по цьому самому об’єкту автора дістати List із його книгами з Map.

4. Queue

Queue (черга) – є колекцією, яка побудована як черга. Причому ця черга може бути не лише LIFO (Last In First Out – останній зайшов, перший вийшов), а й FIFO (First In First Out – перший зайшов, перший вийшов). А ще черга може бути двоспрямованою з виходами з обох боків.

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

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

Як ми з тобою можемо бачити, всі структури гарні, якщо використовувати їх за призначенням. І в межах одного прикладу, бібліотеки, ми використовували всі чотири типи колекцій.

2. Складність

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

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

Найчастіше, обираючи той чи інший інструмент, ми дивимося на 2 показники:

• наскільки цей інструмент підходить під завдання
• наскільки швидко відбуватиметься робота з ним

Якщо з вибором інструменту, що підходить під завдання, ми абияк розібралися, то швидкість його роботи – це щось новеньке.

Показник швидкості роботи часто виражають через тимчасову складність і позначають великою літерою О.

Що взагалі таке ця тимчасова складність?

Простими словами, ця складність вказує на час відпрацювання алгоритму, закладеного в колекцію для тієї чи іншої дії (додавання, видалення елемента, пошук).

ArrayList vs LinkedList

Давай розглянемо це на прикладі двох реалізацій інтерфейсу List — ArrayList i LinkedList.

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

Зовні робота із цими колекціями схожа:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

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

Завдяки різній реалізації інтерфейсу List ці дві структури мають різну ефективність за різного використання.

Розглянемо приклад операції видалення та додавання елемента.

Якщо нам потрібно буде видалити елемент із середини списку ArrayList, щоразу ми будемо переписувати решту списку, що йде за елементом, який ми видаляємо.

Припустимо, у нас є список із 5-ти елементів і нам потрібно видалити 3-й.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

У такому разі після видалення у нас звільниться одна комірка, і ми будемо змушені перезаписати 4-й елемент на місце 3-го, а 5-й – на місце 4-го.

Це максимально неефективно.

Те саме відбуватиметься і у разі додавання елемента в середину списку.

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

На прикладі того самого списку з 5-ти елементів, видаливши з нього 3-й, ми повинні просто змінити посилання на наступний елемент у 2-му та посилання на попередній у 4-му елементі.

Те саме, тільки навпаки, відбувається у разі додавання елемента до списку.

Зверніть увагу, наскільки менше дій нам необхідно виконати в LinkedList порівняно з ArrayList. А це тільки 5 елементів. Якби у списку було 100 і більше елементів, перевага LinkedList була б більш відчутною.

Але як зміниться ситуація, якщо ми звертатимемося до елемента за індексом?

Тут все буде рівно навпаки.

Оскільки ArrayList влаштований як звичайний масив, нам буде просто взяти будь-який елемент за його індексом. Ми просто перемістимо вказівник на певне місце і візьмемо з комірки елемент.

Але в LinkedList так просто не вийде. Нам доведеться пройтися всіма елементами масиву, щоб знайти елементи з певним індексом. Тільки в цьому випадку є сенс називати це не індекс, а порядковий номер.

Давай спробуємо виразити це все через велику О?

Почнемо зі звернення до елемента за індексом.

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

Тимчасова складність у цьому випадку буде О(1).

У LinkedList нам доведеться перебрати ту кількість елементів, індекс якого нам потрібний.

Тимчасова складність для такої дії буде О(n), де n – це індекс елемента, який нам потрібний.

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

Повернемося до видалення та додавання?

Почнемо з LinkedList.

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

Складність цієї самої операції для ArrayList буде вже О(n) і називається лінійною.

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

Складність ще буває логарифмічною. Виглядає вона так — O(log n).

Як приклад можемо розглянути відсортований TreeSet список із 10-ти чисел, у якому нам потрібно знайти число 2.

Оскільки список відсортований і в ньому немає дублікатів, ми можемо розділити його навпіл і перевірити, в якій частині списку залишилася шукане число, відкинути одну з частин і повторити дії знову, поки не дійдемо до шуканого елемента. У підсумку ми знайдемо число, обробивши log(n) кількість елементів.

Давай поглянемо на таблицю, в якій описані складності інших колекцій.

Тепер, коли у нас із тобою є таблиця, в якій зазначена тимчасова складність для популярних колекцій, ми можемо відповісти на запитання, чому з такої кількості колекцій ми найчастіше використовуємо ArrayList, HashSet i HashMap.

Вони просто максимально ефективні для більшості завдань:)