Ποια είναι η χρονική πολυπλοκότητα της προσθήκης ενός νέου στοιχείου στο τέλος μιας απλής συνδεδεμένης λίστας;

Η χρονική πολυπλοκότητα της προσθήκης ενός νέου στοιχείου στο τέλος μιας απλής συνδεδεμένης λίστας εξαρτάται από το αν η λίστα έχει δείκτη στο τελευταίο στοιχείο (ουρά).

• Αν υπάρχει δείκτης στην ουρά, η προσθήκη γίνεται σε 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).