Kokia yra laiko sudėtingumas pridėti naują elementą prie viengubo susietojo sąrašo pabaigos?

Pridėti naują elementą į paprastąjį susietąjį sąrašą laiko sudėtingumas priklauso nuo to, ar sąraše yra nuoroda į paskutinį elementą (uodegą).

• Jei yra nuoroda į uodegą, pridėjimas vyksta per O(1), nes galima tiesiogiai pasiekti paskutinį elementą ir pridėti naują.
• Jei nuoroda nėra, reikia pereiti visą sąrašą nuo galvos iki pabaigos, tai užtrunka O(n) laiko, kur n yra elementų skaičius sąraše.

Pavyzdys su nuoroda į uodegą:

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

Čia pridėjimas vyksta per pastovų laiką — O(1).