Kaip pasiekti elementus pagal indeksą vienkryptėje sąraše ir masyve?

Prieiga prie elementų pagal indeksą masyve yra labai greita ir paprasta — galima tiesiogiai kreiptis į norimą elementą naudojant sintaksę $array[$index]. Tai įmanoma dėl to, kad masyvai saugo elementus nuoseklioje atminties srityje.

Vienkryptės susietosios sąraše nėra tiesioginės prieigos pagal indeksą, nes elementai yra susieti per rodykles. Norint gauti elementą su tam tikru indeksu, reikia pereiti per sąrašą nuo pradžios, pereinant iš vieno mazgo į kitą, kol pasieksite norimą indeksą:

function getElementAt($head, $index) {
    $current = $head;
    $count = 0;
    while ($current !== null) {
        if ($count === $index) {
            return $current->value;
        }
        $current = $current->next;
        $count++;
    }
    return null; // indeks už diapazono ribų
}

Taigi, prieiga pagal indeksą vienkryptėje susietoje sąraše turi sudėtingumą O(n), o masyve — O(1).