What is the time complexity of inserting a new node at the head of a circular singly linked list with a tail pointer, assuming the list is non-empty?

• A. O(1)
• B. O(n)
• C. O(log n)
• D. O(n log n)

Answer: (A)

In a circular singly linked list with a tail pointer, the node after the tail is the head. Inserting at the head means placing a new node right after the tail, so it becomes the new head while the tail stays the same. You just create the new node, set its next to the current head (tail->next), and update tail->next to point to the new node. This is a fixed set of pointer updates that does not depend on how many nodes are in the list, so it runs in constant time. Therefore, the operation is O(1). The non-empty condition simply means there is a tail to reference; inserting into an empty list would require initializing a single node that points to itself, which is still constant time.