Theory
Two queues with different endings
BookBridge now runs 2 waiting lines.
The issue-request queue: requests arrive, get served, and the line eventually EMPTIES. It has a genuine end.
The reading-room roster: 4 members share 2 desks by turns, and after the last member the turn goes back to the FIRST. This line never ends; it cycles.
Same nodes, same links, one structural difference: what the last node's next holds. That single slot splits the unit's 2 list types.
Theory
Singly linked list, formally
A singly linked list is a set of nodes where each node references the next, reachable from one entry reference called the head:
head → [Riya] → [Aman] → [Zoya] → null
Properties that exams quote:
- links point one direction only: forward (that is the "singly")
- the last node's next is null: the end marker
- traversal starts at head and stops at null
- from any node you can reach everything AFTER it, never anything before it
Theory
Bend it into a circle
Now change exactly one thing: the last node's next holds the head reference instead of null.
head → [Riya] → [Aman] → [Zoya] ↩ (back to Riya)
This is the singly circular linked list. Still singly: one direction, one link per node. But:
- there is no null anywhere: the chain has no natural end
- from ANY node, keep walking and you reach every node, including those "before" you
- "last" and "first" are neighbours: perfect for turn-taking
At a glance
Singly vs singly circular
| Aspect | Singly | Singly circular |
|---|---|---|
| Last node's next | null | The head node |
| End detection | cur == null | Back at the starting node |
| Traversal loop | while (cur != null) | do-while until start reappears |
| Head from last node | Impossible (no backward path) | One step: last.next |
| Natural fit | Queues and stacks that empty | Round-robin turns, repeating playlists |
Quiz
You print a singly CIRCULAR list with the familiar loop: while (cur != null) { print; cur = cur.next; } What happens?
- It prints each member once and stops at the last node
- It loops forever: no next in the circle is ever null
- It throws a NullPointerException at the last node
- It prints nothing: the loop condition fails immediately
Show the answer
It loops forever: no next in the circle is ever null
The while waits for a null that does not exist: in a circular list every next points at a real node, so the loop cycles Riya, Aman, Zoya, Riya, Aman... forever. This is the infinite-loop killer from the Unit 1 looping lesson wearing a data-structure costume. Option A describes the SINGLY list's behaviour. Option C has it backwards: the crash of dereferencing null cannot happen where null never appears. The circular traversal needs a different stop signal: am I back where I started?
Think first
Design the right stop signal
If null never comes, how DO you traverse a circular list exactly once? Think about which loop from Unit 1 fits, and why while cannot work even with the fixed condition.
Show the answer
Remember the start, walk, and stop when you see it again: start at head, and loop while (cur != head). But test-at-the-top while fails at step 0: cur IS head before you have printed anything, so the body never runs. The loop that runs its body before checking is do-while: do { print; cur = cur.next; } while (cur != head); prints every node exactly once. The confident host from Unit 1 finally meets the structure that genuinely needs it.
Watch out
Concept traps the exam loves
"Circular means you can go backwards": no. It is still SINGLY linked: one forward link per node. You can reach earlier nodes only by going all the way around; a doubly linked list (a later course) is the one with real backward links.
"The circular list has no head": it still needs an entry reference to be usable; implementations often keep a reference to the LAST node, because last.next IS the head: 2 ends for the price of 1.
Theory
Where each shape runs the world
The singly list is the default chain: BookBridge's request queue next lesson, undo histories, hash-table buckets. The circular one owns turn-taking: BCA203's round-robin CPU scheduling handed each process a time slice from exactly this shape, a music player's repeat-all is a circular walk, and the reading-room roster cycles the same way. Next 2 lessons build both, operation by operation, with every reference update traced.
Summary
Key takeaways
- Singly linked list: head to last, one-directional links, last node's next is null.
- Singly circular: identical, except the last node's next holds the head: no null anywhere.
- Traversal: while (cur != null) for singly; do-while until the start reappears for circular.
- while (cur != null) on a circular list loops forever: the classic trap.
- Circular is still one-directional; going "back" means going all the way around.
- Keeping a reference to the LAST node of a circle gives the head free: last.next.
- Memory hook: singly ends at null, circular ends where it began.