Які види зв'язаних списків існують?
Існує кілька видів зв'язаних списків, і вони відрізняються тим, як пов'язані між собою вузли (елементи).
Головна ідея - у кожного вузла є дані та посилання (вказівники) на інші вузли.
1. Однозв'язний список (Singly Linked List)
Кожен вузол зберігає:
- дані,
- посилання на наступний елемент (
next).
head → [A | *] → [B | *] → [C | None]- Рух можливий тільки вперед.
- Щоб видалити елемент, потрібно знати попередній вузол.
- Кінець списку (
tail) має посиланняNone.
Плюси: проста реалізація, економія пам'яті. Мінуси: не можна рухатися назад, доступ за індексом повільний (O(n)).
2. Двозв'язний список (Doubly Linked List)
Кожен вузол зберігає:
- дані,
- посилання на наступний елемент (
next), - посилання на попередній (
prev).
None ← [A | * | *] ↔ [B | * | *] ↔ [C | * | None]- Можна рухатися в обидва боки.
- Простіше видаляти й вставляти елементи.
Плюси: гнучкий, швидкі вставки й видалення. Мінуси: потребує більше пам'яті (два посилання замість одного).
3. Циклічний список (Circular Linked List)
Останній елемент (tail) вказує не на None, а на перший елемент (head), утворюючи кільце.
[A] → [B] → [C]
↑__________↓- Може бути однозв'язним або двозв'язним.
- Зручний для циклічних структур (наприклад, кільцевих черг).
Плюси: можна нескінченно обходити список по колу. Мінуси: потрібна обережність - легко потрапити в нескінченний цикл.
4. Багатозв'язний (або skip list)
Кожен вузол зберігає кілька посилань на різні "рівні" списку. Використовується для прискорення пошуку (приклад - структура даних Skip List).
Рівень 2: A → → → E
Рівень 1: A → B → C → D → EПлюси: пошук швидший, ніж у звичайному списку (у середньому O(log n)). Мінуси: складніша реалізація.
Підсумок:
| Вид списку | Посилання | Рух | Особливості |
|---|---|---|---|
| Однозв'язний | Тільки next | Вперед | Простий, економічний |
| Двозв'язний | prev і next | Вперед і назад | Швидкі вставки/видалення |
| Циклічний | Замикається в кільце | По колу | Для циклічних структур |
| Багатозв'язний (skip list) | Кілька посилань | Швидкий пошук | Використовується в базах даних |
Висновок:
Усі зв'язані списки працюють за однією ідеєю - ланцюжок вузлів із посиланнями, але різні види дають різний баланс між швидкістю, пам'яттю та гнучкістю.
Коротка відповідь
Для співбесідиКоротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.