Əgər artıq doldurulmuş massiviniz varsa, əlaqəli siyahının ortasına element əlavə etmənin vaxt mürəkkəbliyi nədir?

Əgər doldurulmuş bir massiviniz varsa və əlaqəli siyahının ortasına element əlavə etmək istəyirsinizsə, əvvəlcə siyahıda əlavə etmə mövqeyini tapmalısınız. Əlaqəli siyahıda element axtarma vaxt mürəkkəbliyi O(n)-dir, çünki istədiyiniz mövqeyə qədər elementləri keçməlisiniz.

Mövqe tapıldıqdan sonra, elementin əlaqəli siyahıya əlavə edilməsi O(1) vaxt alır, çünki sadəcə əlaqələri yenidən təyin etmək kifayətdir.

Beləliklə, massiv (indeksi tez tapmağa kömək edə bilən, lakin siyahının düyününü yox) mövcud olduqda, əlaqəli siyahının ortasına element əlavə etmənin ümumi vaxt mürəkkəbliyi O(n) olacaq, çünki düyünü axtarma lineer vaxt alır.

Əgər əlaqəli siyahının düyünlərinə istinad edən bir massiviniz varsa (məsələn, siyahı elementlərinə göstəricilərin massivi), onda əlavə etmə O(1) vaxtında həyata keçirilə bilər, çünki lazım olan düyünü dərhal əldə edirsiniz.

Nümunə:

// Tutaq ki, əlaqəli siyahı və düyünlər massivimiz var
Node[] düyünMassivi = ...; // əlaqəli siyahının düyünləri massiv
int əlavəİndeksi = düyünMassivi.length / 2;
Node əvvəlkiDüyün = düyünMassivi[əvvəlkiDüyün - 1];
Node yeniDüyün = new Node(dəyər);
yeniDüyün.next = əvvəlkiDüyün.next;
əvvəlkiDüyün.next = yeniDüyün;
// Əlavə O(1) vaxtında tamamlandı

Əgər düyünlər ilə massiv yoxdursa, onda siyahını istənilən mövqeyə qədər keçməlisiniz — O(n).