How to implement index-based access in a singly linked list and in an array?

Accessing elements by index in an array is very fast and simple — you can immediately refer to the desired element using the syntax $array[$index]. This is possible because arrays store elements in a contiguous block of memory.

In a singly linked list, direct access by index is not available, as elements are connected via pointers. To get an element at a specific index, you need to traverse the list from the beginning, moving from one node to the next until you reach the desired index:

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

Thus, index access in a singly linked list has a complexity of O(n), whereas in an array it is O(1).