1. Історія LinkedList
У Java є ще один клас-колекція, який дістався Java у спадок від мови C++. Це клас LinkedList
, назва якого перекладається як «Зв'язаний список».
Зовні LinkedList
— це такий самий список, як ArrayList
. Клас LinkedList
має такі самі методи, що й клас ArrayList
. Власне, ви завжди можете використовувати LinkedList
замість ArrayList
, і все працюватиме.
Тож навіщо потрібен іще один клас-список?
Вся річ у внутрішній будові класу LinkedList
. Замість масиву в ньому використовується двобічно зв'язаний список. Що це таке, розповімо далі.
Завдяки іншій внутрішній будові клас LinkedList
забезпечує найшвидше виконання операції вставлення елементів усередину списку.
В інтернеті часто можна побачити таке порівняння класів ArrayList
і LinkedList
:
Операція | Метод | ArrayList | LinkedList |
---|---|---|---|
Додавання елемента |
|
Швидко | Дуже швидко |
Вставляння елемента |
|
Повільно | Дуже швидко |
Отримання елемента |
|
Дуже швидко | Повільно |
Змінення елемента |
|
Дуже швидко | Повільно |
Видалення елемента |
|
Повільно | Дуже швидко |
Начебто все зрозуміло: якщо потрібно вставляти елементи в список часто, використовуйте LinkedList
, якщо рідко — ArrayList
. Однак у реальності все дещо інакше.
2. Ніхто не використовує LinkedList
Ніхто не використовує LinkedList
.
Нещодавно навіть сам автор коду класу LinkedList
написав у Твіттері: «Друзі, хтось взагалі використовує LinkedList
? Я за 20 років не використав його жодного разу!»
Так у чому ж річ?
По-перше, у класі ArrayList
елементи всередину списку тепер вставляються дуже швидко. Під час додавання елемента всередину списку слід посунути всі елементи після потрібного на 1 позицію в бік кінця списку. Раніше це потребувало часу.
Але зараз все змінилося. Усі елементи масиву розташовані поруч в одному блоці пам'яті, тому операція зсуву елементів масиву виконується дуже швидкою командою низького рівня System.arraycopy()
.
До того ж зараз процесори мають великий кеш, і зазвичай весь масив потрапляє в такий кеш, тому елементи масиву зсуваються навіть не в пам'яті, а в кеші процесора. Щоб посунути мільйон елементів, потрібно не більше мілісекунди.
По-друге, клас LinkedList
швидко вставляє елементи, якщо це робиться за допомогою ітератора. Якщо ви за допомогою ітератора перебираєте список LinkedList
і постійно вставляєте нові елементи (або видаляєте наявні), це дійсно супершвидка операція.
Якщо ж ви просто в циклі додаєте елементи всередину класу LinkedList
, кожна швидка операція вставлення супроводжується повільною операцією «отримання елемента».
У реальності ситуація така:
Операція | Метод | ArrayList | LinkedList |
---|---|---|---|
Додавання елемента |
|
Швидко | Дуже швидко |
Вставляння елемента |
|
Повільно | Дуже повільно |
Отримання елемента |
|
Дуже швидко | Дуже повільно |
Змінення елемента |
|
Дуже швидко | Дуже повільно |
Видалення елемента |
|
Повільно | Дуже повільно |
Вставляння за допомогою ітератора |
|
Повільно | Дуже швидко |
Видалення за допомогою ітератора |
|
Повільно | Дуже швидко |
Чому ж операція отримання елемента в 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
. Неодмінно.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