Cum se implementează accesul la elemente după index într-o listă simplu înlănțuită și într-un array?

Accesul la elemente după index într-un array este foarte rapid și simplu — se poate accesa direct elementul dorit folosind sintaxa $array[$index]. Acest lucru este posibil deoarece array-urile stochează elementele într-o zonă continuă de memorie.

Într-o listă simplu înlănțuită, nu există acces direct după index, deoarece elementele sunt legate prin pointeri. Pentru a obține un element cu un anumit index, trebuie să parcurgi lista de la început, trecând de la un nod la altul, până ajungi la indexul dorit:

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

Astfel, accesul pe bază de index într-o listă simplu înlănțuită are complexitatea O(n), în timp ce în array este O(1).