Qual é a complexidade temporal da operação de adicionar um elemento ao final de uma lista ligada?

A complexidade temporal da operação de adicionar um elemento ao final de uma lista ligada depende de ter um ponteiro para o último elemento.

• Se houver um ponteiro para o final (tail), a adição ocorre em O(1), pois pode-se adicionar imediatamente um novo elemento após o tail.
• Se não houver um ponteiro para o tail, é necessário percorrer toda a lista para encontrar o último elemento, e então a complexidade será O(n), onde n é o número de elementos na lista.

Exemplo com ponteiro para o 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;
        }
    }
}