Каква е времевата сложност на операцията за добавяне на елемент в края на свързания списък?

Времевата сложност на операцията за добавяне на елемент към края на свързан списък зависи от това дали списъкът има указател към последния елемент.

• Ако има указател към опашката (tail), добавянето става за O(1), тъй като може веднага да добавите нов елемент след опашката.
• Ако няма указател към опашката, трябва да преминете през целия списък, за да намерите последния елемент, и тогава сложността ще бъде O(n), където n е броят на елементите в списъка.

Пример с указател към опашката:

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;
        }
    }
}