Ποια είναι η ασυμπτωτική πολυπλοκότητα των λειτουργιών με στοιχεία στη λίστα;

Εξαρτάται από τον τύπο της λίστας και την λειτουργία.

Γενικά, λαμβάνονται υπόψη οι ακόλουθοι τύποι λιστών:

• Μονή σύνδεση λίστα
• Διπλή σύνδεση λίστα
• Πίνακας (ως ειδική περίπτωση της λίστας)

Ενέργειες:

• Πρόσβαση μέσω δείκτη
• Εισαγωγή
• Διαγραφή
• Αναζήτηση τιμής

Ενέργεια	Μονή σύνδεση λίστα	Διπλή σύνδεση λίστα	Πίνακας
Πρόσβαση μέσω δείκτη	O(n)	O(n)	O(1)
Εισαγωγή	O(1) (στην αρχή)	O(1) (στην αρχή/τέλος)	O(n)
Διαγραφή	O(n)	O(n)	O(n)
Αναζήτηση τιμής	O(n)	O(n)	O(n)

Επεξηγήσεις:

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

Λεπτομέρειες:

• Σε μια μονή σύνδεση λίστα: Εισαγωγή στην αρχή - O(1). Εισαγωγή στο τέλος ή εισαγωγή/διαγραφή με δείκτη απαιτεί διαδρομή μέχρι το επιθυμητό στοιχείο, που δίνει O(n).
• Σε μια διπλή σύνδεση λίστα: Εισαγωγή στην αρχή και στο τέλος - O(1). Εισαγωγή/διαγραφή σε μια δεδομένη θέση - O(1), αλλά η αναζήτηση αυτού του κόμβου με τιμή ή δείκτη - O(n).
• Σε έναν πίνακα: Πρόσβαση μέσω δείκτη - O(1). Εισαγωγή ή διαγραφή στο μέσο του πίνακα απαιτεί μετακίνηση στοιχείων, που δίνει O(n). Εισαγωγή/διαγραφή στο τέλος, αν υπάρχει διαθέσιμη χωρητικότητα (π.χ. σε std::vector με ορισμένη χωρητικότητα), μπορεί να είναι κατά μέσο όρο O(1), αλλά στην χειρότερη περίπτωση (ανακατανομή) O(n).