Свайпніть щоб показати меню

Що, якби об'єкти були пов'язані між собою?

Переходимо до наступної, досить цікавої структури даних — LinkedList.

Розглянемо синтаксис та схему роботи LinkedList:

Як бачимо, синтаксис повністю ідентичний оголошенню ArrayList. Загалом, будь-який список можна оголосити таким чином.

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

Як влаштований LinkedList?

Усередині LinkedList працює з Nodes (вузлами). Node — це об'єкт, який зберігається всередині LinkedList. Його реалізація в LinkedList виглядає так:

Main.java


              1234567891011
            
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

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

Розглянемо, з чого складається цей клас. Спочатку потрібно відповісти на головне питання: що означає <E>? Це узагальнення (generic).

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

Це можна порівняти з перевантаженням.

Розглянемо, як це працює:

Отже, замість перевантаження цього методу для кожного типу даних, використовується універсальний тип (generic), у який підставляється потрібний тип даних, з яким працюватиме метод. Літера E буде просто замінена на необхідний тип даних. У нашому випадку це Integer.

Далі звернемо увагу на поле item типу E. Це значення об'єкта, яке зберігатиметься у цьому Node. Тобто, якщо ми створимо список на кшталт {0, 1, 2, 3}, перший вузол зберігатиме елемент 0, другий — елемент 1 і так далі.

Далі ви бачите посилання на інші об'єкти Node: Node<E> next та Node<E> prev. Це основна особливість зв'язаного списку. В одному Node міститься посилання на наступний Node і попередній вузол. Саме так відбувається проходження по списку. Розглянемо детальніше ітерацію по LinkedList.

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

У ArrayList<>() під капотом програма використовує масив, який подвоюється за розміром, коли кількість елементів досягає 3/4 його місткості.

У LinkedList<>() немає необхідності створювати новий масив, оскільки в LinkedList масиву тут немає. Натомість при додаванні нового елемента створюється новий об'єкт Node, який з'єднується посиланнями з попереднім останнім елементом.

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

Методи для LinkedList такі ж, як і для ArrayList, оскільки обидва наслідують інтерфейс List, який визначає методи, що мають бути реалізовані всіма його нащадками.

Алгоритмічна складність

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

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

З іншого боку, якщо розглянути вставку елемента, у LinkedList вона має константну складність, а у ArrayList — лінійну складність. Це відбувається тому, що для вставки елемента у LinkedList достатньо змінити посилання у вузлах на нові, вставивши елемент між ними. Для ArrayList потрібно створити новий масив із новим елементом, що передбачає копіювання старого масиву та вставку елемента, що займає набагато більше часу.

Розглянемо приклад:

Main.java


              1234567891011121314151617181920212223242526272829
            
package com.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();

        Random random = new Random();

        for (int i = 0; i < 1000000; i++) {
            int randomValue = random.nextInt(100);
            arrayList.add(randomValue);
            linkedList.add(randomValue);
        }
        long startTimeArrayList = System.nanoTime();
        arrayList.add(1000, 50);
        long endTimeArrayList = System.nanoTime();
        long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList;
        System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds");

        long startTimeLinkedList = System.nanoTime();
        linkedList.add(1000, 50);
        long endTimeLinkedList = System.nanoTime();
        long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList;
        System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds");
    }
}

Ми створили два списки: один — це ArrayList, а інший — LinkedList. Далі ми заповнили їх 1 000 000 випадкових цілих чисел. Обидва списки мають однаковий вміст, кожен містить мільйон чисел від 1 до 100.

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

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

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

SinglyLinkedList

Існує ще одна неописана структура даних під назвою SinglyLinkedList. Як випливає з назви, ця структура даних використовує ітерацію лише в одному напрямку. У той час як у класі LinkedList вузол Node має поля: item, next та prev, у класі SinglyLinkedList вузол Node має лише 2 поля: item та next.

Main.java


              123456789
            
class Node<E> {
    E item;
    Node<E> next;

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

Ця структура даних використовується у таких структурах, як мапи, де ітерація потрібна лише в одному напрямку. Ми розглянемо мапи, зокрема HashMap, у наступних розділах.

У наступному розділі ми напишемо реалізацію SinglyLinkedList, щоб краще зрозуміти, як працює ця цікава структура даних.

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

2. Яка структура даних працюватиме швидше при виконанні операції видалення?

3. Яким чином клас `Node` бере участь у роботі `LinkedList`?

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 1. Розділ 6

Запитати АІ

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Секція 1. Розділ 6

Linkedlist у Java

Що, якби об'єкти були пов'язані між собою?

Як влаштований LinkedList?

Алгоритмічна складність

SinglyLinkedList

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

2. Яка структура даних працюватиме швидше при виконанні операції видалення?

3. Яким чином клас Node бере участь у роботі LinkedList?

3. Яким чином клас `Node` бере участь у роботі `LinkedList`?