</>EmbeddedInterview

What is the difference between an array and a linked list?

EasyData Structures & Algorithms

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.