Kokia yra laiko sudėtingumas įterpimo, ištrynimo ir paieškos operacijoms vienpusiai susietame sąraše?

Vienkryptės sujungtosios sąrašo operacijos turi šias laiko sudėtingumo charakteristikas:

• Įterpimas:

  • Sąrašo pradžioje — O(1), nes pakanka pakeisti galvos rodyklę.
  • Pabaigoje arba bet kurioje vietoje — O(n), nes reikia pereiti per sąrašą iki norimos pozicijos.

• Ištrynimas:

  • Pirmo elemento ištrynimas — O(1).
  • Elemento ištrynimas pagal reikšmę arba poziciją — O(n), nes reikia rasti elementą ir ankstesnį mazgą.

• Paieška:

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

Todėl, įterpimo ir ištrynimo operacijos pradžioje yra labai greitos, o kitos reikalauja linijinio laiko dėl sąrašo perėjimo.