Jaka jest złożoność czasowa operacji dodania elementu na koniec listy powiązanej?

Złożoność czasowa operacji dodawania elementu na koniec listy powiązanej zależy od tego, czy lista ma wskaźnik na ostatni element.

• Jeśli istnieje wskaźnik na ogon (tail), dodanie odbywa się w O(1), ponieważ można od razu dodać nowy element za ogonem.
• Jeśli wskaźnik na ogon nie istnieje, trzeba przejść przez całą listę, aby znaleźć ostatni element, a wtedy złożoność będzie O(n), gdzie n to liczba elementów na liście.

Przykład z wskaźnikiem na ogon:

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