How does a linked list differ from an array?

A linked list differs from an array primarily in its structure and how it stores elements. In a linked list, each element is contained in a node, and each node contains a reference or pointer to the next node in the sequence. This means that nodes in a linked list do not need to be stored in contiguous memory locations; they can be located anywhere in memory, with connections established through pointers.

This structure allows for efficient insertions and deletions since modifying the list merely involves changing pointers rather than shifting elements like in an array. When new elements are added to a linked list or existing elements are removed, the only operations necessary are to adjust the pointers of the affected nodes, making these operations generally efficient.

In contrast, arrays have a fixed size and store elements in contiguous memory. This means that once an array is created, its size cannot be changed without creating a new array and copying the elements, which adds overhead. Furthermore, accessing elements in an array is typically faster due to improved locality of reference, as they are stored sequentially in memory.

Thus, the composition of nodes and the use of pointers to link them together are what fundamentally define a linked list, distinguishing it from an array.