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. HEAD then 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.

Insertion at the end

Adding a node at the end means finding the current last node first, since it's the one whose NEXT needs to be redirected onto the new node, and it's the new node itself that must take over the wraparound to HEAD.

INSERT_END(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. PTR->next = NEW
7. NEW->next = HEAD
8. Return HEAD

Example: inserting 40 at the end of 10 → 20 → 30 → (back to 10). Steps 4-5 walk PTR forward until PTR->next == HEAD, landing on the current last node, 30:

Step 6 sets PTR->next = NEW, attaching 40 after the old last node. Step 7 sets NEW->next = HEAD, so the wraparound now lands on 40 instead of 30:

Insertion after a given node

Once the node to insert after is already known, no walk is needed at all, the new node just needs to be spliced in between it and whatever came next.

NEW->next = PTR->next
PTR->next = NEW

Example: inserting 25 after the node holding 20, in the circular list 10 → 20 → 30 → (back to 10). PTR is the node holding 20, found beforehand:

The first line sets NEW->next = PTR->next (the node holding 30), wiring NEW forward before PTR stops pointing at 30 directly. The second line sets PTR->next = NEW, so 20 now points at 25 instead of 30:

The order matters here for the same reason it does in a plain singly linked list: NEW->next has to be set before PTR->next is overwritten, otherwise the link to the rest of the list, including the wraparound to HEAD, would be lost. Once PTR is known, inserting after it is O(1), exactly like a plain singly linked list. Whether that insertion point happens to be the last node or not doesn't matter here, unlike inserting at the end starting from HEAD, which still has to walk to find it.

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.

Deletion at the head

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.

Deletion of a specific node

Deleting a node that isn't the head means finding the node just before it first, since that's the only node whose NEXT needs to change to skip over the deleted one.

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

Example: deleting the node holding 20 from 10 → 20 → 30 → (back to 10). Since HEAD->data != 20, step 2 doesn't fire, so steps 3-4 walk PTR forward, stopping as soon as PTR->next->data == KEY, at the node just before the one being deleted, the node holding 10:

Step 6 sets TEMP to the node being removed (20). Step 7 sets PTR->next = TEMP->next, so 10 now points directly at 30, skipping over 20 entirely, and step 8 frees TEMP:

Reusing DELETE_HEAD for step 2 rather than duplicating its logic keeps the single-node and empty-list edge cases handled in exactly one place. Deleting a specific node is O(n): even though the deletion itself is a constant number of pointer updates, finding the predecessor first requires walking the list, exactly like deleting a specific node from a plain singly linked list.

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.
• Inserting at the beginning or the end both cost O(n) without a maintained TAIL pointer, since the last node has to be found by walking either way; inserting after an already-known node is O(1).
• Deleting the last remaining node needs a separate check (HEAD->next == HEAD), otherwise the freed node would incorrectly keep pointing at itself. Deleting any other specific node is O(n), since finding its predecessor still requires a walk.
• Without a maintained TAIL pointer, operations needing the last node cost O(n) to find it, same limitation as a plain singly linked list without a tail pointer.