Ako sa určuje časová zložitosť odstránenia prvku nachádzajúceho sa uprostred spojeného zoznamu?

Časová zložitosť odstránenia prvku zo stredu spájanej zoznamu závisí od toho, či máte priame prístup k tomuto prvku a jeho predchádzajúcemu uzlu.

• Ak máte ukazovateľ na samotný prvok a na predchádzajúci uzol (napríklad v dvojzmyselne spájanej zozname), odstránenie prebieha za O(1), pretože stačí preusporiadať odkazy.
• Ak máte iba hodnotu alebo ukazovateľ na prvok bez prístupu k predchádzajúcemu, najskôr musíte prejsť zoznam od začiatku až k tomuto prvku, čo trvá O(n), kde n je počet prvkov pred odstraňovaným.

Všeobecne sa teda odstránenie zo stredu spájanej zoznamu považuje za operáciu s časovou zložitosťou O(n), ak nemáte priame prístup k predchádzajúcemu uzlu.