Linked List - Insert at Head
O(1) insertion. Allocate a node, rewire next, and move the head pointer.
What is a linked list?
A chain of nodes where each node holds a value and a pointer to the next node. Unlike an array, elements are not stored contiguously in memory.
Where you will see it
Real systems that use this exact idea. Tap a card to open it.
Common traps
The mistakes interviewers watch for. Guess the fix, then reveal it.
FixMoving head first makes newNode.next point at ITSELF - an instant cycle. Rewire next before moving head.
FixIn functional-style APIs the caller's reference must update. Returning nothing leaves the caller holding the old list.
FixList nodes live anywhere on the heap. Index arithmetic is meaningless - only next-pointer walks work.
Interview prep
Questions you could be asked, with the depth an interviewer wants to hear.
For O(1) insertion and deletion at the head or at a known node, and when the size changes often. Arrays win on random access and cache locality.
insert O(1) · access O(n)
Real worldA queue backed by a linked list never resizes; an array-backed queue does.
DeeperThe trade-off is fundamental: contiguous memory buys O(1) access but O(n) shifting.