Kui suur on ajakulud, kui lisada element seotud nimekirja keskossa, kui teil on juba täidetud massiiv?

Kui teil on täidetud massiiv ja soovite sisestada elemendi seotud nimekirja keskpaika, peate kõigepealt leidma sisestuspositsiooni nimekirjas. Elementide otsimise keerukus seotud nimekirjas on O(n), kuna peate läbima elemendid kuni soovitud positsioonini.

Kui positsioon on leitud, toimub elemendi sisestamine seotud nimekirja O(1) ajal, kuna piisab linkide ümber suunamisest.

Seega, kogu aeglõike keerukus elemendi sisestamisel seotud nimekirja keskpaika, kui on olemas massiiv (mis võib aidata kiiresti leida indeksi, kuid mitte nimekirja sõlme), on O(n), kuna sõlme otsimine võtab lineaarse aega.

Kui teil on massiiv, mis salvestab viited seotud nimekirja sõlmedele (näiteks, viidete massiiv nimekirja elementidele), siis võib sisestamine toimuda O(1) ajal, kuna saate otse vajalikku sõlme.

Näide:

// Oletame, et meil on seotud nimekiri ja sõlmede massiiv
Node[] sõlmedeMassiiv = ...; // seotud nimekirja sõlmede massiiv
int sisestusIndeks = sõlmedeMassiiv.length / 2;
Node eelmineSõlm = sõlmedeMassiiv[sisestusIndeks - 1];
Node uusSõlm = new Node(väärtus);
uusSõlm.next = eelmineSõlm.next;
eelmineSõlm.next = uusSõlm;
// Sisestus tehti O(1) ajal

Kui teil pole sõlmede massiivi, peate läbima nimekirja kuni soovitud positsioonini — O(n).