Ինչպե՞ս որոշել միացյալ ցանկի միջինում տարր ավելացնելու գործողության ժամանակային բարդությունը։

Միացրեք տարրին միացյալ ցանկի միջինում, նախ պետք է անցնել ցանկը սկզբից մինչև անհրաժեշտ դիրքը, քանի որ միացյալ ցանկում չկա հակադարձ հղումներ կամ ուղղակի մուտք դեպի տարրեր ըստ ինդեքսի:

Միջինում միացման գործողության ժամանակային բարդությունը O(n) է, որտեղ n — մինչև տեղադրության դիրքը տարրերի քանակը։ Դա կապված է ցանկը անցնելու անհրաժեշտության հետ մինչև ցանկալի հանգույցը:

Ինքնին միացման գործընթացը (հղումների փոփոխությունը) տևում է O(1), բայց դիրքը որոնելը — O(n), հետևաբար ընդհանուր բարդությունը — O(n):