Kāda ir laika sarežģītība elementa ievietošanai saistītajā sarakstā vidū, ja jums jau ir pilns masīvs?

Ja jums ir pilns masīvs, un vēlaties ievietot elementu saistītā saraksta vidū, vispirms jāatrod ievietošanas pozīcija sarakstā. Laika sarežģītība elementa meklēšanai saistītajā sarakstā ir O(n), jo jums jāiziet cauri elementiem līdz vēlamajai pozīcijai.

Kad pozīcija ir atrasta, elementa ievietošana saistītajā sarakstā notiek O(1), jo pietiek ar saistību pārrādīšanu.

Tādējādi kopējā laika sarežģītība elementa ievietošanai saraksta vidū, ja ir masīvs (kas var palīdzēt ātri atrast indeksu, bet ne mezglu sarakstā), būs O(n), jo mezgla meklēšana aizņem lineāru laiku.

Ja jums ir masīvs, kas glabā atsauces uz saistītā saraksta mezgliem (piemēram, masīvs ar norādēm uz saraksta elementiem), tad ievietošana var tikt veikta O(1), jo jūs tieši saņemat nepieciešamo mezglu.

Piemērs:

// Pieņemsim, ka mums ir saistīts saraksts un mezglu masīvs
Node[] mezgluMasivs = ...; // saistītā saraksta mezglu masīvs
int ievietošanasIndekss = mezgluMasivs.length / 2;
Node iepriekšējaisMezgls = mezgluMasivs[ievietošanasIndekss - 1];
Node jaunsMezgls = new Node(vērtība);
jaunsMezgls.next = iepriekšējaisMezgls.next;
iepriekšējaisMezgls.next = jaunsMezgls;
// Ievietošana veikta O(1) laikā

Ja jums nav mezglu ar atsaucēm, jums jāiziet cauri sarakstam līdz vēlamajai pozīcijai — O(n).