Micro-questions over the linked lists module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The object itself
1. What is a linked list?
Answer
A chain of nodes, each holding a data value and a pointer to the next node. Nothing more than that.
2. Why do linked lists exist?
Answer
To make insertion and deletion cheap. An array must shift elements to open a gap; a linked list just rewires two pointers, because nothing has to be adjacent to anything.
3. Give a real-world illustration.
Answer
A treasure hunt. Each clue card holds a message and tells you where the next card is. The cards can be anywhere in the city — only the chain of references matters.
4. Draw a singly linked list.
Answer
Head -> [ Value | Next ] -> [ Value | Next ] -> None
5. What does a linked list give up compared to an array?
Answer
Contiguity — and therefore random access, address arithmetic, and cache locality.
B. The vocabulary
6. What is a node?
Answer
A small container holding one data value and a pointer to another node.
7. What is a pointer?
Answer
A stored memory address — a note saying “the next item lives over there”. In Python it is a reference held in a variable; in C it is a literal address.
8. What is next?
Answer
The usual name for the pointer inside a node that points to the following node.
9. What is the head, and why does it matter so much?
Answer
The pointer to the very first node. It is the only way in — lose it and the whole list becomes unreachable, because nothing else points at the start.
10. What is the tail, and how do you recognise it?
Answer
The last node. Its next points at nothing — None in Python, NULL in C — and that nothing is how you know you have reached the end.
11. What is traversal?
Answer
Walking from the head following next pointers one at a time. It is the only way to reach the middle, which is why reaching position costs .
12. What is a singly linked list?
Answer
Each node points only forwards. You can walk head to tail, never backwards.
13. What is a doubly linked list, and what does the extra pointer buy?
Answer
Each node holds prev as well as next. It costs extra memory per node and buys backwards traversal and deletion when you already hold the node.
14. What is a sentinel?
Answer
Also called a dummy head — a fake node placed before the real first one, holding no useful data. It removes special cases by guaranteeing there is always a node before the one you are working on.
15. What is a cycle?
Answer
When some node’s next points back to an earlier node, so the chain loops forever instead of ending. Detecting one is what fast and slow pointers are for.
C. The four variants
16. Name the four main variations.
Answer
Singly linked, doubly linked, circular singly linked, circular doubly linked.
17. Which variants can delete a node you hold in , and why?
Answer
The doubly linked ones. Deletion means rewiring the predecessor, and only a prev pointer gives you the predecessor without walking from the head.
18. Why can a singly linked list not delete a held node in ?
Answer
You need the node before it to re-route around it, and a singly linked node has no way back. Finding the predecessor is an walk.
19. Give a real use for a doubly linked list.
Answer
LRU caches and browser back/forward history — anything needing movement in both directions plus removal from the middle.
20. Give a real use for a circular list.
Answer
Round-robin CPU schedulers and music playlists (circular singly); the Linux kernel process list, list_head, is circular doubly linked.
D. The sentinel trick
21. Where do 90% of linked list bugs happen?
Answer
Edge cases: inserting into an empty list, deleting the head, deleting the last node.
22. How does a sentinel eliminate them?
Answer
It guarantees the list is never empty and that every real node has a predecessor, so head operations use exactly the same code as middle operations — no if head is None branches.
23. In a function using a sentinel, what do you return at the end?
Answer
dummy.next — the real head, which may have changed during the operation. Never the dummy itself, and never the original head variable.
E. Costs
24. Cost of access by index?
Answer
for both singly and doubly linked — you must walk. Arrays do it in .
25. Cost of insert or delete at the head?
Answer
for both variants. This is what the structure is for; an array charges for the same thing.
26. Cost of insert or delete at the tail?
Answer
Singly: , or if you keep a tail pointer — but deletion at the tail is still because you need the predecessor. Doubly: .
27. Cost of searching for a value?
Answer
— the same as an unsorted array, and with worse constants.
28. What is the space overhead per item?
Answer
One pointer per item for singly linked, two for doubly linked, zero for an array. On a 64-bit machine that is 8 or 16 extra bytes per element, which for small values can exceed the data itself.
29. Why is binary search useless on a sorted linked list?
Answer
Binary search needs access to the midpoint. Reaching the midpoint of a linked list is , which destroys the saving entirely.
F. The ADT and the proviso
30. List the linked list ADT.
Answer
insert_front, delete_front, insert_after(node), delete_after(node) — all ; get(i) — ; find(value) — ; is_empty() and size() — with a running count, without.
31. State the array/linked-list trade as two sentences.
Answer
An array gives access by position and charges for middle insertion and deletion.
A linked list gives insertion and deletion — provided you already hold the node — and charges for access by position.
32. What is the most commonly missed point about ” deletion”?
Answer
The proviso. It is only true once you are standing at the right node. Given only an index you must walk there first, so deleting the th item is overall.
33. Where does the node reference genuinely come from somewhere else?
Answer
An LRU cache: a hash map maps the key straight to the node, so the delete really is with no walk. That combination is the whole design.
G. The hardware reality check
34. On paper linked lists beat arrays for insertion. Why do dynamic arrays usually win in practice?
Answer
Cache. Array elements sit next to each other, so one fetch brings in several; linked list nodes are scattered on the heap, so every next you follow can be a cache miss costing hundreds of clock cycles.
35. Both walks are . What does the complexity table fail to show?
Answer
The constant factor. Walking a linked list is several times slower than scanning an array of the same length, because Big-O counts operations and cannot see memory behaviour.
36. What follows from that for everyday code?
Answer
Arrays are the default. A linked list is reached for only when its specific splice genuinely matters and you genuinely hold the node.
H. Traps
37. What happens if you reassign head = head.next without saving the old head?
Answer
The previous node becomes unreachable and is garbage collected — in C, leaked. Whatever you were meant to do with it is gone.
38. Inserting node X between A and B — what is the correct order of assignments, and why?
Answer
X.next = B first, then A.next = X. Doing it in reverse overwrites A.next before you have read it, losing B and the entire rest of the list.
39. Why does while current: infinite-loop on a circular list?
Answer
A circular list has no None at the end, so the condition never fails. You must loop while current is not start_node.
40. Summarise the linked list in one sentence.
Answer
Order without adjacency — which buys splicing at a held node and costs random access, cache locality, and a pointer’s worth of memory per item.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Linked Lists — the module
- Arrays — Question Bank — the opposite trade
- Fast & Slow Pointers — cycle detection
- Linked List Reversal — the pointer-order trap in anger
Software engineering
Infrastructure & security
Computer science
Hardware & engineering