Como implementar o acesso a elementos por índice numa lista ligada simples e num array?

O acesso aos elementos por índice num array é muito rápido e simples — pode-se aceder imediatamente ao elemento desejado usando a sintaxe $array[$índice]. Isto é possível porque os arrays armazenam os elementos numa região contínua de memória.

Num lista ligada simples, não há acesso direto por índice, pois os elementos estão ligados através de ponteiros. Para obter um elemento com um índice específico, é necessário percorrer a lista desde o início, passando de um nó para outro, até chegar ao índice desejado:

function getElementAt($head, $index) {
    $current = $head;
    $count = 0;
    while ($current !== null) {
        if ($count === $index) {
            return $current->value;
        }
        $current = $current->next;
        $count++;
    }
    return null; // índice fora do intervalo
}

Assim, o acesso por índice numa lista ligada simples tem complexidade O(n), enquanto num array é O(1).