Kā tiek novērtēta elementa ievietošanas operācija divvirzienu saraksta centrālo daļu pēc sarežģītības?

Divkārši saistīts saraksts parasti prasa pirmo atrast ievietošanas pozīciju, pēc tam mainīt blakus esošo mezglu saites.

Operācijas sarežģītība:

• Pozīcijas meklēšana: ja jums ir atsauce uz mezglu, kurā vēlaties ievietot, meklēšana nav nepieciešama.
• Ievietošana: blakus esošo mezglu saites maiņa ir O(1) operācija.

Ja ievietošanas pozīcija ir noteikta pēc indeksa, jums ir jāpārlūko saraksts līdz vēlamajam mezglam, kas aizņem O(n) laiku.

Kopsavilkums:

• Ja pozīcija ir zināma (mezgls atrasts) — ievietošana O(1).
• Ja pozīcija ir noteikta pēc indeksa — meklēšana + ievietošana O(n).