Bağlı listenin içine ekleme, silme ve arama işlemlerinin zaman karmaşıklığı nasıl değerlendirilir?

Bağlı listenin işlemlerinin zaman karmaşıklığı, tam olarak ne yaptığımıza ve ihtiyaç duyulan öğeye erişimimiz olup olmadığına bağlıdır:

• Ekleme:

  • Listenin başına — O(1), çünkü bağlantıları değiştirmek yeterlidir.
  • Tek yönlü bağlı listenin sonuna — O(n), tüm listeyi dolaşmak gerekir.
  • Sonuna gösterge ile — O(1).
  • Rastgele bir yere (indeks veya değere göre) — O(n), konumu bulmak gerekir.

• Silme:

  • İlk öğeyi silmek — O(1).
  • Değere veya indekse göre silmek — O(n), öğeyi ve öncesini bulmak gerekir.

• Arama:

  • Değere göre öğe arama — O(n), listeyi dolaşmak gerekir.

Bu nedenle, ana işlemler, ihtiyaç duyulan düğüme doğrudan erişim yoksa doğrusal zaman gerektirir. Bu, bağlı listenin ardışık doğasıyla ilgilidir.