Circular linked list — applications: Question bank

Before the traps, we build every symbol and picture you will need — nothing is used before it is defined.

Definition The words we lean on

Node — one box holding data plus a next pointer (an arrow to another box).
Pointer / arrow — a stored address saying "the next box is over there." When we draw it, it is literally an arrow from one box to another.
next — the arrow every node carries, pointing to the box that follows it.
prev — a second arrow that some nodes also carry, pointing to the box before them (so you can walk backwards). A list with only next is singly linked; a list with both next and prev is doubly linked.
Head — the box we call the "first" one; in a CLL this label is a convenience, not a real boundary.
Tail — the last box, whose next arrow loops back to the head.
null — the special "points to nothing" value that ends a normal chain. A CLL has ==no null== anywhere.
Traverse — walk from box to box following next arrows.

The figure below is the mental model for every question on this page — glance back at it whenever a trap talks about arrows, next, prev, or "looping back."

Figure — Circular linked list — applications

True or false — justify

A CLL always has exactly one node whose next points to the head.

True — that node is the tail; by definition tail.next = head, and since every node carries exactly one next arrow (glance at figure s01 — each box has one out-arrow), only one arrow can be the one that lands on the head, so only one node closes the loop.

Every node in a CLL can reach every other node.

True — because the loop never terminates (in s01 the arrows form an unbroken ring), following next from any starting box eventually visits all boxes and returns to the start.

A CLL must contain a null somewhere to know where it ends.

False — a CLL has no end and no null; the "ending" is detected by returning to the node you started from.

In a singly circular list, the head is a special node the traversal must start from.

False — any node works as a start because the structure is symmetric (every box in s01 looks the same); "head" is just a label we chose, unlike in a Singly Linked List where the head is the only entry point.

A one-node CLL has that node pointing to null.

False — a one-node CLL must point to itself (node.next = node, the self-loop A→A) to preserve the loop; pointing to null would break circularity.

Storing a tail pointer lets you reach both ends of a CLL in

O (1)

True — tail.next is the head (that arrow is already drawn in s01), so one pointer delivers both the last node and the first node with a fixed, list-size-independent number of steps.

A doubly circular list and a Doubly Linked List differ only in that the doubly circular one has head.prev = tail and tail.next = head.

True — the two extra loop-closing links (head's prev arrow back to the tail, tail's next arrow to the head) are the only structural difference; both give every node a next and a prev.

Deleting a node from a CLL requires shifting all following nodes.

False — deletion is

O (1)

(a fixed cost): you relink prev.next = victim.next, no shifting (unlike an array, which is why the Josephus Problem favours a CLL).

A Ring Buffer built on an array is conceptually the same wrap-around idea as a CLL.

True — both reuse a fixed loop of slots where "after the last comes the first"; the CLL makes the loop explicit with arrows, the array simulates it with modular indices (a write pointer that wraps to slot 0, overwriting the oldest data).

Round-robin scheduling needs extra "go back to start" code at the end of the process list.

