Aká je odhadovaná časová zložitosť operácie odstránenia prvku v jednoducho spojenom zozname?

Časová zložitosť odstránenia prvku v jednoducho prepojenej zozname závisí od toho, či máme ukazovateľ na odstraňovaný prvok alebo len na hlavu zoznamu.

• Ak je potrebné odstrániť prvok, poznajúc len hlavu zoznamu, najskôr musíme prejsť zoznam, aby sme našli prvok a jeho predchádzajúci uzol. To trvá O(n) času, kde n je počet prvkov v zozname.
• Ak máme ukazovateľ na predchádzajúci prvok (alebo na samotný odstraňovaný prvok, ak je to prvý), odstránenie prebieha za O(1), pretože stačí preusporiadať odkazy.

Všeobecne platí, že odstránenie prvku v jednoducho prepojenom zozname je operácia s časovou zložitosťou O(n).