Sadə əlaqəli siyahının sonuna yeni element əlavə etməyin vaxt mürəkkəbliyi nədir?

Sadə əlaqəli siyahının sonuna yeni element əlavə etmənin vaxt mürəkkəbliyi siyahının sonuncu elementə (quyruq) işarəçisinin olub-olmamasından asılıdır.

• Əgər quyruğa işarəçi varsa, əlavə O(1) vaxtında həyata keçirilir, çünki birbaşa sonuncu elementə müraciət edib yeni element əlavə etmək mümkündür.
• Əks halda, bütün siyahını başdan sona qədər keçmək lazımdır, bu da O(n) vaxt alır, burada n siyahıdakı elementlərin sayıdır.

Quyruğa işarəçi ilə nümunə:

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

Burada, əlavə etmə əməliyyatı sabit vaxtda, yəni O(1), həyata keçirilir.