Care este complexitatea temporală a adăugării unui nou element la sfârșitul unei liste simplu înlănțuite?

Complexitatea temporală pentru adăugarea unui element nou la sfârșitul unei liste simplu înlănțuite depinde de existența unui pointer către ultimul element (coadă).

• Dacă există un pointer către coadă, adăugarea se face în O(1), deoarece se poate accesa direct ultimul element și adăuga unul nou.
• Dacă nu există, trebuie să parcurgi întreaga listă de la cap până la sfârșit, ceea ce durează O(n) timp, unde n este numărul de elemente din listă.

Exemplu cu un pointer către coadă:

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

Aici, adăugarea se face în timp constant O(1).