Koja je vremenska složenost prilikom izvršavanja operacija umetanja, brisanja i pretraživanja elemenata u jednostruko povezanoj listi?

U jednostruko povezanoj listi operacije imaju sledeće vremenske složenosti:

• Umetanje:

  • Na početak liste — O(1), jer je dovoljno promeniti pokazivač glave.
  • Na kraj ili na proizvoljno mesto — O(n), jer je potrebno proći kroz listu do željene pozicije.

• Brisanje:

  • Brisanje prvog elementa — O(1).
  • Brisanje elementa po vrednosti ili poziciji — O(n), jer je potrebno pronaći element i prethodni čvor.

• Pretraživanje:

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

Dakle, operacije umetanja i brisanja na početku liste su veoma brze, dok ostale zahtevaju linearno vreme zbog potrebe da prođemo kroz listu.