Qual é a complexidade temporal de adicionar um novo elemento ao final de uma lista ligada simples?

A complexidade temporal de adicionar um novo elemento ao final de uma lista ligada simples depende de ter ou não um ponteiro para o último elemento (cauda).

• Se houver um ponteiro para a cauda, a adição ocorre em O(1), pois pode-se acessar diretamente o último elemento e adicionar um novo.
• Se não houver ponteiro, é necessário percorrer toda a lista desde a cabeça até o final, o que leva O(n) tempo, onde n é o número de elementos na lista.

Exemplo com ponteiro para a cauda:

class Node {
    var value: Int
    var next: Node?
    init(value: Int) {
        self.value = value
    }
}

class LinkedList {
    var head: Node?
    var tail: Node?

    func append(_ value: Int) {
        let newNode = Node(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
    }
}

Aqui, a adição ocorre em tempo constante O(1).