Aká je časová zložitosť pridania nového prvku na koniec jednoduchej spájanej zoznamu?

Časová zložitosť pridania nového prvku na koniec jednoducho spojeného zoznamu závisí od toho, či zoznam má ukazovateľ na posledný prvok (chvost).

• Ak existuje ukazovateľ na chvost, pridanie prebieha v O(1), pretože sa môže priamo dostať k poslednému prvku a pridať nový.
• Ak ukazovateľ neexistuje, je potrebné prejsť celý zoznam od hlavy až do konca, čo trvá O(n) času, kde n je počet prvkov v zozname.

Príklad s ukazovateľom na chvost:

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

Tu, pridanie prebieha v konštantnom čase O(1).