LinkedList

Привіт! Усі останні лекції були присвячені вивченню списку ArrayList. Ця структура даних дуже зручна і дає змогу вирішувати безліч завдань. Однак у Java є безліч інших структур даних. Чому? Насамперед тому, що коло наявних завдань дуже широке, і для різних завдань найефективнішими є різні структури даних. Сьогодні ми познайомимося з новою структурою – двобічно зв'язаним списком LinkedList. Давай розберемося, як він влаштований, чому називається двобічно зв'язаним і які його відмінності від ArrayList. У LinkedList елементи фактично являють собою ланки одного ланцюга. У кожного елемента крім тих даних, які він зберігає, є посилання на попередній і наступний елемент. За цими посиланнями можна переходити від одного елемента до іншого. Створюється він так:

public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Kyiv");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Виведення: Ось так виглядатиме будова нашого списку: Давай подивимося, як відбувається додавання нового елемента. Це робиться за допомогою методу add().

earlBio.add(str2);

На момент цього рядка коду наш список складається з одного елемента – рядка str1. Подивимося, що відбувається далі на малюнку: В результаті str2 і str1 стають пов'язаними через посилання next і previous, що зберігаються в них: Тепер тобі має стати зрозумілою головна ідея двобічно зв'язаного списку. Елементи LinkedList є єдиним списком саме завдяки ось цьому ланцюжку посилань. Усередині LinkedList немає масиву, як в ArrayList, або чогось схожого. Вся робота з ArrayList (здебільшого) зводиться до роботи з внутрішнім масивом. Вся робота з LinkedList зводиться до зміни посилань. Це дуже добре видно на прикладі додавання елемента в середину списку:

public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Kyiv");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

Як бачиш, перевантажений метод add() дає змогу вказати конкретний індекс для нового елемента. У цьому випадку ми хочемо додати рядок str2 між str1 і str3. Ось що відбуватиметься всередині: І в результаті зміни внутрішніх посилань елемент str2 успішно додано до списку: Тепер усі 3 елементи пов'язані. Від першого елемента ланцюжком next можна дійти останнього і навпаки. Зі вставкою ми більш-менш розібралися, а що з видаленням елементів? Принцип роботи той самий. Ми просто перевизначаємо посилання у двох елементів "з боків" від того, що видаляється:

public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Kyiv");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

Ось що відбуватиметься, якщо ми видалимо елемент з індексом 1 (він розташований всередині списку): Після перевизначення посилань ми отримуємо потрібний результат: На відміну від видалення в ArrayList тут немає жодних зсувів елементів масиву тощо. Ми просто перевизначаємо посилання в елементів str1 і str3. Тепер вони вказують один на одного, а об'єкт str2 "випав" з цього ланцюжка посилань, і більше не є частиною списку.

Огляд методів

LinkedList має багато спільних з ArrayList методів. Наприклад, такі методи як add(), remove(), indexOf(), clear(), contains() (чи міститься елемент у списку), set() (вставка елемента із заміною) і size() є в обох класах. Хоча (як ми з'ясували на прикладі add() і remove()) усередині багато які з них працюють інакше, але в кінцевому підсумку вони роблять те ж саме. Однак у LinkedList є окремі методи для роботи з початком і кінцем списку, яких немає в ArrayList:

• addFirst(), addLast(): методи для додавання елемента в початок/кінець списку

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

Виведення: У підсумку "Форд" опинився на початку списку, а "Фіат" – наприкінці.

• peekFirst(), peekLast(): повертають перший/останній елемент списку. Повертають null, якщо список порожній.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

Виведення:

• pollFirst(), pollLast(): повертають перший/останній елемент списку і видаляють його зі списку. Повертають null, якщо список порожній

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println("Що залишилося у списку?");
   System.out.println(cars);
}

Виведення:

• toArray(): повертає масив з елементів списку

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

Виведення: Тепер ми знаємо, як влаштований LinkedList і чим він відрізняється від ArrayList. У чому ж полягають вигоди від використання LinkedList? Насамперед, у роботі з серединою списку. Вставка і видалення в середину LinkedList влаштовані набагато простіше, ніж в ArrayList. Ми просто перевизначаємо посилання сусідніх елементів, а непотрібний елемент "випадає" з ланцюжка посилань. У той час як в ArrayList ми:

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

