Ako implementovať prístup k prvkom podľa indexu v jednoduchej spájanej zozname a v poli?

Prístup k prvkom podľa indexu v poli je veľmi rýchly a jednoduchý — môžete priamo pristupovať k požadovanému prvku pomocou syntaxe $array[$index]. To je možné, pretože polia ukladajú prvky v súvislej oblasti pamäte.

V jednoducho prepojenej zozname neexistuje priame prístupovanie podľa indexu, pretože prvky sú prepojené ukazovateľmi. Na získanie prvku s určitým indexom je potrebné prejsť zoznam od začiatku, prechádzaním z jedného uzla na druhý, až kým nedosiahnete požadovaný index:

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

Takto má prístup podľa indexu v jednoducho prepojenej zozname zložitosť O(n), zatiaľ čo v poli je O(1).