Ako sa hodnotí zložitosť operácie vloženia prvku do centrálnej časti dvojzložkového zoznamu?

Vloženie prvku do centrálnej časti dvojzloženej zoznamu zvyčajne vyžaduje najskôr nájsť pozíciu vloženia a potom zmeniť odkazy susedných uzlov.

Zložitosť operácie:

• Vyhľadanie pozície: ak máte odkaz na uzol, kam chcete vložiť, vyhľadávanie nie je potrebné.
• Vloženie: zmena odkazov susedných uzlov je operácia O(1).

Ak je pozícia vloženia určená indexom, je potrebné prejsť zoznam až k požadovanému uzlu, čo trvá O(n) času.

Zhrnutie:

• Ak je pozícia známa (uzol nájdený) — vloženie v O(1).
• Ak je pozícia určená indexom — vyhľadávanie + vloženie v O(n).