What is the difference between an array and a linked list?
Short answer: An array stores elements contiguously, giving O(1) access by index and excellent cache behaviour, but inserting or deleting in the middle needs O(n) shifting and its size is fixed. A linked list stores each element in a separate node with a pointer, giving O(1) insertion and deletion once you have the node and flexible size, but O(n) access by position, pointer overhead and poor cache locality.
| Array | Linked list | |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert/delete in the middle | O(n) shifting | O(1) given the node (or its predecessor) |
| Memory overhead | none | one or two pointers per node |
| Cache behaviour | excellent (prefetch, contiguous) | poor (nodes scattered) |
| Size | fixed (or realloc) | grows node by node |
| Allocation | one block, often static | per node (or from a pool) |
In embedded systems: arrays usually win: no allocation, predictable timing, and better performance for the small n typical in firmware. Linked lists are used where objects must move between collections cheaply: RTOS ready/blocked lists, timer lists, free lists in memory pools, and network buffer chains, usually as intrusive lists (next question) with nodes from static pools.
Real-world note: even on desktops, iterating an array is often an order of magnitude faster than a linked list of the same length because of cache misses, so "O(1) insert" is not the whole story.