Junior — Middle
Milyen időmértékű az elem beszúrásának művelete a kétszárnyú láncolt lista középső részébe?
sobes.tech MI
Válasz az MI-től
Kétirányú láncolt lista középső részébe elem beszúrása általában először meg kell találni a beszúrás helyét, ami O(n) időt vesz igénybe, mivel végig kell menni a listán a kívánt csomópontig.
A beszúrás maga (a szomszédos csomópontok mutatóinak módosítása) O(1) idő alatt történik.
Összefoglalva:
- Pozíció keresése — O(n)
- Beszúrás — O(1)
Ha a pozíció már ismert (például, ha van egy mutató egy csomópontra), akkor a beszúrás O(1). Ha nem, először végig kell menni a listán, ami O(n) időt vesz igénybe.