რამდენი დრო სჭირდება ელემენტის ჩასმას კავშირულ სიაში, თუ თქვენ უკვე გაქვთ სავსე მასივი?

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

მიუხედავად იმისა, რომ პოზიცია იპოვეთ, ელემენტის ჩასმა დაკავშირებულ სიაში ხდება O(1)-ში, რადგან საკმარისია გადამისამართოთ ბმულები.

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

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

მაგალითი:

// დავუშვათ, რომ გვაქვს დაკავშირებული სია და ნაჭრების მასივი
Node[] ნაჭრებისმასივი = ...; // დაკავშირებული სიის ნაჭრების მასივი
int ჩასმისინდექსი = ნაჭრებისმასივი.length / 2;
Node წინამორბედინაჭერი = ნაჭრებისმასივი[ჩასმისინდექს - 1];
Node ახალინაჭერი = new Node(მნიშვნელობა);
ახალინაჭერი.next = წინამორბედინაჭერი.next;
წინამორბედინაჭერი.next = ახალინაჭერი;
// ჩასმა შესრულდა O(1)-ში

თუ ნაჭრების მასივი არ გაქვთ, მაშინ უნდა გაიაროთ სია საჭირო პოზიციამდე — O(n).