Linked Lists, Stacks & Queues · question

Question 1 of 78

What is a linked list, and how does it differ from an array?

beginner

← All Linked Lists, Stacks & Queues questions

Re-explain

A linked list chains elements together through nodes. Each node holds a value and a pointer to the next node. The list only knows where its first node lives, so you reach any element by following pointers one hop at a time.

An array stores elements side by side in one contiguous block. That layout lets you jump straight to index 5 by arithmetic. A linked list cannot, so reaching position 5 costs O(n) hops. Arrays give O(1) random access, and linked lists give O(n).

The tradeoff flips for growth. An array has a fixed block, so growing may mean copying everything. A linked list just allocates a node and rewires a pointer. Choose based on whether you index often or reshape often.

Rewriting in plainer words…

This answer doesn't lend itself to a diagram - it reads best . No credits were charged.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·

What should the new diagram focus on?

Guided practice for Linked Lists, Stacks & Queues One question at a time. Answer out loud, get graded, see what you missed.

See it - interactive diagram

Reaching index 5 in an array and in a linked list

x = arr[5]

cur = head

for hop in range(1, 6):

cur = cur.next

y = cur.value

Arrayone contiguous block

102030405060

read in one jump

Linked listnodes anywhere in memory

Variables

x60

1step

An array keeps its elements side by side in one block. The computer calculates where index 5 sits, so one jump reads 60.

1 / 8

An array is one block, so any index is one jump, which is O(1). A linked list's nodes sit anywhere, so you hop from the head, which is O(n).

Other questions have diagrams like this too. Sign in to ask for one where it's missing - it's free.

Create a free account

How well did you know this?

AI:

Saved in this browser - sign in to keep your review list.

How should your speech become text?

Listening… your words appear above as you speak - tap Stop when you're done.

Recording · cr - tap Stop & transcribe when you're done.

Transcribing with AI…

Voice:

Keep going - a few more words and AI can grade it.

Interview lens How interviewers actually use this question

Likely follow-ups

What does inserting into the middle cost in each, once you count finding the spot? An array shifts every later element, which is O(n). A list rewires in O(1) only once you hold the node before the spot, and walking there is O(n).
Both take O(n) to scan. Why is scanning an array usually much faster in practice? Name cache locality. Contiguous elements share cache lines and prefetch well, while each list hop can land on a cache miss.
When would you actually choose a linked list over an array? You insert or remove often at nodes you already hold, you never need random access, or you need nodes that stay at fixed addresses. Otherwise default to an array.
If growing an array can mean copying everything, why is append still called O(1)? Growing the capacity by a factor, such as doubling, spreads the copy cost over many appends. That makes append O(1) amortized, though one append can still cost O(n).
What does a linked list cost in memory per element compared to an array? Name the per-node pointer and the allocator overhead, and compare them with the spare capacity an array may leave unused.

What you can say

A linked list is a chain of nodes, where each node holds a value and a pointer to the next one, and the list itself only knows where the first node is.
To reach an element you start at the head and follow pointers one hop at a time, so reaching a given position costs O(n).
An array keeps its elements side by side in one contiguous block, so finding index 5 is just arithmetic, which gives O(1) random access.
Growth flips the tradeoff, because an array's block is fixed and growing it may mean copying everything, while a linked list just allocates a node and rewires a pointer.
So I pick an array when I index often, and a linked list when I reshape the collection often.

Weak answers to avoid

Defines both but never compares them Two separate definitions miss the question. Tie layout to cost. A contiguous block makes indexing O(1), and following pointers makes it O(n).
Claims list insertion is always O(1) The rewire is O(1) only once you hold the right node. Finding a position by index still walks the list in O(n). Say both parts.
Says arrays cannot grow at all A fixed block means growing may need a copy into a bigger block, not that growth is impossible. Dynamic arrays do exactly that copy.
Lists costs but gives no rule for choosing Stopping at Big-O leaves half the question unanswered. Close with the rule. Use an array when you index often and a list when you reshape often.

Interview lens

Likely follow-ups, what you can say, and the weak answers to avoid.

Want a quick review of the fundamentals? See the Linked Lists, Stacks & Queues cheatsheet.

← Back to all Linked Lists, Stacks & Queues questions

Pro · $10/mo

67 of 78 Linked Lists, Stacks & Queues answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

Full answers + code
AI explanations, simpler or deeper
1,000 AI credits / month
Cancel anytime

Get Pro → See plans & pricing →