Яка складність вставки в кінець списку?

Складність вставки в кінець зв'язаного списку залежить від того, чи зберігається вказівник на останній елемент (tail).

---

#1. Якщо tail відсутній

(тільки head - як у простому однозв'язному списку)

Щоб додати новий елемент у кінець, потрібно:

1. Почати з head;
2. Пройти всі вузли, поки не знайдеш останній (next = None);
3. Додати новий вузол і зв'язати його.

Це вимагає пройти весь список - Складність: O(n).

---

#2. Якщо tail зберігається окремо

(структура списку містить обидва вказівники: head і tail)

Тоді:

1. Створюється новий вузол;
2. Поточний tail.next вказує на нього;
3. tail оновлюється на новий вузол.

Усе виконується за постійний час - Складність: O(1).

---

#3. Для двозв'язного списку

Та сама логіка:

• без tail - O(n);
• з tail - O(1).

---

#Порівняння з масивом

---

Підсумок:

Вставка в кінець зв'язаного списку виконується: • за O(1), якщо є вказівник tail, • за O(n), якщо потрібно проходити весь список до кінця.