რა არის დროის სირთულე ერთმხრივი დაკავშირებული სიის ბოლოს ახალი ელემენტის დამატებისას?

ახალი ელემენტის დამატების დროის სირთულე მარტივი დაკავშირებული სიის ბოლოს დამოკიდებულია იმაზე, აქვს თუ არა სიის ბოლო ელემენტზე (ხახუნზე) მიმთითებელი.

• თუ მიმთითებელი ხახუნზე არსებობს, დამატება ხდება 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).