Milline on aja keerukus lisada uus element üheksaküljelisse ühendatud nimekirja lõppu?

Lihtsa ühendatud nimekirja uue elemendi lisamise ajakompleksus sõltub sellest, kas nimekirjal on viit viimasele elemendile (saba).

• Kui viit saba olemas, toimub lisamine O(1) ajal, kuna saab otse jõuda viimase elemendini ja lisada uue.
• Kui viit puudub, tuleb kogu nimekiri läbi käia peast lõpuni, mis võtab aega O(n), kus n on nimekirja elementide arv.

Näide viitega sabale:

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

Siin lisamine toimub konstantsel ajal — O(1).