Mi az időbeli komplexitás, ha már van egy kitöltött tömböd, és be szeretnéd szúrni egy összekapcsolt listába a közepébe?

Ha van egy kitöltött tömböd, és be szeretnéd szúrni egy elemét egy összekapcsolt lista közepébe, először meg kell találnod a beszúrási pozíciót a listában. Az elem keresésének időkomplexitása összekapcsolt listában O(n), mivel végig kell menned az elemeket a kívánt pozícióig.

Miután megtaláltad a pozíciót, az elem beszúrása az összekapcsolt listába O(1), mivel elegendő átirányítani a hivatkozásokat.

Így az összesített időkomplexitás az összekapcsolt lista közepébe történő elem beszúrására, ha van egy tömb (amely gyorsan megtalálhatja az indexet, de nem a lista csomópontját), O(n) lesz, mivel a csomópont keresése lineáris időt vesz igénybe.

Ha van egy tömb, ami a lista csomópontjaira mutató hivatkozásokat tárol (például, egy pointerek tömbje a lista elemeire), akkor a beszúrás O(1) idő alatt végrehajtható, mivel közvetlenül megkapod a szükséges csomópontot.

Példa:

// Tegyük fel, hogy van egy összekapcsolt listánk és egy csomópontokat tartalmazó tömb
Node[] csomopontTomb = ...; // összekapcsolt lista csomópontjainak tömbje
int beszúrásiIndex = csomopontTomb.length / 2;
Node elottiCsomopont = csomopontTomb[beszúrásiIndex - 1];
Node ujCsomopont = new Node(ertek);
ujCsomopont.next = elottiCsomopont.next;
elottiCsomopont.next = ujCsomopont;
// A beszúrás O(1) idő alatt megtörtént

Ha nincs ilyen tömb, akkor végig kell menned a listán a kívánt pozícióig — O(n).