Kāda ir laika sarežģītība vienvirziena saistītā saraksta elementu ievietošanai, dzēšanai un meklēšanai?

Vienkāršas saistītas saraksts operācijas ir šādas laika sarežģītības:

• Ievietošana:

  • Sākuma vietā — O(1), jo pietiek mainīt galvas norādītāju.
  • Beigās vai jebkurā vietā — O(n), jo ir nepieciešams pārlūkot sarakstu līdz vēlamajai pozīcijai.

• Dzēšana:

  • Pirmā elementa dzēšana — O(1).
  • Elementa dzēšana pēc vērtības vai pozīcijas — O(n), jo ir jāatrod elements un iepriekšējais mezgls.

• Meklēšana:

  • Elementa meklēšana pēc vērtības — O(n), jo ir jāpārlūko saraksts secīgi.

Tādējādi, operācijas, kas veicamas sākumā, ir ļoti ātras, bet pārējās prasa lineāru laiku, jo ir nepieciešams pārlūkot sarakstu.