Kaip įvertinti susietojo sąrašo įterpimo, ištrynimo ir paieškos operacijų laiko sudėtingumą?

Sujungto sąrašo operacijų laiko sudėtingumas priklauso nuo to, ką tiksliai darome ir ar turime prieigą prie reikalingo elemento:

• Įterpimas:

  • Sąrašo pradžioje — O(1), nes pakanka pakeisti nuorodas.
  • Viengubo sujungto sąrašo pabaigoje be nuorodos į galą — O(n), reikia pereiti visą sąrašą.
  • Pabaigoje su nuoroda į galą — O(1).
  • Bet kurioje vietoje (pagal indeksą ar reikšmę) — O(n), nes reikia rasti poziciją.

• Šalinimas:

  • Pirmo elemento šalinimas — O(1).
  • Pagal reikšmę ar indeksą — O(n), nes reikia rasti elementą ir jo priešą.

• Paieška:

  • Elemento paieška pagal reikšmę — O(n), nes reikia pereiti sąrašą.

Todėl pagrindinės operacijos reikalauja linijinio laiko, jei nėra tiesioginės prieigos prie reikalingo mazgo. Tai yra susiję su sujungtų sąrašų sekine prigimtimi.