В массиве доступ к элементам по индексу очень быстрый и простой — можно сразу обратиться к нужному элементу, используя синтаксис $array[$index]. Это возможно благодаря тому, что массивы хранят элементы в непрерывной области памяти.

В односвязном списке прямого доступа по индексу нет, так как элементы связаны через указатели. Чтобы получить элемент с определённым индексом, нужно пройтись по списку от начала, переходя от одного узла к другому, пока не дойдём до нужного индекса:

function getElementAt($head, $index) {
    $current = $head;
    $count = 0;
    while ($current !== null) {
        if ($count === $index) {
            return $current->value;
        }
        $current = $current->next;
        $count++;
    }
    return null; // индекс вне диапазона
}

Таким образом, доступ по индексу в односвязном списке имеет сложность O(n), а в массиве — O(1).

Как реализовать доступ к элементам по индексу в односвязном списке и в массиве?