Yagona bog'langan ro'yxatda elementlarni qo'shish, o'chirish va qidirish operatsiyalarining vaqt murakkabligi qanday?

Yagona bog'langan ro'yxatda operatsiyalar quyidagi vaqt murakkabligiga ega:

• Qo'shish:

  • Ro'yxat boshiga — O(1), chunki faqat bosh ko'rsatkichini o'zgartirish kifoya.
  • Oxiriga yoki istalgan joyga — O(n), chunki kerakli pozitsiyaga qadar ro'yxatni o'tish kerak.

• O'chirish:

  • Birinchi elementni o'chirish — O(1).
  • Qiymat yoki pozitsiyaga ko'ra elementni o'chirish — O(n), chunki element va oldingi tugunni topish kerak.

• Qidirish:

  • Qiymat bo'yicha elementni qidirish — O(n), chunki ro'yxatni ketma-ket o'tish kerak.

Shuning uchun, ro'yxat boshidagi qo'shish va o'chirish operatsiyalari juda tez, qolganlari esa ro'yxatni o'tish zarurligi sababli chiziqli vaqt oladi.