Jaka jest złożoność czasowa dodania nowego elementu na koniec jednokierunkowej listy?

Złożoność czasowa dodania nowego elementu na koniec jednokierunkowej listy powiązanej zależy od tego, czy lista ma wskaźnik na ostatni element (ogon).

• Jeśli wskaźnik na ogon istnieje, dodanie odbywa się w O(1), ponieważ można od razu odwołać się do ostatniego elementu i dodać nowy.
• Jeśli wskaźnika nie ma, trzeba przejść całą listę od głowy do końca, co zajmuje O(n) czasu, gdzie n to liczba elementów na liście.

Przykład z wskaźnikiem na ogon:

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

Tutaj dodanie odbywa się w czasie stałym O(1).