Hogyan értékeljük a középső részbe történő elem beszúrásának műveleti nehézségét egy kétszárú láncolt listában?

Kétirányú láncolt lista középső részébe elem beszúrása általában először a beszúrás helyének megtalálását és utána a szomszédos csomópontok hivatkozásainak módosítását igényli.

A művelet összetettsége:

• Pozíció keresése: ha van hivatkozásod arra a csomópontra, ahová beszúrni szeretnéd, akkor nincs szükség keresésre.
• Beszúrás: a szomszédos csomópontok hivatkozásainak módosítása O(1) művelet.

Ha a beszúrás helyét index alapján határozzák meg, akkor végig kell menni a listán a kívánt csomópontig, ami O(n) időt vesz igénybe.

Összefoglalva:

• Ha a pozíció ismert (a csomópont megtalálva) — beszúrás O(1).
• Ha a pozíció index szerint van meghatározva — keresés + beszúrás O(n).