¿Cuál es la complejidad temporal de agregar un nuevo elemento al final de una lista enlazada simple?

La complejidad temporal de agregar un nuevo elemento al final de una lista enlazada simple depende de si la lista tiene un puntero al último elemento (cola).

• Si hay un puntero a la cola, la adición se realiza en O(1), ya que se puede acceder directamente al último elemento y agregar uno nuevo.
• Si no hay puntero, es necesario recorrer toda la lista desde la cabeza hasta el final, lo que lleva O(n) tiempo, donde n es la cantidad de elementos en la lista.

Ejemplo con puntero a la cola:

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

Aquí, la adición se realiza en tiempo constante O(1).