როგორ აფასებენ ორმხრივი დაკავშირებული სიის ცენტრალურ ნაწილში ელემენტის ჩასმის ოპერაციას?

ორი მხრიდან დაკავშირებული სია ჩვეულებრივ მოითხოვს ჯერ განთავსების პოზიციის მოძიებას, შემდეგ კი მეზობელი კვანძების კავშირების შეცვლას.

ოპერაციის სირთულე:

• პოზიციის ძიება: თუ გაქვთ ბმული იმ კვანძზე, სადაც გსურთ ჩასმა, ძიება საჭირო არ არის.
• ჩასმა: მეზობელი კვანძების ბმულების შეცვლა არის ოპერაცია O(1).

თუ ჩასმის პოზიცია განსაზღვრულია ინდექსით, მაშინ უნდა გაიაროთ სია მანამდე, სანამ არ მიაღწევთ საჭირო კვანძს, რაც მოითხოვს O(n) დროს.

საჯამო:

• თუ პოზიცია ცნობილია (კვანძი ნაპოვნია) — ჩასმა O(1).
• თუ პოზიცია განსაზღვრულია ინდექსით — ძიება + ჩასმა O(n).