Ինչ է ժամանակային բարդությունը նոր տարր ավելացնելու համար միակողմանի կապակցված ցանկի վերջում?

Նոր տարր ավելացնելու ժամանակային բարդությունը պարզ կապակցված ցանկի վերջում կախված է նրանից, կա արդյոք ցանկում վերջին տարրին (փորոց) ցույց տվող ցուցիչ:

• Եթե կա ցուցիչ փորոցին, ապա ավելացումը կատարվում է O(1) ժամանակում, քանի որ կարելի է անմիջապես հասնել վերջին տարրին և ավելացնել նորին:
• Եթե չկա ցուցիչ, ապա անհրաժեշտ է անցնել ամբողջ ցանկը գլխից մինչև վերջ, ինչը ժամանակ է պահանջում O(n), որտեղ n — տարրերի քանակն է:

Օրինակ՝ ցուցիչով փորոցին:

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

Այստեղ ավելացումը կատարվում է հաստատուն ժամանակով՝ O(1):