Circular Linked List

In a singly linked list, the last node's NEXT is NULL, marking a dead end. A circular linked list changes exactly one thing: the last node's NEXT points back to the first node instead, turning the chain into a loop with no end at all.

Structure

Unlike a standard singly linked list, the last node (30) has no NULL terminator, its NEXT field wraps back around to the first node (10). Traversal never naturally stops here, since there's always a next node to move to; a loop has to explicitly check when it has come back to where it started.

Insertion at the beginning

Inserting a new node at the front means the new node still needs to link forward to the old head, and the last node's NEXT still needs to point at the new head, not the old one.

INSERT_BEGIN(HEAD, ITEM)
 
1. Create NEW
2. NEW->data = ITEM
3. If HEAD == NULL
       NEW->next = NEW
       HEAD = NEW
       Return HEAD
4. PTR = HEAD
5. While PTR->next != HEAD
       PTR = PTR->next
6. NEW->next = HEAD
7. PTR->next = NEW
8. HEAD = NEW
9. Return HEAD

Example 1: inserting into an empty list. Inserting 10 when HEAD == NULL. Step 3 catches this: NEW->next = NEW makes the single node point at itself, satisfying the circular property with only one node in the list, then HEAD moves onto it.

Example 2: inserting into a non-empty list. Inserting 5 at the beginning of a circular list 10 → 20 → 30 → (back to 10). Step 4 sets PTR = HEAD (the node holding 10), then step 5 walks PTR forward until PTR->next == HEAD, that's the last node, the one currently wrapping back to the head:

Step 6 sets NEW->next = HEAD (the old head, 10), and step 7 redirects PTR->next (the last node, 30) onto NEW, so the wraparound now lands on NEW instead of the old head. Step 8 moves HEAD onto NEW:

Finding the last node (step 4-5) requires a full walk, since there's no TAIL pointer kept here, unlike insertion at the beginning of a plain singly linked list, which is O(1) because it never needs to touch the last node at all. Insertion at the beginning of a circular linked list is O(n) without a maintained tail pointer (finding the last node to redirect its NEXT), or O(1) if a TAIL pointer is kept up to date.

Traversal

Traversal has to explicitly check for a return to the starting point, since there's no NULL to signal the end.

TRAVERSE(HEAD)
 
1. If HEAD == NULL
       Return
2. PTR = HEAD
3. Do
       Print PTR->data
       PTR = PTR->next
   While PTR != HEAD
4. Stop

Example: traversing 10 → 20 → 30 → (back to 10). The loop is a do-while, not a while, since the very first check (PTR != HEAD) would immediately be false, PTR starts equal to HEAD, and nothing would ever print. Printing has to happen before the check, guaranteeing every node is visited exactly once:

After printing 10, PTR moves to 20, then 30, printing each in turn. When PTR moves from 30 back to 10, the condition PTR != HEAD becomes false, and the loop stops, having printed 10 20 30, each node exactly once.

Deleting the only node

A circular list with exactly one node points to itself: HEAD->next == HEAD. Deleting that node needs to recognize this case separately from deleting the head of a longer list.

DELETE_HEAD(HEAD)
 
1. If HEAD == NULL
       Return HEAD
2. If HEAD->next == HEAD
       free(HEAD)
       Return NULL
3. PTR = HEAD
4. While PTR->next != HEAD
       PTR = PTR->next
5. TEMP = HEAD
6. HEAD = HEAD->next
7. PTR->next = HEAD
8. free(TEMP)
9. Return HEAD

Example 1: empty list. Deleting from an empty list, HEAD == NULL. Step 1 catches this and returns immediately.

Example 2: single-node list. Deleting the only node in a list holding just 10, where HEAD->next == HEAD. Step 2 catches this directly: the node is freed, and HEAD becomes NULL, an empty list, correctly distinct from a list that still has nodes left.

Example 3: multi-node list. Deleting the head from 10 → 20 → 30 → (back to 10). Since HEAD->next != HEAD, steps 3-4 walk to find the last node (the one whose NEXT wraps back to HEAD), then HEAD moves to the second node and the last node's NEXT is redirected onto the new head, keeping the wraparound intact before the old head is freed.

Skipping the HEAD->next == HEAD check would be a real bug here: without it, step 6 would set HEAD = HEAD->next, which is HEAD itself, and step 7 would make the freed node point at itself forever, corrupting the list instead of emptying it.

Why use a circular linked list

Quick recall

• The only structural difference from a singly linked list: the last node's NEXT points back to HEAD instead of NULL.
• A single-node circular list points to itself: HEAD->next == HEAD.
• Traversal uses a do-while loop, checking PTR != HEAD after printing, since checking before printing would immediately be false and skip every node.
• Deleting the last remaining node needs a separate check (HEAD->next == HEAD), otherwise the freed node would incorrectly keep pointing at itself.
• Without a maintained TAIL pointer, operations needing the last node (like insertion at the beginning) cost O(n) to find it, same limitation as a plain singly linked list without a tail pointer.