Яка складність вставки на початок списку?
Складність вставки на початок зв'язаного списку - O(1) (постійна).
Чому так
Щоб додати елемент на початок списку, не потрібно проходити весь список. Достатньо:
- Створити новий вузол.
- Вказати, що його
next(посилання на наступний) = старийhead. - Перемістити
headна цей новий вузол.
Приклад:
javascript
До:
head → [10] → [20] → [30]
Після вставки 5:
head → [5] → [10] → [20] → [30]Ці три кроки займають постійний час, незалежно від довжини списку.
Формально
| Операція | Складність |
|---|---|
| Вставка на початок | O(1) |
| Вставка в середину | O(n) - потрібно дійти до потрібної позиції |
| Вставка в кінець | O(1), якщо є tail; інакше O(n) |
Чому це важливо
Це одна з головних переваг зв'язаних списків перед масивами:
- У масиві вставка на початок вимагає зсунути всі елементи → O(n).
- У списку достатньо змінити пару посилань → O(1).
Підсумок:
Вставка нового елемента на початок зв'язаного списку виконується за O(1), тому що потрібно лише переназначити одне посилання
head- без обходу решти вузлів.
Коротка відповідь
Для співбесідиPremium
Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.