Kā novērtēt saistītā saraksta elementu ievietošanas, dzēšanas un meklēšanas operāciju laika sarežģītību?

Saistīto saraksta operāciju laika sarežģītība ir atkarīga no tā, ko tieši mēs darām un vai mums ir piekļuve nepieciešamajam elementam:

• Ievietošana:

  • Sākuma sarakstā — O(1), jo pietiek mainīt saites.
  • Vienkārši saistīta saraksta beigās bez norāda uz galotni — O(n), ir jāiziet cauri visam sarakstam.
  • Beigās ar norādi uz galotni — O(1).
  • Jebkurā vietā (atbilstoši indeksam vai vērtībai) — O(n), jāatrod pozīcija.

• Dzēšana:

  • Pirmā elementa dzēšana — O(1).
  • Dzēšana pēc vērtības vai indeksa — O(n), jāatrod elements un tā priekšgājējs.

• Meklēšana:

  • Elementa meklēšana pēc vērtības — O(n), ir jāiziet cauri sarakstam.

Tādējādi galvenās operācijas prasa lineāru laiku, ja nav tiešas piekļuves nepieciešamajam mezglam. Tas ir saistīts ar saistīto sarakstu secīgo raksturu.