Arrays vs Linked Lists: What Interviewers Expect You to Know

When an interviewer asks you to choose between an array and a linked list for a problem like LRU Cache, the correct answer is almost always the array until pointer manipulation forces your hand. Arrays offer contiguous memory that fits cleanly into CPU cache lines, while linked lists scatter nodes across heap memory with pointer overhead on every single access.

Memory Layout and Cache Behaviour

An array stores elements in adjacent memory locations. If you declare int arr[1000], those thousand integers sit back-to-back in RAM. When the CPU processor requests arr[0], it pulls a whole cache line of 64 bytes into L1 cache at once, bringing arr[1] through arr[15] along for free.

A linked list does the opposite. Each node contains a data payload and a next pointer, scattered across random heap addresses. Traversing head->next ten times triggers ten distinct cache misses, forcing the CPU to wait while memory fetches crawl from RAM. For interview problems involving heavy traversal like Binary Search, a linked list fails immediately because you cannot jump to index n/2 in O(1) time.

Insertion and Deletion Mechanics

Arrays win on access time with O(1) index lookup, but insertion and deletion in the middle cost O(n) because you must shift trailing elements. If you insert an element at index 0 in vector<int> v of size 1000, all 1000 elements move right by one position.

Linked lists invert this trade-off. If you hold a pointer to a specific node, deleting it takes O(1) time by rewiring the previous node's next pointer around it. This makes linked lists mandatory for problems like Design Browser History or implementing chaining in a hash map where you perform frequent head insertions without index lookups.

Dynamic Array Growth and Amortised Cost

Under the hood, dynamic arrays like std::vector in C++ or ArrayList in Java do not reallocate memory on every push. When capacity fills up, the runtime allocates a new block of double the current size, copies the old elements over, and frees the original block.

Consider a vector starting at capacity 1. Pushing four elements requires reallocations at sizes 1, 2, and 4, taking 1 plus 2 plus 4 total copy operations. Spread across 4 insertions, the cost averages to 7/4 operations per push, giving an amortised time complexity of O(1). This growth factor of 2 ensures that individual insertions rarely trigger massive slowdowns during coding rounds.

Problem Suitability Rules

Use an array when the input size is fixed, you need binary search, or you iterate sequentially through data loaded from disk or network streams. Use a linked list when you implement an undo stack, manage free lists in memory allocators, or solve graph traversal problems where node degrees change constantly.

Here is how amortised growth works in practice when pushing elements into a capacity-1 vector:

1. Push 10: capacity 1, size 1, 0 copies.
2. Push 20: capacity doubles to 2, size 2, 1 copy of 10.
3. Push 30: capacity doubles to 4, size 3, 2 copies of 10 and 20.
4. Push 40: capacity 4, size 4, 0 copies. Total copies equal 3 for 4 insertions.

Practical Rules for Placement Tests

• Choose arrays by default for any problem involving sorting, two pointers, or prefix sums.
• Use linked lists only when node manipulation happens without random index access.
• Calculate memory limits before picking a structure; 10 to the power of 6 integers fit easily in 4 megabytes of contiguous RAM.
• Practice Reverse Nodes in k-Group to master pointer rewiring without losing track of head references.
• Use DSA Tracker to log every time you choose the wrong structure during mock interviews.

Open your current practice sheet and refactor your last three linked list solutions to use arrays if they only required sequential scans.

Keep going with practice problems and the online compiler.

Further reading: Binary search on Wikipedia.