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

Складність видалення із середини зв'язаного списку - O(n) (лінійна).

---

#Чому так

Щоб видалити елемент із середини, потрібно:

1. Знайти цей елемент - а отже, пройти список від head до потрібного вузла (це вже O(n)).
2. Переназначити посилання:

• попередній вузол тепер має вказувати на наступний після видаленого,
• а видаленому вузлу "випадає" з ланцюжка.

Ця друга операція - O(1), але пошук позиції - O(n), і саме він визначає загальну складність.

---

#Приклад

1. Пройти до [20] - займає час, пропорційний кількості вузлів.
2. Змінити посилання попереднього: [10].next = [30].
3. Вузол [20] видалено.

---

#Якщо вказівник на вузол, що видаляється, уже є

Якщо програма вже має пряме посилання на потрібний вузол (а не індекс), то видалення виконується за O(1) - просто переназначаються посилання.

---

#Формально

---

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

---

Підсумок:

Видалення із середини зв'язаного списку займає O(n), тому що потрібно пройти до потрібного вузла, перш ніж змінити посилання.