Hogyan határozható meg a középen lévő elem törlésének időbeli összetettsége egy láncolt listában?

A láncolt lista közepéből történő elem törlésének időbeli összetettsége attól függ, hogy van-e közvetlen hozzáférése ehhez az elemhez és annak előző csomópontjához.

• Ha van mutató az elemre és az előző csomópontjára (például kétszintű láncolt listában), akkor a törlés O(1) idő alatt végrehajtható, mivel csak a hivatkozásokat kell újra konfigurálni.
• Ha csak az értéket vagy egy mutatót az elemre, de nincs hozzáférés az előzőhöz, akkor először végig kell menni a listán az elejétől, amíg el nem érjük ezt az elemet, ami O(n) időt vesz igénybe, ahol n az elem előtt lévő elemek száma.

Általánosságban elmondható, hogy a láncolt lista közepéből történő törlés, ha nincs közvetlen hozzáférés az előző csomóponthoz, O(n) időkomplexitású műveletnek számít.