Aká je časová zložitosť operácie pridania prvku na koniec spájanej zoznamu?

Časová zložitosť operácie pridania prvku na koniec spojeného zoznamu závisí od toho, či zoznam obsahuje ukazovateľ na posledný prvok.

• Ak je ukazovateľ na koniec (tail), pridanie prebieha v O(1), pretože ihneď môžete pridať nový prvok za tail.
• Ak ukazovateľ na tail nie je, je potrebné prejsť celý zoznam, aby ste našli posledný prvok, a potom bude zložitosť O(n), kde n je počet prvkov v zozname.

Príklad s ukazovateľom na 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;
        }
    }
}