Mi a becslése az időbeli komplexitásnak egy elem törlésének műveletében egy egysoros láncolt listában?

Egy egysoros láncolt lista elemének törlésének időbeli komplexitása attól függ, hogy van-e mutatónk a törlendő elemre vagy csak a lista fejére.

• Ha csak a lista fejét ismerjük, és egy elemet kell törölni, akkor először végig kell menni a listán, hogy megtaláljuk az elemet és annak előző csomópontját. Ez O(n) időt vesz igénybe, ahol n a lista elemeinek száma.
• Ha van mutatónk az előző elemre (vagy a törlendő elemre, ha az első), akkor a törlés O(1) idő alatt végrehajtható, mivel elegendő a hivatkozásokat újra beállítani.

Általánosságban elmondható, hogy egy egysoros láncolt listából történő elem törlése egy O(n) időkomplexitású művelet.