What is the time complexity of pop_back() if only a head pointer is available?

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

Answer: (A)

When you only have access to the head of a singly linked list and you want to remove the last element, you can’t reach that last node directly. You must start at the head and traverse the list until you reach the node just before the last one, so you can set its next pointer to null (and update the head if the list becomes empty). This traversal touches every node along the way in the worst case, so the time grows linearly with the number of elements. With n elements, you perform roughly n−1 steps, giving O(n) time. If you had a tail pointer or were using a doubly linked list, removing the last element could be done in constant time, but with only a head pointer it’s a linear operation. The other options describe faster-than-necessary growth for this scenario, which isn’t achievable here.