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

Временная сложность добавления нового элемента в конец односвязного списка зависит от того, есть ли у списка указатель на последний элемент (хвост).

• Если указатель на хвост есть, то добавление происходит за 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).