Wie greift man auf Elemente nach Index in einer einfach verketteten Liste und in einem Array zu?

Der Zugriff auf Elemente nach Index in einem Array ist sehr schnell und einfach — man kann direkt auf das gewünschte Element zugreifen, indem man die Syntax $array[$index] verwendet. Dies ist möglich, weil Arrays die Elemente in einem zusammenhängenden Speicherbereich speichern.

In einer einfach verketteten Liste gibt es keinen direkten Zugriff nach Index, da die Elemente durch Zeiger verbunden sind. Um ein Element mit einem bestimmten Index zu erhalten, muss man die Liste vom Anfang an durchlaufen, von einem Knoten zum nächsten, bis man den gewünschten Index erreicht:

function getElementAt($head, $index) {
    $current = $head;
    $count = 0;
    while ($current !== null) {
        if ($count === $index) {
            return $current->value;
        }
        $current = $current->next;
        $count++;
    }
    return null; // Index außerhalb des Bereichs
}

Daher hat der Zugriff nach Index in einer einfach verketteten Liste die Komplexität O(n), während er in einem Array O(1) ist.