Каква е оценката за времевата сложност на операцията по изтриване на елемент в едносвързан списък?

Времевата сложност при изтриване на елемент в едносвързан списък зависи от това дали разполагаме с указател към изтривания елемент или само към главата на списъка.

• Ако трябва да изтрием елемент, знаейки само главата на списъка, първо трябва да преминем през списъка, за да намерим елемента и неговия предходен възел. Това отнема O(n) време, където n е броят на елементите в списъка.
• Ако имаме указател към предходния елемент (или към самия изтриван елемент, ако е първият), изтриването става за O(1), тъй като е достатъчно да пренастроим връзките.

Общо взето, изтриването на елемент в едносвързан списък е операция с времева сложност O(n).