Jaká je časová složitost přidání nového prvku na konec jednoduše spojeného seznamu?

Časová složitost přidání nového prvku na konec jednoduše spojovaného seznamu závisí na tom, zda seznam obsahuje ukazatel na poslední prvek (ocas).

• Pokud ukazatel na ocas existuje, přidání probíhá v O(1), protože se může přímo dostat k poslednímu prvku a přidat nový.
• Pokud ukazatel neexistuje, je třeba projít celý seznam od hlavy až do konce, což zabere O(n) času, kde n je počet prvků v seznamu.

Příklad s ukazatelem na ocas:

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

Zde se přidání provádí v konstantním čase O(1).