Jak se určuje časová složitost odstranění prvku nacházejícího se uprostřed spojovaného seznamu?

Časová složitost odstranění prvku ze středu spojovaného seznamu závisí na tom, zda máte přímý přístup k tomuto prvku a jeho předchozímu uzlu.

• Pokud máte ukazatel na samotný prvek a na předchozí uzel (například u dvousměrně spojovaného seznamu), pak odstranění probíhá za O(1), protože je třeba pouze přenastavit odkazy.
• Pokud máte pouze hodnotu nebo ukazatel na prvek bez přístupu k předchozímu, je nejprve nutné projít seznam od začátku až k tomuto prvku, což trvá O(n), kde n je počet prvků před odstraňovaným.

Obecně se tedy odstranění ze středu spojovaného seznamu považuje za operaci s časovou složitostí O(n), pokud nemáte přímý přístup k předchozímu uzlu.