Jak získat přístup k prvkům podle indexu v jednoduše spojeném seznamu a v poli?

Přístup k prvkům podle indexu v poli je velmi rychlý a jednoduchý — můžete přímo přistupovat k požadovanému prvku pomocí syntaxe $array[$index]. To je možné díky tomu, že pole ukládají prvky v souvislé oblasti paměti.

U jednoduše spojeného seznamu neexistuje přímý přístup podle indexu, protože prvky jsou spojeny ukazateli. Pro získání prvku s určitým indexem je třeba projít seznam od začátku, přecházejíc z jednoho uzlu na druhý, dokud nedosáhnete požadovaného indexu:

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
}

Tímto způsobem má přístup podle indexu v jednoduše spojeném seznamu složitost O(n), zatímco v poli je O(1).