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

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

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

Παράδειγμα με δείκτη στην ουρά:

class LinkedList {
    Node head;
    Node tail;

    void addLast(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }
}