Kako pristupiti elementima po indeksu u jednostruko povezanoj listi i nizu?

Pristup elementima po indeksu u nizu je veoma brz i jednostavan — možete direktno da se obratite željenom elementu koristeći sintaksu $array[$index]. To je moguće zato što nizovi čuvaju elemente u kontinuiranom delu memorije.

U jednostruko povezanoj listi, nema direktnog pristupa po indeksu, jer su elementi povezani putem pokazivača. Da biste dobili element sa određenim indeksom, morate proći kroz listu od početka, prelazeći sa jednog čvora na drugi, dok ne stignete do željenog indeksa:

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

Tako, pristup po indeksu u jednostruko povezanoj listi ima složenost O(n), dok je u nizu — O(1).