Ako určiť časovú zložitosť operácie vloženia prvku do stredu jednoducho spojeného zoznamu?

Vloženie prvku do stredu jednoducho prepojenej zoznamu si vyžaduje najskôr prejsť zoznam od začiatku po požadovanú pozíciu, pretože v jednoducho prepojenom zozname neexistujú spätné odkazy ani priame prístupy k prvkom podľa indexu.

Časová zložitosť operácie vloženia do stredu jednoducho prepojeného zoznamu je O(n), kde n je počet prvkov až po pozíciu vloženia. To je spôsobené potrebou prejsť zoznam až k požadovanému uzlu.

Samotný proces vloženia (zmena ukazovateľov) trvá O(1), ale hľadanie pozície — O(n), takže celková zložitosť je O(n).