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

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

• Εισαγωγή:

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

• Διαγραφή:

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

• Αναζήτηση:

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

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