home
›
cheatsheets
›
computer_science
›
linked_lists_stacks_queues
Free to read Every card and diagram, and Quiz me
2
Free account Star cards. Your Quiz me marks are kept, so next time you drill just what you missed
3
Pro All 78 answers on this sheet, My sheet across every topic, and PDFs
A free account keeps your stars and Quiz me marks. Pro adds all 78 answers on this sheet, My sheet across every topic, and PDFs.
/
Read
Quiz me
Comfortable
Compact
0
Click any code to copy it
Done 0 /0
To review 0
On this sheet
01 Linked lists vs arrays02 Linked list techniques03 Stacks04 Queues05 Deques & sliding windows06 Classic design questions07 Recursion & the call stack08 Thread-safe structures09 Queues in production10 Linked lists at scale
The model A linked list is a chain of nodes, each with a value and a next pointer. Reaching index k is O(n), but inserting at a node you hold is O(1). A stack hands back the newest item first (LIFO). A queue hands back the oldest first (FIFO). Stacks and queues are contracts , not storage. Build them on an array, a ring buffer or a list, and every operation is O(1). On real hardware arrays usually win . Their elements share cache lines, while each list hop can miss the cache. A, B and C are nodes, and each arrow is a pointer. The head and tail boxes are pointers the list keeps. A stack and a queue differ only in the ends they use.
Linked lists vs arrays what a node costs, and what it buys you Linked list or array Read the item at index k O(1) in an array, by address math. O(n) in a list, by walking.
Insert or delete at the front O(1) in a list. O(n) in an array, which shifts every element.
Insert or delete at a node you hold O(1) in a list. O(n) in an array, which shifts the rest.
Append at the end O(1) in both, with a tail pointer or amortized growth.
Tip Use a list when you mostly insert at nodes you hold. Use an array when you mostly read by index.
Trap The list's O(1) insert assumes you already hold the node. Walking there first still costs O(n).
Nodes, head and tail Walk to the kth node for (let i = 0; i < k && cur; i++) cur = cur.next O(n). Stop at null if the list is shorter than k.
Append in O(1) Keep a tail pointer, or every append walks the list.
Trap Delete the last node without moving tail, and the next append writes through a stale pointer.
Singly, doubly or circular Delete a node you hold in O(1) Doubly linked. prev gives you the node before it, with no search.
Cycle through the items forever Circular. The last node points back to the first. Round-robin uses it.
Tip Skip prev if you only touch one end. It costs memory on every node and doubles the link updates.
Trap A circular list has no null, so while (node) never ends. Stop when you are back at the head.
Why arrays win in practice Explain why an array scan is fast Elements sit side by side, so one read caches their neighbors.
Explain why a list scan is slow Each next jumps somewhere new, and a miss costs hundreds of cycles.
Count a list's memory per element A 4-byte int can take 24 to 32 bytes with its pointer, header and padding.
Tip Both scans are O(n) on paper. In practice the array can run many times faster.
Linked list techniques the list code interviewers ask you to write Reverse a list in place let prev = null, cur = head; while (cur) { const next = cur.next; save it first cur.next = prev; flip the pointer prev = cur; cur = next; } return prev; the new head
Give the cost of reversing in place O(n) time and O(1) extra space.
Trap The recursive version also takes O(n) stack space. A long list overflows it.
Two pointers on a list A B C D E F a cycle F points back to C, so the loop starts at C. Set F.next to null to break it.Find the middle in one pass while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } On an even length, slow ends on the second middle.
Find the kth node from the end Move one pointer k nodes ahead, then step both. When the lead hits null, the other is on it.
Detect a cycle in O(1) space Same loop. If slow === fast at any step, the list has a cycle.
Find where the cycle starts Reset one pointer to the head. Step both by one. They meet at the start.
Break the cycle Set next to null on the node that points back to the start.
Tip A hash set of visited nodes also finds a cycle. It's simpler, but it costs O(n) memory.
Sentinel node Skip the special cases at the head const dummy = { next: head } Every real node now has a node before it. Return dummy.next.
Merge two sorted lists From a dummy, append the smaller front node each step, then the rest.
List a doubly linked list's edge cases An empty list, one node that is both head and tail, removing either end, and a double delete.
Tip Check node.prev.next === node and node.next.prev === node to catch a broken link early.
Trap Point a new circular sentinel's next and prev at itself, or the first operation reads garbage.
Insert, delete and splice Insert after a node you hold n.next = node.next; node.next = n
Delete a node given only a pointer to it node.value = node.next.value; node.next = node.next.next Copy the next node's value, then unlink that node.
Join or split two lists O(1) once you hold the boundary nodes. No data moves.
Trap The copy trick fails on the tail, and it breaks outside pointers to the node you overwrote.
Sorted lists and skip lists Binary search a linked list No gain. Each midpoint is a walk, so even the best version is O(n).
Insert into a sorted list An O(n) walk, then an O(1) link. A sorted array finds the spot in O(log n) but shifts in O(n).
Search a sorted list in O(log n) A skip list. Sparse express lanes above the list let search skip ahead.
Tip Skip list levels come from coin flips, so O(log n) is expected. The worst case is O(n).
Stacks last in, first out Stack operations Push, pop and peek at the top stack.push(x) stack.pop() stack.at(-1)
Tip Push and pop at the array's end. unshift and shift work at the front and cost O(n).
Trap Popping an empty stack is an underflow, but JavaScript's pop() just returns undefined. Check the length first.
Array or linked list underneath Pick a stack's default storage A dynamic array. Both operations use one end, which stays in cache.
Build a stack on a linked list The head is the top. Push adds a head and pop unlinks it.
Explain O(1) amortized push A full array copies its items to a new one, 1.5 to 2 times bigger. Spread over n pushes, that's O(1) each.
Tip Your language's dynamic array is already a good stack. Reach for it first.
Trap Amortized is an average. One push can still copy the whole array, so real-time code preallocates.
Problems a stack solves Check that brackets match Push each opener. On a closer, pop and check that it matches. The stack must end empty.
Back out of a dead end Push each choice. Pop back to it when a path fails.
Spot a monotonic stack problem Each item needs its nearest larger or smaller neighbor, as in stock span.
Find each item's next greater element while (st.length && a[st.at(-1)] < a[i]) next[st.pop()] = a[i] Then push i. Each index is pushed once and popped at most once, so it's O(n).
Trap A monotonic stack doesn't help with range queries or the kth largest. Use a segment tree or a heap.
Queues first in, first out Queue operations Add at the back and remove from the front enqueue and dequeue, both O(1) with a ring buffer or a tail pointer.
Tell a stack from a queue A stack gives back the newest item. A queue gives back the oldest.
Tip Pick a queue when arrival order matters, as in print jobs, task runners and message pipelines.
Build a queue Drain an array queue with shift() while (q.length) q.shift() O(n^2). Every shift() moves all the remaining elements.
Dequeue from an array without shifting const first = q[head++] O(1), but it never reuses the cells before head.
Build a queue on a linked list Enqueue at the tail and dequeue at the head. The tail pointer keeps it O(1).
Choose a ring buffer or a linked list A ring buffer for a fixed size and speed. A list to grow without limit.
Trap Shifting down after each dequeue frees those cells, but costs O(n). Wrap the indexes instead.
Ring buffer tail head E free free C D ring buffer The head reads C, then D, then wraps to E at the front. The tail writes after E next.Advance an index with wrap-around tail = (tail + 1) % capacity
Tell full from empty Both show head === tail. Keep a count, or leave one slot empty.
BFS and priority queues Find the shortest unweighted path BFS with a queue. It finishes each distance before the next, so its first path is the shortest.
Serve the most urgent item first A priority queue, usually a binary heap. Insert and remove cost O(log n).
Break priority ties by arrival order Add a sequence number to the key. A heap isn't stable.
Trap Use a stack instead and you get DFS. It finds a path, but not always the shortest.
Deques & sliding windows both ends in O(1) Double-ended queue Add or remove at either end A deque, O(1) at both ends. It's a stack and a queue in one.
Build a deque A circular array, or a doubly linked list with head and tail pointers.
Use a deque from the standard library Python has collections.deque and Java has ArrayDeque. JavaScript has none.
Tip The circular array is faster for the cache, but a resize copies everything. The list never resizes.
Trap A deque on a plain array is O(n) at the front, because every element shifts to make room.
Sliding window maximum Get the max of every window of size k Keep a deque of indexes whose values fall front to back. The front is the max.
Add the next index while (dq.length && a[dq.at(-1)] < a[i]) dq.pop() Then push i. Drop the front once it leaves the window.
Name what a monotonic queue can't track The median, the sum or the second largest. Use a running total or two heaps.
Tip Each index enters and leaves once, so the sweep is O(n). Rescanning every window costs O(nk).
Trap Store indexes, not values. A value alone can't tell you when it has left the window.
Classic design questions build a structure out of simpler ones Queue from stacks, stack from queues Enqueue onto two stacks inbox.push(x)
Dequeue from two stacks if (!out.length) while (inbox.length) out.push(inbox.pop()) out.pop() The move puts the oldest on top. Each item moves once, so it's O(1) amortized.
Build a stack from one queue Enqueue, then rotate the older items behind it. Push costs O(n) and pop O(1).
Trap The two-stack queue is O(1) only on average, and one dequeue can still take O(n). The queue-based stack gets no average win.
Min stack Return the minimum in O(1) min.push(Math.min(x, min.length ? min.at(-1) : x)) A second stack tracks the running minimum. Pop both together.
Save memory on the min stack Push only when x <= min. Pop only when the popped value is the min.
Trap Compare with <=, not <. Otherwise a repeated minimum disappears when one copy pops.
LRU cache Build a fixed-size LRU cache A hash map from key to node, plus a doubly linked list ordered by recency.
Handle get and put Both leave the node at the front. When full, put evicts the tail.
Explain why the list is doubly linked Moving a node to the front unlinks it mid-list. That needs prev.
Tip One lock serializes every thread. Real systems shard the cache into separate LRU segments.
Trap A put for an existing key must move and overwrite its node, not add a second one.
Undo and redo Undo an action Pop from undo, apply the inverse, and push it onto redo.
Cap the history Drop the oldest entry. That needs a deque, not a stack.
Tip Store inverse commands to save memory, or full snapshots to keep undo simple.
Trap A new action must clear the redo stack. It's the rule people forget.
Recursion & the call stack why deep recursion crashes, and the fix The call stack Say what a stack frame holds The return address, saved registers, parameters and local variables.
Explain a stack overflow A missing base case or very deep data overflows the fixed stack.
Estimate how deep recursion can go Tens of thousands of levels on a typical 1 to 8 MB stack.
Tip Tail-call optimization would reuse one frame, but most mainstream languages don't do it.
Replace recursion with a stack Turn a recursive DFS into a loop Pop a node, visit it, push its children in reverse. Keep a visited set if the graph has cycles.
Decide when to switch When input you don't control sets the depth, or you need to pause and resume the walk.
Free a very long list Loop, saving next before each free. A recursive destructor, as in a unique_ptr chain, overflows.
Tip Keep plain recursion when the depth is small and bounded. It's clearer and just as fast.
Trap An explicit stack swaps stack overflow for heap use. A very wide structure makes it huge.
Thread-safe structures queues, stacks and lists that many threads share Lock-based queues Let producers and consumers work at once Use two locks, one per end. A dummy node keeps the ends apart.
Build a bounded blocking queue A ring buffer, one lock, and condition variables notFull and notEmpty.
Tip Pad the head and tail onto separate cache lines, or the two locks bounce one line between cores.
Trap Wait in a while loop, never an if. Wakeups can be spurious.
Lock-free stacks and queues Make a stack lock-free A Treiber stack. Push and pop retry a compare-and-swap (CAS) on the head.
Make a queue lock-free The Michael-Scott queue. A CAS links the node at tail.next, then tail moves to it.
Free a node another thread may still read Hazard pointers or epoch-based reclamation. It's the hardest part.
Explain the ABA problem A freed and reused address looks unchanged, so CAS wrongly succeeds. Tagged pointers fix it.
Tip Under heavy contention, elimination backoff pairs a push with a pop in a side array, away from the head.
Trap Lock-free means non-blocking, not faster. CAS retries on one hot cache line can lose to a lock.
Scheduler queues Spread tasks across worker threads One deque per worker. Owners use the bottom, and thieves steal from the top.
Stop low-priority tasks from starving Aging. A task that waits too long moves up to a higher queue.
Avoid one global run queue Cores would fight over one lock. Kernels keep a run queue per core.
Tip Multilevel feedback queues demote tasks that hog the CPU and favor short, interactive ones.
A linked list shared by threads Spot a lost update Two threads insert after the same node. Both read the old next, and one insert vanishes.
Publish a new node safely Set its fields first, then link it with a release store.
Read a list while others write it Read-copy-update. Readers take no lock and see the old or the new list.
Tip Hand-over-hand locking scales better than one big lock, but it deadlocks if the lock order slips.
Trap A read-write lock is the simple fix, but it stalls every reader while a writer runs.
Queues in production full buffers, restarts and scale When producers outrun consumers Handle a full ring buffer Block the producer, overwrite the oldest, or reject the newest. Overwrite only latest-value data.
Slow the producer down Backpressure. Block or reject when full, or let the consumer grant credits.
Trap An unbounded queue has no backpressure. It grows until memory runs out and the process dies.
Durable and delayed queues Keep messages across a restart Log each message and fsync before you acknowledge it. Replay on startup.
Commit a consumer's offset After processing succeeds. A crash in between redelivers the message.
Deliver a message at a set time A min-heap on delivery time. A dispatcher sleeps until the next one is due.
Hold millions of timers A timing wheel. Bucketing time makes insert O(1), not O(log n).
Tip One fsync per message is slow. Group commit batches many messages into one.
Trap Committing after processing means at-least-once delivery. Make consumers idempotent.
Scale a queue past one machine Shard a queue Partition it by a routing key. Order holds only within a partition.
Handle a million messages a second The shared tail breaks first. Producers fight over one cache line.
Tip Shard across cores, batch enqueues, and give each producer its own region of the buffer.
Trap A hot key overloads one partition while the others sit idle.
Linked lists at scale where a list still wins, and what breaks When a list still wins Unlink nodes you already hold Kernel run queues, timer wheels and LRU eviction do it in O(1).
Keep node addresses stable Other structures can point straight at a node. Inserts never move it.
Skip the allocation per node An intrusive list. next and prev live inside the object.
Track freed memory blocks A free list threaded through the freed blocks. Pop to allocate, push to free.
Trap An intrusive object reserves space for its links and fits only the lists it was built for.
Lists with millions of nodes Estimate a walk over 10 million nodes About a second of pure stalls, at roughly 100 ns per cache miss.
Cut the cache misses An unrolled list. Each node holds a small array, so one miss serves many.
Count the link memory for a billion nodes 16 GB for two 8-byte pointers each, before any payload.
Stop a long-lived list from fragmenting memory Allocate nodes from a pool or slab. They stay packed and the same size.
Halve a doubly linked list's pointers XOR linking. One field holds prev XOR next.
Tip A stop-the-world collector visits every live node, so a billion nodes means multi-second pauses.
Trap XOR links hide the real pointers from garbage collectors and debuggers, all to save 8 bytes a node.
Nothing matches. Try a shorter word, or clear the search.
Practice Guided practice One question at a time, with the ones you miss coming back. Practice 78 interview questions Full answers, from beginner to expert.
Found this useful? Pass it on.
Share on LinkedIn
Share on X
Copy link
This sheet stays free. With Pro , you can:
Every answer on this sheet. Read the full answer to all 78 questions it links, not just the 11 free ones.My sheet. The cards you star and the ones you miss in Quiz me, from every sheet, on one page to quiz and print.PDFs. Download this sheet and My sheet, laid out for A4, with every question a link to its answer.The rest of Pro. Every answer in the question library, and 1,000 AI credits a month.
