Ի՞նչ է ժամանակային բարդությունը միակողմանի կապակցված ցանկում տարրեր ավելացնելու, հեռացնելու և որոնելու գործողությունների ժամանակ:

Միակ կապակցված ցանկում գործողությունները ունեն հետևյալ ժամանակային բարդությունները՝

• Ներմուծում՝

  • Ցանկի սկզբում — O(1), քանի որ բավարար է փոխել գլխի ցուցիչը:
  • Սկզբի կամ ցանկացած վայրում — O(n), քանի որ անհրաժեշտ է անցնել ցանկը մինչև ցանկալի դիրքը:

• Հեռացում՝

  • Առաջին տարրն հեռացնելը — O(1):
  • Տարրն ըստ արժեքի կամ դիրքի — O(n), քանի որ անհրաժեշտ է գտնել տարրն ու նախորդ հանգույցը:

• Փնտրում՝

  • Տարրն ըստ արժեքի — O(n), քանի որ անհրաժեշտ է անցնել ցանկը հերթականությամբ:

Այսպիսով, ցանկի սկզբում ավելացնելը և հեռացնելը շատ արագ են, մյուսները պահանջում են գծային ժամանակ, քանի որ անհրաժեշտ է անցնել ցանկը։