Como determinar o tempo gasto ao adicionar um elemento a uma lista ligada?

O tempo necessário para adicionar um elemento a uma lista ligada depende exatamente de onde o elemento é adicionado:

• Se a adição ocorre no início da lista (cabeça), a operação é O(1), pois basta reatribuir os ponteiros.
• Se a adição ocorre no final da lista (cauda) e você tem uma referência ao último elemento, também é O(1).
• Se precisar adicionar um elemento em uma posição arbitrária por índice, primeiro é necessário percorrer a lista até ao local desejado, o que leva O(n), onde n é o número de elementos até essa posição.

Exemplo de adição no início de uma lista ligada simples em Java:

class No {
    int valor;
    No proximo;
    No(int val) { valor = val; }
}

class ListaLigada {
    No cabeca;

    void adicionarNoInicio(int val) {
        No novoNo = new No(val);
        novoNo.proximo = cabeca;
        cabeca = novoNo;
    }
}

Aqui, a operação adicionarNoInicio é O(1).