False — the circular link makes current = current->next (follow current's next arrow) automatically wrap from last to first, so no special reset code exists (see Round-Robin Scheduling).

Spot the error

start=head; p=head; while(p!=start){ visit(p); p=p.next; } — what breaks?

The while test is checked before the first visit, so p==start is immediately true and the loop body never runs; it visits nothing. Use a do-while so the head is visited once first.

start=head; p=head; do{ visit(p); p=p.next; } while(p!=null); — what breaks?

There is no null in a CLL (no arrow in s01 ever points to nothing), so p!=null is always true and the loop runs forever (infinite loop / hang). The correct guard is p!=start.

Inserting a new tail with newnode.next = oldtail.next; oldtail.next = newnode; but stopping there — what's missing?

The tail pointer was never updated to newnode, so subsequent inserts use a stale tail and the "last" node is now wrong. After any back-insert you must set tail = newnode.

Inserting the first node into an empty CLL with newnode.next = head; head = newnode; (head was null) — what's wrong?

This points the lone node at null (the old head), so there is no loop at all. The empty-case must special-case: newnode.next = newnode; tail = newnode (the self-loop A→A).

Deleting the head node but forgetting to update tail.next — what breaks?

tail.next still points to the freed old head, dangling into deleted memory; the loop is corrupted. You must set tail.next to the new head after removing the old one.

A programmer counts nodes with n=0; p=head; while(p){ n++; p=p.next; } — why does this hang on a CLL?

p is never null in a CLL, so while(p) never ends; it should count until p returns to head using a do-while.

Why questions

Why does traversal use a do-while instead of a plain while loop?

Because we must visit the starting node before testing the stop condition p==start; since p begins equal to start, a plain while would find the condition already satisfied on entry and skip everything — the do-while runs the body once first.

Why do we prefer storing tail over head for a CLL?

Because tail.next gives the head for free (that arrow already exists in s01), so one pointer yields fixed-cost

O (1)

access to both ends, whereas storing only the head would need an

O (n)

walk all the way round to find the tail for back-inserts.

Why is a CLL the natural fit for the Josephus Problem rather than an array?

In the Josephus problem people stand in a circle and every

k

-th is eliminated; counting wraps around (last leads back to first), which the ring in s01 models directly, and removing a person is a fixed-cost

O (1)

pointer relink versus an

O (n)

element shift in an array.

Why does a music playlist on "repeat" map so cleanly to a CLL?

After the last song the player must return to the first; current = current->next on a circular list does exactly that forever, with no branch to detect the end.

Why can a Fibonacci Heap merge two sibling lists in

O (1)

using CLLs?

Because two circular lists can be spliced by swapping just two pairs of next/prev arrows (a fixed number of edits, independent of list size), and no traversal to find ends is needed since every node's neighbours are already in the loop.

Why does round-robin (Round-Robin Scheduling) avoid a "return to first process" branch entirely?

The tail's next already points to the head, so advancing past the last process lands on the first automatically — the wrap is baked into the structure (the closed ring of s01), not the code.

Why does a Ring Buffer overwrite the oldest data when full rather than the newest?

The write pointer loops back to the position of the oldest unread slot, and "after the last slot comes the first," so the value it lands on is the oldest one still present — the same wrap-around as a CLL walking past its tail onto the head.

Why can you detect "one full lap" without a counter in a CLL?

Because the loop is closed, arriving back at the exact node you started from is the unambiguous signal that every node was visited once — no separate count needed.

Edge cases

What does traversal do on a single-node CLL where node.next = node (the self-loop A→A)?

It visits the node once (the do-while body), then the test p==start is true immediately, so it stops correctly after one visit.

What is the correct empty-CLL representation, and how does the first insert differ?

Empty is head = null (and tail = null); the first insert is special-cased to node.next = node; tail = node so the single node loops to itself (A→A).

When the Josephus circle shrinks to one node, how does the CLL look?

The survivor's next points to itself (A→A, a one-node CLL); no more eliminations are possible because counting stays on that single node.

What happens if you try to delete the only node from a CLL?

You return to the empty representation: set both head and tail to null (or your empty marker), rather than relinking, since there is no other node's prev/next to reattach.

In a two-node CLL A→B→A, what does deleting A require?

Set B.next = B (B becomes the self-loop B→B), then update head = B and tail = B; forgetting the self-loop would leave B's next dangling into freed memory.

For a full Ring Buffer where read and write pointers meet, how do you distinguish "full" from "empty"?

Both states have the pointers coinciding, so you need an extra flag (or keep one slot empty / track a count); the pointer positions alone are ambiguous.

Recall One-line self-test before you move on

Cover this and recite: the loop is closed, so we stop at start not null, we store the tail to derive the head, first insert points to itself (A→A), and deletion is == $O (1)$ == by relinking.