What you'll learn

  1. Quick answer
  2. How Each One Is Laid Out in Memory
  3. The Operations Compared
  4. Why Arrays Usually Win in Practice
  5. When a Linked List Is Genuinely Right
  6. How to Answer This in an Interview
  7. FAQ

Quick Answer

An array stores elements in one continuous block of memory, so any element can be read instantly by index in O(1), but inserting or deleting in the middle costs O(n) because everything after it must shift. A linked list stores each element in its own node with a pointer to the next, so inserting or deleting is O(1) once you are at the position — but reaching that position takes O(n) because you must walk from the head. Use an array when you mostly read; use a linked list when you mostly insert and delete at known positions.

How Each One Is Laid Out in Memory

The whole comparison follows from one difference: where the elements physically live.

An array is one continuous block. If the first element sits at address 1000 and each element takes 4 bytes, then element 5 is at 1000 plus 5 times 4. The computer calculates that address in a single step, which is why array access by index is O(1) no matter how large the array is.

Array in memory:
[ 10 ][ 20 ][ 30 ][ 40 ][ 50 ]
 1000  1004  1008  1012  1016     <- addresses, evenly spaced

A linked list scatters its elements. Each node holds a value and the address of the next node. Nothing guarantees they sit near each other in memory.

Linked list in memory:
[10|→] ....... [20|→] .. [30|→] ....... [40|null]
 2400          7180      3020           9550     <- wherever there was room

To reach the fourth node you must start at the head and follow three pointers. There is no arithmetic shortcut, because there is no pattern to the addresses. That single fact produces every difference below.

The Operations Compared

Here is the honest comparison, with the caveat that matters written next to each row.

  • Access by index — Array O(1), linked list O(n). This is the array's decisive advantage.
  • Search for a value — Both O(n) when unsorted. Neither wins.
  • Insert or delete at the front — Array O(n) because everything shifts right; linked list O(1) because you just repoint the head. This is the linked list's decisive advantage.
  • Insert or delete at the end — Array O(1) amortised; linked list O(n) unless you keep a tail pointer, then O(1).
  • Insert or delete in the middle — This is where people go wrong. See below.

The middle-insertion trap. Textbooks say linked list insertion is O(1) and arrays are O(n), so linked lists win. That is only true if you are already holding the node. If you have an index and must find the position first, the linked list spends O(n) walking there, then O(1) inserting — total O(n). The array spends O(1) finding the position and O(n) shifting — also total O(n).

Both are O(n). The linked list has not won anything. It only wins when you already have a reference to the node, which happens when you are iterating and deleting as you go.

Why Arrays Usually Win in Practice

This is the part textbooks skip, and it surprises people who learned the theory first. On real hardware, arrays frequently beat linked lists even for operations where the linked list has better complexity on paper.

The reason is cache locality. Processors do not fetch one value at a time; they pull in a chunk of neighbouring memory at once, on the assumption that you will want the next value soon. For an array that assumption is exactly right — the next element is physically adjacent, so it is already there. For a linked list the next node could be anywhere, so nearly every step is a fresh trip to main memory, which is dramatically slower than cache.

There is a memory overhead too. Every linked list node stores at least one pointer alongside the value. For a list of small values, the pointers can take as much space as the data itself. An array stores only the values.

This is why languages default to arrays. Python's list, JavaScript's Array, Java's ArrayList and C++'s vector are all array-backed, growable structures — and they are the right default for the vast majority of code you will write.

When a Linked List Is Genuinely Right

They are not obsolete. They are just narrower than they appear in a syllabus.

  • You insert and delete constantly at both ends. A queue or deque built on a doubly linked list gives O(1) at either end without shifting anything.
  • You already hold a reference to the node. An LRU cache is the classic real example: a hash map points straight at nodes in a doubly linked list, so moving an item to the front is O(1) with no searching.
  • You cannot afford a resize pause. When an array-backed list runs out of room it allocates a bigger block and copies everything across. Usually irrelevant, but in latency-sensitive code that copy is a visible spike.
  • You genuinely do not know the size. A linked list grows one node at a time and never needs contiguous space, which matters in memory-constrained or heavily fragmented environments.

In interviews, linked lists appear less because they are practical and more because pointer manipulation is easy to test. Reversing a linked list, detecting a cycle with fast and slow pointers, and finding the middle node are staples — worth practising even though you will rarely build one at work.

How to Answer This in an Interview

The question is usually phrased as "when would you use a linked list over an array?", and the weak answer is "linked lists are better for insertion". State the real decision rule instead.

Ask what the access pattern is. If the code mostly reads by index, use an array — O(1) access is not something a linked list can ever match. If the code mostly inserts and deletes at positions it already holds, a linked list avoids the shifting.

Then add the practical note, because it shows you have thought past the table: for small and medium data, arrays often win anyway thanks to cache locality, so a linked list needs a clear reason rather than being the default for insert-heavy work.

If asked about a dynamic array specifically, mention amortised cost. Appending is usually O(1), but when capacity runs out the structure doubles its size and copies everything, an O(n) operation. Spread across many appends the average stays O(1), which is what "amortised" means.

Frequently Asked Questions

Is a Python list an array or a linked list? It is a dynamic array — a resizable block of contiguous memory holding references. That is why indexing is O(1) and inserting at the front with insert(0, x) is O(n). If you need fast operations at both ends, use collections.deque instead.
Why is inserting at the front of an array O(n)? Because every existing element has to move one position right to make room. For a million-element array that is a million moves. A linked list only repoints the head, which is why it is O(1) there.
What is a doubly linked list used for? Each node also points backwards, which lets you walk in both directions and delete a node in O(1) when you hold a reference to it, without needing the previous node. LRU caches, browser history and undo stacks all use this.
Which is better for interviews, arrays or linked lists? Practise both, but expect more array-based problems. Two pointers, sliding window and sorting all operate on arrays. Linked list questions cluster around a few patterns: reversal, cycle detection with fast and slow pointers, and finding the middle.
Do linked lists use more memory than arrays? Yes. Every node carries at least one pointer alongside the value, and each is allocated separately. For a list of integers, the pointer overhead can equal or exceed the data. Arrays store only the values in one block.