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

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

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

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

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