Tek bağlı listenin sonuna yeni bir öğe eklemenin zaman karmaşıklığı nedir?

Tekrar ekleme işleminin zaman karmaşıklığı, tek bağlı listenin sonuna yeni bir öğe eklenirken listenin son öğesine (kuyruk) işaretçi olup olmamasına bağlıdır.

• Eğer kuyruk işaretçisi varsa, ekleme O(1) sürede gerçekleşir, çünkü doğrudan son öğeye erişip yeni ekleyebilirsiniz.
• Eğer yoksa, listenin başından sonuna kadar tüm listeyi dolaşmanız gerekir, bu da O(n) zaman alır, burada n listedeki öğe sayısıdır.

Kuyruğa işaretçi ile örnek:

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

Burada, ekleme işlemi sabit zamanlıdır O(1).