CLL Time Complexity
These bounds assume a singly circular linked list with a tail pointer and tail->next as the first node (head), as in the lessons above. n is the number of nodes. Auxiliary space is extra pointer/stack space beyond the list itself.
Time (worst case)
| Operation | Time | Why |
|---|---|---|
| Insert at beginning / end | O(1) |
Fix tail and next links; no full scan. |
Insert at index pos |
O(min(pos, n)) |
Ends are O(1); middle needs walk from head. |
| Delete from beginning | O(1) |
Update tail->next, free old head. |
| Delete from end | O(n) |
Must find predecessor of tail (singly linked). |
| Delete at index | O(n) |
Worst case hits end delete or long walk. |
| Search / traverse full ring | O(n) |
Must visit each node once (stop when back at start). |
| Count nodes | O(n) |
One lap if length not stored. |
Auxiliary space
| Operation | Extra space |
|---|---|
| Insert / delete (iterative) | O(1) |
| Traverse / search | O(1) for a few pointers |
| Storing the list | O(n) for the nodes themselves |
Compared to SLL
With a tail pointer, CLL matches SLL for O(1) insert/delete at both ends (begin/end), except delete at end stays O(n) for singly linked structures—same as SLL without a back pointer.
See the broader comparison in Time Complexity (Linked List) and the CLL pattern in CLL vs SLL, tail pointer.
Key takeaway
The circular shape does not remove the need for a predecessor when deleting the last node with only next links—so delete tail remains O(n). The tail + tail→next idiom makes insert at both ends O(1), which is the usual reason to prefer it in CLL.