Тобто, якщо у твоїй програмі частіше відбуваються операції вставки/видалення з серединою списку, LinkedList має бути швидшим за ArrayList.

Теоретично

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start=System.currentTimeMillis();

       for(int i=0;i<100;i++){
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Час роботи для LinkedList (у мілісекундах) = " + (System.currentTimeMillis()-start));
   }
}

Виведення:

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start=System.currentTimeMillis();

       for (int i=0;i<100;i++){
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Час роботи для ArrayList (у мілісекундах) = " + (System.currentTimeMillis()-start));
   }
}

Виведення: Несподівано! Здавалося б, ми проводили операцію, де LinkedList має бути набагато ефективнішим – вставку 100 елементів у середину списку. Та й список у нас величезний – 5000000 елементів: ArrayList'у доводилося зсувати по парі мільйонів елементів щоразу під час вставки! У чому ж причина його перемоги? По-перше, доступ до елемента здійснюється в ArrayList за фіксований час. Коли ти вказуєш:

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

то у випадку з ArrayList [2_000_000] це конкретна адреса в пам'яті, адже у нього всередині масив. У той час як у LinkedList масиву немає. Він шукатиме елемент номер 2_000_000 за ланцюжком посилань. Для нього це не адреса в пам'яті, а посилання, до якого ще треба дійти: ArrayList вже знає точну адресу в пам'яті, до якої він повинен звернутися, а ось LinkedList'у ще треба до потрібного місця "дотопати". По-друге, справа в структурі самого ArrayList'a. Розширення внутрішнього масиву, копіювання всіх елементів і зсув елементів здійснює спеціальна внутрішня функція – System.arrayCopy(). Вона працює дуже швидко, тому що спеціально оптимізована для цієї роботи. А ось у ситуаціях, коли "топати" до потрібного індексу не потрібно, LinkedList дійсно показує себе краще. Наприклад, якщо вставка відбувається в початок списку. Спробуємо вставити туди мільйон елементів:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       //напишіть тут ваш код
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); //обчислюємо різницю
       System.out.println("Результат у мілісекундах: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Виведення: Зовсім інший результат! На вставку мільйона елементів в початок списку ArrayList витратив понад 43 секунди, тоді як LinkedList впорався за 0,1 секунди! Позначився саме той факт, що в цій ситуації LinkedList'у не довелося "пробігати" щоразу ланцюжком посилань до середини списку. Він одразу знаходив потрібний індекс на початку списку, а там уже різниця в принципах роботи була на його боці:) Насправді, дискусія "ArrayList проти LinkedList" дуже поширена, і сильно в неї заглиблюватися на поточному рівні ми не будемо. Головне, що тобі потрібно запам'ятати:

• Не всі переваги тієї чи тієї колекції "на папері" діятимуть у реальності (ми розібрали це на прикладі з серединою списку)
• Не варто вдаватися до крайнощів під час обрання колекції ("ArrayList завжди швидший, використовуй його і не помилишся. LinkedList давно ніхто не користується").

Хоча навіть творець LinkedList Джошуа Блох так каже :) Проте ця точка зору правильна далеко не на 100%, і ми в цьому переконалися. У нашому попередньому прикладі LinkedList відпрацював у 400 (!) разів швидше. Інша річ, що ситуацій, коли LinkedList буде найкращим вибором, дійсно небагато. Але вони є, і в потрібний момент LinkedList може тебе серйозно виручити. Не забувай про те, про що ми говорили на початку лекції: для різних завдань найефективнішими є різні структури даних. Не можна на 100% впевнено говорити, яка структура даних буде кращою, поки невідомі точно всі умови завдання. Пізніше ти більше дізнаєшся про ці колекції, і зробити вибір буде простіше. Але найпростіший і найдієвіший варіант завжди один: випробуй і те, і інше на реальних даних своєї програми. Тоді ти зможеш на власні очі побачити результати роботи обох списків і точно не помилишся :)