Comment accéder aux éléments par index dans une liste chaînée simple et dans un tableau?

L'accès aux éléments par index dans un tableau est très rapide et simple : on peut accéder directement à l'élément souhaité en utilisant la syntaxe $array[$index]. Cela est possible car les tableaux stockent les éléments dans une zone mémoire contiguë.

Dans une liste chaînée simple, il n'y a pas d'accès direct par index, car les éléments sont liés par des pointeurs. Pour obtenir un élément à un index donné, il faut parcourir la liste depuis le début, en passant d'un nœud à l'autre, jusqu'à atteindre l'index souhaité :

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

Ainsi, l'accès par index dans une liste chaînée simple a une complexité de O(n), tandis que dans un tableau, c'est O(1).