Alohida ro'yxatning o'rtasiga element qo'shish vaqt murakkabligi qanday, agar sizda to'ldirilgan massiv bo'lsa?

Agar siz to'ldirilgan massivga egasiz va bog'langan ro'yxatning o'rtasiga element qo'shmoqchi bo'lsangiz, avvalo ro'yxatda qo'shish pozitsiyasini topishingiz kerak. Bog'langan ro'yxatda elementni qidirish vaqt murakkabligi O(n), chunki kerakli pozitsiyagacha elementlarni o'tishingiz kerak.

Pozitsiya topilgach, elementni bog'langan ro'yxatga qo'shish O(1) da amalga oshiriladi, chunki faqat havolalarni yangilash kifoya.

Shunday qilib, massiv (indeksni tezda topishga yordam beradigan, ammo ro'yxat tuguniga emas) mavjud bo'lsa, bog'langan ro'yxatning o'rtasiga element qo'shish umumiy vaqt murakkabligi O(n) bo'ladi, chunki tugunni qidirish lineer vaqt oladi.

Agar sizda bog'langan ro'yxat tug'lariga havolalarni saqlovchi massiv bo'lsa (masalan, ro'yxat elementlariga ko'rsatkichlar), unda qo'shish O(1) da amalga oshirilishi mumkin, chunki siz kerakli tugunni darhol olasiz.

Misol:

// Faraz qilaylik, bizda bog'langan ro'yxat va tugunlar massivlari bor
Node[] tugunlarMassivi = ...; // bog'langan ro'yxatning tugunlari massiv
int qo'shishIndeksi = tugunlarMassivi.length / 2;
Node oldingiTugun = tugunlarMassivi[qo'shishIndeksi - 1];
Node yangiTugun = new Node(qiymat);
yangiTugun.next = oldingiTugun.next;
oldingiTugun.next = yangiTugun;
// Qo'shish O(1) da bajarildi

Agar tugunlar bilan massiv bo'lmasa, unda ro'yxatni kerakli pozitsiyaga qadar o'tishingiz kerak — O(n).