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

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

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

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