Question

Suppose you are given pointers to the first and the last nodes of a singly linked list, which one of the following operations would require traversal of the linked list?

• A. Delete the first node
• B. Insert a new node as the first node of the list
• C. Delete the last node of the list
• D. Insert a new node at the end of the list

Hint:

In a singly linked list, operations involving the previous node require traversal.

Answer 1

The Correct Option is C

Since each node in a singly linked list only knows the node after it, not the one before it, any operation that only touches the very first or very last node can be done instantly through the head or tail pointer.
Deleting the first node, inserting at the front, and inserting at the end all fall into this category, they only need to rewire one pointer at a known location.
Deleting the last node is different: after removing it, the node before it must become the new tail, and finding "the node before the last one" is only possible by walking the list from the head, since there's no backward link to jump to it directly.
So the correct answer is Delete the last node of the list.

Answer 2

A useful way to check this is to ask, for each operation, whether it only needs a node we already have a pointer to, or whether it needs a node we don't have a direct handle on:

1. Delete the first node: Needs only the first node (already pointed to) and its immediate successor (reachable in one step via its next field). No unknown node is required.
2. Insert a new node as the first node: Needs only the current first node (already pointed to), to link the new node in front of it.
3. Delete the last node: Needs the node immediately before the last node, a node we have no pointer to at all. The only way to obtain a pointer to it is to traverse from the head until the node whose next field points to the last node is found.
4. Insert a new node at the end: Needs only the last node (already pointed to), to attach the new node after it.

Three of the four operations only ever touch nodes we already hold a reference to; only one requires locating a node we have no direct access to.

Therefore, the correct answer is Delete the last node of the list.