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

Σε μια απλή συνδεδεμένη λίστα, οι λειτουργίες έχουν τις ακόλουθες χρονικές πολυπλοκότητες:

• Εισαγωγή:

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

• Διαγραφή:

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

• Αναζήτηση:

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

Έτσι, οι λειτουργίες εισαγωγής και διαγραφής στην αρχή της λίστας είναι πολύ γρήγορες, ενώ οι υπόλοιπες απαιτούν γραμμικό χρόνο λόγω της ανάγκης διασχίσεως της λίστας.