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

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

• Αν πρέπει να διαγράψουμε ένα στοιχείο, γνωρίζοντας μόνο την κεφαλή της λίστας, πρέπει πρώτα να διασχίσουμε τη λίστα για να βρούμε το στοιχείο και τον προηγούμενο κόμβο του. Αυτό παίρνει O(n) χρόνο, όπου n είναι ο αριθμός των στοιχείων στη λίστα.
• Αν έχουμε δείκτη στον προηγούμενο κόμβο (ή στο ίδιο το στοιχείο προς διαγραφή, αν είναι το πρώτο), η διαγραφή γίνεται σε O(1), καθώς αρκεί να επαναρυθμίσουμε τις συνδέσεις.

Γενικά, η διαγραφή ενός στοιχείου σε μια απλή συνδεδεμένη λίστα είναι μια λειτουργία με χρονική πολυπλοκότητα O(n).