Hogyan határozható meg egy egyszemélyes láncolt lista közepébe történő elem beszúrásának időbeli összetettsége?

Egyszerű láncolt lista közepébe elem beszúrása először végig kell menni a listán a kezdettől a kívánt pozícióig, mivel az egyszerű láncolt listában nincsenek fordított hivatkozások vagy közvetlen hozzáférés az elemekhez index szerint.

Az egyszerű láncolt lista közepébe történő beszúrás időkomplexitása O(n), ahol n a beszúrási pozícióig tartó elemek száma. Ez annak köszönhető, hogy végig kell menni a listán a kívánt csomópontig.

A beszúrás maga (mutatók módosítása) O(1), de a pozíció keresése O(n), így a teljes komplexitás O(n).