Qoşulmuş siyahıda elementlərin əlavə edilməsi, silinməsi və axtarış əməliyyatlarının vaxt mürəkkəbliyi necə qiymətləndirilir?

Bağlı siyahıda əməliyyatların vaxt mürəkkəbliyi tam olaraq nə etdiyimizə və lazım olan elementə çıxışımız olub-olmamasına bağlıdır:

• Əlavə etmə:

  • Siyahının əvvəlinə — O(1), çünki əlaqələri dəyişmək kifayətdir.
  • Tək yönlü bağlı siyahının sonuna — O(n), bütün siyahını keçmək lazımdır.
  • Sonuna göstərici ilə — O(1).
  • İstənilən yerə (indeks və ya dəyərə görə) — O(n), mövqeyi tapmaq lazımdır.

• Silinmə:

  • Birinci elementi silmək — O(1).
  • Dəyər və ya indeksə görə silmək — O(n), elementi və onun əvvəlcisini tapmaq lazımdır.

• Axtarış:

  • Dəyərə görə elementi tapmaq — O(n), siyahını keçmək lazımdır.

Buna görə, əsas əməliyyatlar, lazım olan düyünə birbaşa çıxış yoxdursa, xətti vaxt tələb edir. Bu, bağlı siyahıların ardıcıl təbiətindən irəli gəlir.