Kuidas hinnata seotud nimekirja operatsioonide sisestamise, kustutamise ja otsimise ajakulut?

Seotud nimekirja operatsioonide ajamõõt sõltub sellest, mida täpselt teeme ja kas meil on juurdepääs vajalikele sõlmedele:

• Lisamine:

  • Nimekirja alguses — O(1), kuna piisab viidete muutmisest.
  • Ühe suunaga seotud nimekirja lõpus ilma viiteta lõppu — O(n), tuleb kogu nimekiri läbi käia.
  • Lõpus viitega lõppu — O(1).
  • Igas asukohas (indeksi või väärtuse järgi) — O(n), kuna tuleb leida asukoht.

• Kustutamine:

  • Esimese elemendi kustutamine — O(1).
  • Väärtuse või indeksi järgi kustutamine — O(n), tuleb leida element ja selle eelkäija.

• Otsing:

  • Elementi otsimine väärtuse järgi — O(n), kuna tuleb nimekiri läbi käia.

Seega nõuavad peamised operatsioonid lineaarset aega, kui meil ei ole otsest juurdepääsu vajalikele sõlmedele. See tuleneb seotud nimekirjade järjestuslikust olemusest.