Каква е времевата сложност при добавяне на нов елемент в края на едносвързан списък?

Времевата сложност при добавяне на нов елемент към края на едносвързан списък зависи от това дали списъкът има указател към последния елемент (опашката).

• Ако има указател към опашката, добавянето се извършва за 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).