Ինչպե՞ս է ժամանակային բարդությունը մի տարր ավելացնել կապակցված ցանկի մեջ, եթե ձեր առջև արդեն լցված զանգված կա։

Եթե ձեր ձեռքում կա լցված զանգված և ցանկանում եք ավելացնել տարր կապակցված ցանկի մեջ միջինում, նախ պետք է գտնեք ավելացման դիրքը ցանկում։ Կապակցված ցանկում տարր որոնելու ժամանակային բարդությունը՝ O(n), քանի որ պետք է անցնեք տարրերով մինչև ցանկալի դիրքը։

Երբ դիրքը գտնվի, տարր ավելացնելը կապակցված ցանկում կատարվում է՝ O(1), քանի որ բավական է ուղղել հղումները։

Այսպիսով, ընդհանուր ժամանակային բարդությունը տարր ավելացնելու համար միջինում կապակցված ցանկում՝ ունենալով զանգված (որը կարող է օգնել արագ գտնել ցուցիչը, բայց ոչ ցանկի հանգույցը), կլինի՝ O(n), քանի որ հանգույցի որոնումը ժամանակատար է։

Եթե ունեք զանգված, որը պահում է կապակցված ցանկի հանգույցների հղումները (օրինակ՝ ցուցակների ցուցիչների զանգված), ապա ավելացումը կարող է կատարվել՝ O(1), քանի որ անմիջապես ստանում եք անհրաժեշտ հանգույցը։

Օրինակ՝

// Ենթադրենք, որ ունենք կապակցված ցանկ և հանգույցների զանգված
Node[] հանգույցներ = ...; // կապակցված ցանկի հանգույցների զանգված
int ավելացմանՑուցանիշ = հանգույցներ.length / 2;
Node նախորդՀանգույց = հանգույցներ[ավելացմանՑուցանիշ - 1];
Node նորՀանգույց = new Node(արժեք);
նորՀանգույց.next = նախորդՀանգույց.next;
նախորդՀանգույց.next = նորՀանգույց;
// Ավելացումը կատարվել է՝ O(1)

Եթե չունեք հանգույցների զանգված, ապա պետք է անցնեք ցանկով մինչև ցանկալի դիրքը՝ O(n)։