Hogyan valósítjuk meg az index szerinti hozzáférést egy egyszemélyes láncolt listában és egy tömbben?

A tömbben az elemekhez index szerint való hozzáférés nagyon gyors és egyszerű — közvetlenül elérheti a kívánt elemet a $array[$index] szintaxissal. Ez azért lehetséges, mert a tömbök az elemeket folyamatos memória területen tárolják.

Egy egyszerű láncolt listában nincs közvetlen index szerinti hozzáférés, mivel az elemek pointereken keresztül vannak összekapcsolva. Egy adott indexű elem eléréséhez végig kell járni a listát a kezdettől, egyik csomópontból a másikba lépve, amíg el nem éri a kívánt indexet:

function getElementAt($head, $index) {
    $current = $head;
    $count = 0;
    while ($current !== null) {
        if ($count === $index) {
            return $current->value;
        }
        $current = $current->next;
        $count++;
    }
    return null; // index kívül esik a tartományon
}

Ezért az index szerinti hozzáférés egy egyszerű láncolt listában O(n) komplexitású, míg tömbben O(1).