Мӯҳлати вақт барои илова кардани унсури нав ба охири рӯйхати пайвастаи оддӣ чӣ қадар аст?

Ҷасади вақти илова кардани унсури нав ба охири рӯйхати пайвастаи оддӣ вобаста аст, ки оё рӯйхат ишорагари ба охир (қуттӣ) дорад ё не.

• Агар ишорагари ба қуттӣ вуҷуд дошта бошад, илова кардан дар 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) сурат мегирад.