Знайомство з колекцією LinkedList

1. Історія LinkedList

У Java є ще один клас-колекція, який дістався Java у спадок від мови C++. Це клас LinkedList, назва якого перекладається як «Зв'язаний список».

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

Тож навіщо потрібен іще один клас-список?

Вся річ у внутрішній будові класу LinkedList. Замість масиву в ньому використовується двобічно зв'язаний список. Що це таке, розповімо далі.

Завдяки іншій внутрішній будові клас LinkedList забезпечує найшвидше виконання операції вставлення елементів усередину списку.

В інтернеті часто можна побачити таке порівняння класів ArrayList і LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Начебто все зрозуміло: якщо потрібно вставляти елементи в список часто, використовуйте LinkedList, якщо рідко — ArrayList. Однак у реальності все дещо інакше.

2. Ніхто не використовує LinkedList

Ніхто не використовує LinkedList.

Нещодавно навіть сам автор коду класу LinkedList написав у Твіттері: «Друзі, хтось взагалі використовує LinkedList? Я за 20 років не використав його жодного разу!»

Так у чому ж річ?

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

Але зараз все змінилося. Усі елементи масиву розташовані поруч в одному блоці пам'яті, тому операція зсуву елементів масиву виконується дуже швидкою командою низького рівня System.arraycopy().

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

По-друге, клас LinkedList швидко вставляє елементи, якщо це робиться за допомогою ітератора. Якщо ви за допомогою ітератора перебираєте список LinkedList і постійно вставляєте нові елементи (або видаляєте наявні), це дійсно супершвидка операція.

Якщо ж ви просто в циклі додаєте елементи всередину класу LinkedList, кожна швидка операція вставлення супроводжується повільною операцією «отримання елемента».

У реальності ситуація така:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Чому ж операція отримання елемента в LinkedList така повільна?

Відповідь на це запитання ви дізнаєтеся, коли трохи ознайомитеся з будовою LinkedList

3. Будова LinkedList

Внутрішня будова LinkedList відрізняється від будови ArrayList. Усередині класу немає масиву для зберігання елементів. Замість цього використовується структура даних, яка має назву «двобічно зв'язаний список».

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

Отакий вигляд має цей список у пам'яті:

З боків (сірий фон) — змінні first і last, які зберігають посилання на об'єкти типу Node.

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

• prev — зберігає посилання на попередній об'єкт типу Node (жовтий фон).
• value — зберігає значення, тобто елемент списку (зелений фон).
• next — зберігає посилання на наступний об'єкт типу Node (синій фон).

Другий об'єкт (адреса == F24) є наступним (next) для першого і попереднім (prev) для третього об'єкта. Жовте поле третього об'єкта містить посилання F24, і синє поле першого об'єкта містить посилання F24.

Стрілки з першого й третього об'єктів вказують на той самий другий об'єкт. Тому правильніше було б намалювати стрілки так:

4. Вставляння елемента у зв'язаний список

Щоб додати людину в таку чергу, потрібно просто отримати згоду двох сусідів. Перший сусід запам'ятовує новачка як «ця людина за мною», а другий — як «ця людина переді мною».

Тобто потрібно просто змінити посилання двох сусідніх об'єктів:

Ми додали в наш список новий елемент і змінили посилання в другому й третьому об'єктах. Тепер новачок є наступним для другого об'єкта і попереднім для третього. Крім того, в самому об'єкті-новачку теж потрібно вказати правильні посилання: попередній об'єкт — другий, наступний об'єкт — третій.

Видалення ще простіше. Якщо ми хочемо видалити зі списку, приміром, 100-й об'єкт, потрібно просто в 99-го об'єкта поміняти next, щоб він указував на 101-й об'єкт, а у 101-го об'єкта поміняти prev, щоб він указував на 99-й. І все.

От тільки отримати 100-й об'єкт не так просто.

5. Отримання елемента списку

Щоб отримати 100-й елемент зв'язаного списку, потрібно:

Отримати 1-й об'єкт: на нього посилається змінна first об'єкта LinkedList. 1-й об'єкт містить посилання (поле next) на 2-й об'єкт. За цим посиланням отримуємо другий об'єкт. 2-й об'єкт містить посилання на 3-й об'єкт і т. д.

Щоб отримати посилання на 100-й об'єкт, нам потрібно послідовно перебрати всі об'єкти від 1-го до 100-го. А якщо нам потрібен мільйонний елемент списку, потрібно послідовно перебрати мільйон об'єктів!

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

Отакі справи.

Тож навіщо ми тут вивчаємо, як влаштовано цей повільний LinkedList?

Річ у тім, що на співбесіді вас обов'язково запитають, чим LinkedList відрізняється від ArrayList. Неодмінно.