Array vs Linked List — What's the Difference?

An array stores elements in contiguous memory with fixed-time indexed access; a linked list stores elements as separate nodes connected by pointers, allowing efficient insertion/removal but only sequential access.

Why they differ

• Arrays offer O(1) random access by index, since the memory address of any element can be calculated directly
• Linked lists offer O(1) insertion/removal at a known position (once you have a reference to it), without shifting other elements

How to choose

• Use an array when you mostly read/iterate and rarely insert or remove from the middle
• Use a linked list when you frequently insert or remove elements, especially at the beginning, and rarely need random indexed access

FAQ

Which uses memory more efficiently?

Arrays generally have less memory overhead per element, since linked lists require extra memory for each node's pointer(s) to the next (and sometimes previous) node.