Wat is de tijdcomplexiteit van het toevoegen van een nieuw element aan het einde van een enkelvoudige gekoppelde lijst?

De tijdscomplexiteit van het toevoegen van een nieuw element aan het einde van een enkelvoudig gekoppelde lijst hangt af van of de lijst een pointer naar het laatste element (staart) heeft.

• Als er een pointer naar de staart is, gebeurt het toevoegen in O(1), omdat je direct naar het laatste element kunt gaan en een nieuw kunt toevoegen.
• Als er geen pointer is, moet je de hele lijst vanaf het hoofd tot het einde doorlopen, wat O(n) tijd kost, waarbij n het aantal elementen in de lijst is.

Voorbeeld met een pointer naar de staart:

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

Hier gebeurt het toevoegen in constante tijd O(1).