Mekkora az időbeli komplexitás egy új elem hozzáadása egy egyszemélyes láncolt listához?

Egy egyszerű láncolt lista új elemének végéhez való hozzáadásának időkomplexitása attól függ, hogy van-e a listának mutatója a legutolsó elemre (farokra).

• Ha van mutató a farokra, akkor a hozzáadás O(1) idő alatt történik, mivel közvetlenül elérhető a legutolsó elem, és hozzá lehet adni egy újat.
• Ha nincs mutató, akkor végig kell járni az egész listát a fejétől a végéig, ami O(n) időt vesz igénybe, ahol n a lista elemeinek száma.

Példa mutatóval a farokra:

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

Itt a hozzáadás konstans időben, azaz O(1) történik.