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

Η πρόσβαση σε στοιχεία με δείκτη σε έναν πίνακα είναι πολύ γρήγορη και απλή — μπορείτε να προσεγγίσετε άμεσα το επιθυμητό στοιχείο χρησιμοποιώντας τη σύνταξη $array[$index]. Αυτό είναι εφικτό επειδή οι πίνακες αποθηκεύουν τα στοιχεία σε μια συνεχόμενη περιοχή μνήμης.

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

function getElementAt($head, $index) {
    $current = $head;
    $count = 0;
    while ($current !== null) {
        if ($count === $index) {
            return $current->value;
        }
        $current = $current->next;
        $count++;
    }
    return null; // δείκτης εκτός εύρους
}

Έτσι, η πρόσβαση με δείκτη σε μια απλή συνδεδεμένη λίστα έχει πολυπλοκότητα O(n), ενώ σε έναν πίνακα — O(1).