Hoe implementeer je toegang tot elementen op index in een enkelvoudige gekoppelde lijst en in een array?

Toegang tot elementen op index in een array is zeer snel en eenvoudig — je kunt direct naar het gewenste element verwijzen met de syntax $array[$index]. Dit is mogelijk omdat arrays de elementen opslaan in een aaneengesloten geheugenruimte.

In een enkelvoudig gekoppelde lijst is er geen directe toegang op index, omdat de elementen via pointers verbonden zijn. Om een element met een bepaalde index te krijgen, moet je de lijst vanaf het begin doorlopen, van de ene naar de andere knoop, totdat je de gewenste index bereikt:

function getElementAt($head, $index) {
    $current = $head;
    $count = 0;
    while ($current !== null) {
        if ($count === $index) {
            return $current->value;
        }
        $current = $current->next;
        $count++;
    }
    return null; // index buiten bereik
}

Dus, toegang op index in een enkelvoudige gekoppelde lijst heeft een complexiteit van O(n), terwijl in een array het O(1) is.