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

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

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

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

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

Παράδειγμα:

// Υποθέτουμε ότι έχουμε μια συνδεδεμένη λίστα και έναν πίνακα κόμβων
Node[] πίνακαςΚόμβων = ...; // πίνακας κόμβων της συνδεδεμένης λίστας
int δείκτηςΕισαγωγής = πίνακαςΚόμβων.length / 2;
Node προηγούμενοςΚόμβος = πίνακαςΚόμβων[δείκτηςΕισαγωγής - 1];
Node νέοςΚόμβος = new Node(τιμή);
νέοςΚόμβος.next = προηγούμενοςΚόμβος.next;
προηγούμενοςΚόμβος.next = νέοςΚόμβος;
// Η εισαγωγή ολοκληρώθηκε σε O(1)

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