Що таке однозв'язний список (singly linked list)?
Однозв'язний список (singly linked list) - це структура даних, де кожен елемент (вузол) зберігає:
- значення (дані),
- посилання (вказівник) на наступний вузол у списку.
Останній елемент вказує на None (або null), що означає кінець списку.
1. Як це виглядає
javascript
head → [10 | *] → [20 | *] → [30 | None]head- вказівник на перший вузол;- кожен вузол зберігає дані й адресу наступного;
Noneу останнього вузла - ознака кінця списку.
2. Як зберігаються дані
Елементи не лежать поспіль у пам'яті.
Кожен вузол створюється динамічно і може перебувати будь-де,
а зв'язки між ними створюються через вказівники (next).
Приклад (умовні адреси):
javascript
[10 | next=2056]
[2056]: [20 | next=3172]
[3172]: [30 | next=None]3. Основні операції
| Операція | Складність | Опис |
|---|---|---|
| Доступ за індексом | O(n) | Потрібно пройти всі вузли до потрібного. |
| Вставка на початок | O(1) | Просто переназначається head. |
| Вставка в кінець | O(n) | Потрібно дійти до останнього вузла. |
| Видалення вузла | O(n) | Потрібно знайти попередній елемент. |
4. Переваги
- Проста реалізація.
- Швидка вставка й видалення на початку (O(1)).
- Розмір списку може змінюватися динамічно.
5. Недоліки
- Повільний доступ до елементів (O(n)).
- Не можна рухатися назад (немає посилань на попередні вузли).
- Витрачається додаткова пам'ять на зберігання вказівників.
6. Приклад на Python
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# створення списку 10 → 20 → 30
n1 = Node(10)
n2 = Node(20)
n3 = Node(30)
n1.next = n2
n2.next = n3
head = n1Підсумок:
Однозв'язний список - це динамічна структура даних, де кожен елемент зберігає дані й посилання на наступний. Вона ефективна при вставках і видаленнях, але повільна при доступі за індексом.
Коротка відповідь
Для співбесідиPremium
Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.