What is the time complexity of inserting a new node at the head of a singly linked list?
Correct answer D. O(1)
Explanation
Inserting at the head needs only two pointer updates: the new node's next is set to the current head, and the head is set to the new node. No traversal is involved, so the work is constant. Inserting at the tail of a singly linked list without a tail pointer, however, is O(n) because you must walk to the last node first.
Answer checked How we write and check questions
Discussion