LinkedList у Java
Що, якби об'єкти були пов'язані між собою?
Переходимо до наступної, досить цікавої структури даних — LinkedList.
Розглянемо синтаксис та схему роботи LinkedList:
Як видно, синтаксис абсолютно ідентичний оголошенню ArrayList. Загалом, будь-який список можна оголосити таким чином.
Але найцікавіше починається тоді, коли ми намагаємося зрозуміти, як працює LinkedList.
Як влаштований LinkedList?
Усередині LinkedList працює з Nodes (вузлами). Node — це об'єкт, який зберігається всередині LinkedList. Він реалізований у LinkedList таким чином:
Main.java
1234567891011class 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 і попередній Node.
Саме так здійснюється проходження по списку. Розглянемо детальніше ітерацію по LinkedList.
Розглядаючи таку схему, можна зробити висновок, що ітерація по цьому списку відбувається інакше.
У ArrayList<>() на низькому рівні програма використовує масив, який подвоюється за розміром, коли кількість елементів досягає 3/4 його місткості.
У LinkedList<>() немає потреби створювати новий масив, оскільки масив відсутній у LinkedList.
Замість цього при додаванні нового елемента створюється новий об'єкт Node, який з'єднується посиланнями з попереднім останнім елементом.
Це може здаватися складним, але як програмісту, вам не доведеться все це налаштовувати.
Методи для LinkedList такі ж, як і для ArrayList, оскільки обидва вони успадковують інтерфейс List, який визначає методи, що мають бути реалізовані всіма його нащадками.
Алгоритмічна складність
У Collection framework існує багато різних структур даних, і кожна з них має свою алгоритмічну складність.
Алгоритмічна складність позначається за допомогою нотації великої O (наприклад, O(n), O(n^2)), де "O" означає "велика O" і вказує на верхню межу зростання часу виконання як функції розміру вхідних даних.
Ось основні типи алгоритмічної складності:
-
O(1)(константний час): складність не залежить від розміру вхідних даних. Наприклад, доступ до елемента масиву за індексом; -
O(log n)(логарифмічний час): складність зростає логарифмічно зі збільшенням розміру вхідних даних. Приклад: бінарний пошук у відсортованому масиві; -
O(n)(лінійний час): складність зростає лінійно зі збільшенням розміру вхідних даних. Приклад: перебір усіх елементів уArrayList; -
O(n^2)(квадратичний час): складність пропорційна квадрату розміру вхідних даних. Приклад: сортування бульбашкою.
Це базові категорії, існують й інші типи алгоритмічної складності, такі як O(n log n), O(2^n), O(n!) та інші, які характеризують більш складні алгоритми. Вибір ефективного алгоритму з урахуванням його складності — ключовий аспект розробки програмного забезпечення.
Тепер повернемося до структур даних у Java. Кожна структура даних має свою алгоритмічну складність залежно від операції, яку потрібно виконати. Розглянемо таблицю:
Ви можете побачити, що пошук елемента за індексом у ArrayList має константну складність, оскільки ми просто звертаємося до індексу в масиві.
Водночас у LinkedList пошук за індексом займає набагато більше часу, оскільки потрібно перебрати всі вузли і знайти потрібний об'єкт за індексом.
З іншого боку, якщо подивитися на вставку елемента, у LinkedList константна складність, а у ArrayList — лінійна. Це відбувається тому, що для вставки елемента у LinkedList достатньо змінити посилання у вузлах на нові, вставивши елемент між ними. Для ArrayList потрібно створити новий масив з новим елементом, що передбачає копіювання старого масиву та вставку елемента, що займає набагато більше часу.
Розглянемо приклад:
Main.java
1234567891011121314151617181920212223242526272829package 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
123456789class 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?
Дякуємо за ваш відгук!
Запитати АІ
Запитати АІ
Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат
Чудово!
Completion показник покращився до 4LinkedList у Java
Свайпніть щоб показати меню
Що, якби об'єкти були пов'язані між собою?
Переходимо до наступної, досить цікавої структури даних — LinkedList.
Розглянемо синтаксис та схему роботи LinkedList:
Як видно, синтаксис абсолютно ідентичний оголошенню ArrayList. Загалом, будь-який список можна оголосити таким чином.
Але найцікавіше починається тоді, коли ми намагаємося зрозуміти, як працює LinkedList.
Як влаштований LinkedList?
Усередині LinkedList працює з Nodes (вузлами). Node — це об'єкт, який зберігається всередині LinkedList. Він реалізований у LinkedList таким чином:
Main.java
1234567891011class 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 і попередній Node.
Саме так здійснюється проходження по списку. Розглянемо детальніше ітерацію по LinkedList.
Розглядаючи таку схему, можна зробити висновок, що ітерація по цьому списку відбувається інакше.
У ArrayList<>() на низькому рівні програма використовує масив, який подвоюється за розміром, коли кількість елементів досягає 3/4 його місткості.
У LinkedList<>() немає потреби створювати новий масив, оскільки масив відсутній у LinkedList.
Замість цього при додаванні нового елемента створюється новий об'єкт Node, який з'єднується посиланнями з попереднім останнім елементом.
Це може здаватися складним, але як програмісту, вам не доведеться все це налаштовувати.
Методи для LinkedList такі ж, як і для ArrayList, оскільки обидва вони успадковують інтерфейс List, який визначає методи, що мають бути реалізовані всіма його нащадками.
Алгоритмічна складність
У Collection framework існує багато різних структур даних, і кожна з них має свою алгоритмічну складність.
Алгоритмічна складність позначається за допомогою нотації великої O (наприклад, O(n), O(n^2)), де "O" означає "велика O" і вказує на верхню межу зростання часу виконання як функції розміру вхідних даних.
Ось основні типи алгоритмічної складності:
-
O(1)(константний час): складність не залежить від розміру вхідних даних. Наприклад, доступ до елемента масиву за індексом; -
O(log n)(логарифмічний час): складність зростає логарифмічно зі збільшенням розміру вхідних даних. Приклад: бінарний пошук у відсортованому масиві; -
O(n)(лінійний час): складність зростає лінійно зі збільшенням розміру вхідних даних. Приклад: перебір усіх елементів уArrayList; -
O(n^2)(квадратичний час): складність пропорційна квадрату розміру вхідних даних. Приклад: сортування бульбашкою.
Це базові категорії, існують й інші типи алгоритмічної складності, такі як O(n log n), O(2^n), O(n!) та інші, які характеризують більш складні алгоритми. Вибір ефективного алгоритму з урахуванням його складності — ключовий аспект розробки програмного забезпечення.
Тепер повернемося до структур даних у Java. Кожна структура даних має свою алгоритмічну складність залежно від операції, яку потрібно виконати. Розглянемо таблицю:
Ви можете побачити, що пошук елемента за індексом у ArrayList має константну складність, оскільки ми просто звертаємося до індексу в масиві.
Водночас у LinkedList пошук за індексом займає набагато більше часу, оскільки потрібно перебрати всі вузли і знайти потрібний об'єкт за індексом.
З іншого боку, якщо подивитися на вставку елемента, у LinkedList константна складність, а у ArrayList — лінійна. Це відбувається тому, що для вставки елемента у LinkedList достатньо змінити посилання у вузлах на нові, вставивши елемент між ними. Для ArrayList потрібно створити новий масив з новим елементом, що передбачає копіювання старого масиву та вставку елемента, що займає набагато більше часу.
Розглянемо приклад:
Main.java
1234567891011121314151617181920212223242526272829package 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
123456789class 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?
Дякуємо за ваш відгук!
