Jak uzyskać dostęp do elementów według indeksu na liście jednokierunkowej i w tablicy?

Dostęp do elementów według indeksu w tablicy jest bardzo szybki i prosty — można od razu odwołać się do żądanego elementu, używając składni $array[$index]. Jest to możliwe, ponieważ tablice przechowują elementy w ciągłym obszarze pamięci.

W jednokierunkowej liście powiązanej nie ma bezpośredniego dostępu po indeksie, ponieważ elementy są połączone wskaźnikami. Aby uzyskać element o określonym indeksie, trzeba przejść przez listę od początku, przechodząc od jednego węzła do drugiego, aż dojdziemy do żądanego indeksu:

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

W ten sposób dostęp po indeksie w jednokierunkowej liście ma złożoność O(n), podczas gdy w tablicy — O(1).