Qual è la complessità temporale di aggiungere un nuovo elemento alla fine di una lista collegata semplice?

La complessità temporale dell'aggiunta di un nuovo elemento alla fine di una lista collegata semplice dipende dalla presenza di un puntatore all'ultimo elemento (coda).

• Se esiste un puntatore alla coda, l'aggiunta avviene in O(1), poiché si può accedere direttamente all'ultimo elemento e aggiungere un nuovo elemento.
• Se non c'è un puntatore, è necessario attraversare tutta la lista dalla testa alla fine, il che richiede O(n) tempo, dove n è il numero di elementi nella lista.

Esempio con puntatore alla coda:

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

Qui, l'aggiunta avviene in tempo costante O(1).