რა არის დაკავშირებული სიის ბოლოს ელემენტის დამატების ოპერაციის დროითი სირთულე?

დაკავშირებული სიის ბოლო ელემენტის დამატების ოპერაციის დროის სირთულე დამოკიდებულია იმაზე, აქვს თუ არა სიის ბოლო ელემენტზე მიმთითებელი.

• თუ არსებობს მიმთითებელი (tail), დამატება ხდება O(1) დროს, რადგან შეიძლება დაუყოვნებლივ დაამატოთ ახალი ელემენტი tail-ის შემდეგ.
• თუ მიმთითებელი tail-ზე არ არის, საჭიროა მთელი სია გავიაროთ, რათა მივაგნოთ ბოლო ელემენტი, და მაშინ სირთულე იქნება O(n), სადაც n — ელემენტების რაოდენობა სიის.

მაგალითი tail-ის მიმთითებლით:

class LinkedList {
    Node head;
    Node tail;

    void addLast(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }
}