Aká je časová zložitosť vloženia prvku do stredu prepojenej zoznamu, ak už máte zaplnené pole?

Ak máte zaplnený poľ a chcete vložiť prvok do stredu prepojenej zoznamu, najskôr musíte nájsť pozíciu vloženia v zozname. Časová zložitosť pre vyhľadanie prvku v prepojenom zozname je O(n), pretože musíte prejsť prvky až na požadovanú pozíciu.

Po nájdení pozície sa vloženie prvku do prepojeného zoznamu vykoná v O(1), pretože stačí preusmerniť odkazy.

Celková časová zložitosť pre vloženie prvku do stredu prepojeného zoznamu pri existencii poľa (ktoré môže pomôcť rýchlo nájsť index, ale nie uzol zoznamu) bude O(n), pretože vyhľadávanie uzla trvá lineárny čas.

Ak máte pole, ktoré uchováva odkazy na uzly prepojeného zoznamu (napríklad pole ukazovateľov na prvky zoznamu), potom môže byť vloženie vykonané v O(1), pretože okamžite získate potrebný uzol.

Príklad:

// Predpokladajme, že máme prepojený zoznam a pole uzlov
Node[] poleUzolov = ...; // pole uzlov prepojeného zoznamu
int indexVlozenia = poleUzolov.length / 2;
Node predchadzajuciUzel = poleUzolov[indexVlozenia - 1];
Node novyUzel = new Node(hodnota);
novyUzel.next = predchadzajuciUzel.next;
predchadzajuciUzel.next = novyUzel;
// Vloženie bolo vykonané v O(1)

Ak nemáte pole s uzlami, musíte prejsť zoznam až na požadovanú pozíciu — O(n).