Що таке двозв'язаний список?
Уявіть собі двозв'язаний список як потяг, де кожен вагон (вузол) може рухатися як вперед, так і назад. Кожен вагон знає, який вагон перед ним, а який — позаду. Як і в потязі, ви можете йти по ньому в обох напрямках!
Порівняння швидкості
Давайте порівняємо, як швидко працюють різні структури даних.
Уявімо, що у нас є три різні способи організації даних: Масив (як автобус), Однозв'язний список (як велосипед) та Двозв'язний список (як потяг).
Операція | Масив | Однозв'язний список | Двозв'язний список
---|---|---|---
Вставка на початку | O(n) — Повільно | O(1) — Швидко | O(1) — Швидко
Вставка в кінець | O(1) — Швидко | O(1) — Швидко | O(1) — Швидко
Вставка в середину | O(n) — Повільно | O(n) — Повільно | O(n) — Повільно
Видалення з початку | O(n) — Повільно | O(1) — Швидко | O(1) — Швидко
Видалення з кінця | O(1) — Швидко | O(n) — Повільно | O(1) — Швидко
Видалення з середини | O(n) — Повільно | O(n) — Повільно | O(n) — Повільно
Примітка: O(1) означає сталий час (Швидко), O(n) — лінійний час (Повільно)
Як це працює
Давайте використаємо реальний приклад: уявіть собі музичний плейлист, де ви можете пропустити наступну пісню або повернутися до попередньої.
Кожна пісня (вузол) знає як наступну, так і попередню пісню.
Основний будівельний блок
class Node {
public:
int val; // Пісня
Node* prev; // Посилання на попередню пісню
Node* next; // Посилання на наступну пісню
Node(val) {
this->val = val;
this->prev = NULL;
this->next = NULL;
}
};
Круті речі, які ми можемо зробити
- Рухатись в обидва боки: Як кнопки «Наступна» і «Попередня» у вашому музичному плеєрі
- Додавати пісні: Додавати нову пісню на початок, кінець або між іншими піснями
- Видаляти пісні: Видаляти пісні з будь-якої точки плейліста
- Перемикати порядок: Легко перевертати порядок пісень у плейлисті
Чому це круто
- Можна рухатися вперед і назад, як переглядати фотографії на вашому телефоні
- Швидко видаляти пісні з будь-якого кінця вашого плейліста
- Краще за простіші списки для багатьох завдань
- Легко знаходити сусідні елементи, як знаходити станції поруч з вами на маршруті потяга
Що слід врахувати
Так само, як і організація великої вечірки, треба бути обережним:
- Переконатися, що всі зв'язки правильно зроблені, як зв'язування друзів у Facebook в обидва боки
- Обережно поводитись з першими та останніми елементами
- Не втратити жодного зв'язку під час змін
- Правильно прибирати після видалення елементів
Реальні приклади використання
- Фото галереї, де можна проводити вліво або вправо
- Кнопки «Скасувати/Повторити» у ваших улюблених додатках
- Музичні додатки з кнопками «Попередня» та «Наступна»
- Історія браузера для переходу назад та вперед
Уявіть собі двозв'язний список як двосторонню вулицю — ви можете легко рухатися вперед і назад.
Хоча це потребує трохи більше пам'яті (як більший гараж), це надзвичайно корисно, коли потрібно рухатися в обидва боки!
Перекладено з: Doubly Linked Lists: A Fun Journey Through Connected Data