Come accedere agli elementi per indice in una lista collegata semplice e in un array?

L'accesso agli elementi per indice in un array è molto rapido e semplice — si può accedere direttamente all'elemento desiderato usando la sintassi $array[$index]. Ciò è possibile perché gli array memorizzano gli elementi in un'area di memoria contigua.

In una lista collegata semplice, non esiste un accesso diretto per indice, poiché gli elementi sono collegati tramite puntatori. Per ottenere un elemento con un indice specifico, è necessario attraversare la lista dall'inizio, passando da un nodo all'altro, fino a raggiungere l'indice desiderato:

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

Pertanto, l'accesso per indice in una lista collegata semplice ha una complessità di O(n), mentre in un array è O(1).