¿Cómo acceder a los elementos por índice en una lista enlazada simple y en un array?

El acceso a los elementos por índice en un array es muy rápido y sencillo: se puede acceder directamente al elemento deseado usando la sintaxis $array[$índice]. Esto es posible porque los arrays almacenan los elementos en una región continua de memoria.

En una lista enlazada simple, no hay acceso directo por índice, ya que los elementos están conectados mediante punteros. Para obtener un elemento con un índice determinado, es necesario recorrer la lista desde el principio, pasando de un nodo a otro, hasta llegar al índice deseado:

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

Por lo tanto, el acceso por índice en una lista enlazada simple tiene una complejidad de O(n), mientras que en un array es O(1).