Що таке зв'язаний список?
Зв'язаний список (linked list) - це структура даних, у якій елементи (які називають вузлами) зберігаються не поспіль у пам'яті, а з'єднані між собою посиланнями (вказівниками).
Кожен вузол знає, де лежить наступний елемент, а іноді - і попередній.
1. Структура вузла
Один вузол зазвичай містить:
- дані (value) - саме значення,
- посилання (next) - адресу наступного вузла.
javascript
[дані | посилання на наступний]Приклад (однозв'язний список):
javascript
head → [10 | *] → [20 | *] → [30 | None]2. Види зв'язаних списків
| Тип | Особливості |
|---|---|
| Однозв'язний | Кожен вузол зберігає посилання тільки на наступний елемент. Рух - тільки вперед. |
| Двозв'язний | Кожен вузол зберігає посилання на попередній і наступний. Можна йти в обидва боки. |
| Циклічний | Останній вузол (tail) вказує на перший (head), утворюючи кільце. |
3. Основні операції
| Операція | Складність | Коментар |
|---|---|---|
| Доступ за індексом | O(n) | Потрібно пройти всі вузли до потрібного. |
| Вставка/видалення (за відомого вузла) | O(1) | Просто змінюються посилання. |
| Пошук елемента | O(n) | Послідовний обхід. |
4. Відмінність від масиву
| Критерій | Масив | Зв'язаний список |
|---|---|---|
| Зберігання | Безперервне в пам'яті | Розкидане, з'єднане посиланнями |
| Доступ за індексом | O(1) | O(n) |
| Вставка/видалення | Повільно (O(n)) | Швидко (O(1)) |
| Розмір | Зазвичай фіксований | Може змінюватися динамічно |
5. Застосування
Зв'язані списки використовують, коли:
- потрібне часте додавання й видалення елементів;
- розмір даних заздалегідь невідомий;
- пам'ять може бути фрагментованою (наприклад, у системному програмуванні).
Підсумок:
Зв'язаний список - це динамічна структура, де елементи з'єднані посиланнями, а не розташовані поспіль. Вона гнучка, але повільніша за масив при випадковому доступі.
Коротка відповідь
Для співбесідиPremium
Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.