Introduction to Linked Lists

At this stage, arrays are an established data structure. An array stores elements in contiguous memory locations, enabling constant-time index-based access. To access the fifth element, the system computes its memory address and retrieves it directly, without accessing preceding elements.

This speed of access comes with a constraint: all elements must occupy a single, unbroken block of memory, laid out side by side. That constraint is what gives arrays their strength in access, and also what creates their most significant limitations.

Limitations of arrays

When an array needs to change its structure, the contiguous memory requirement becomes a burden.

• Inserting an element in the middle of an array means every element after the insertion point must be shifted one position forward to make room. Deleting an element from the middle means every element after it must be shifted back. For large arrays, these shifts are expensive.

• When a dynamic array runs out of allocated space, and a new element needs to be added, the entire array must be moved. A new, larger block of contiguous memory is allocated, all existing elements are copied into it, and the old block is released. This is an $O(n)$ operation that happens periodically as the array grows.

• Finally, because all elements must occupy ...