Как да реализираме достъпа до елементи по индекс в едносвързан списък и в масив?

Достъпът до елементи по индекс в масив е много бърз и лесен — можете директно да се обърнете към желания елемент, използвайки синтаксиса $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).