Kako proceniti vremensku složenost operacija umetanja, brisanja i pretraživanja elemenata u povezanoj listi?

Vremenska složenost operacija u povezanoj listi zavisi od toga šta tačno radimo i da li imamo pristup potrebnom čvoru:

• Ubacivanje:

  • Na početak liste — O(1), jer je dovoljno da promenimo veze.
  • Na kraj jednostruko povezane liste bez pokazivača na kraj — O(n), potrebno je proći kroz celu listu.
  • Na kraj sa pokazivačem na kraj — O(1).
  • Na bilo koje mesto (po indeksu ili vrednosti) — O(n), jer je potrebno pronaći poziciju.

• Brisanje:

  • Brisanje prvog elementa — O(1).
  • Brisanje po vrednosti ili indeksu — O(n), jer je potrebno pronaći element i njegovog prethodnika.

• Pretraživanje:

  • Pretraživanje elementa po vrednosti — O(n), jer je potrebno proći kroz listu.

Dakle, osnovne operacije zahtevaju linearnu vremensku složenost ako nemamo direktan pristup potrebnom čvoru. To je posledica sekvencijalne prirode povezanih listića.