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

Step 1: Understanding singly linked lists.
In a singly linked list, each node contains a data field and a pointer to the next node only. There is no pointer to the previous node.
Step 2: Analyzing given operations.
- Deleting the first node requires only updating the head pointer.
- Inserting at the beginning requires only updating the head pointer.
- Inserting at the end can be done directly using the tail pointer.
Step 3: Identifying the operation requiring traversal.
To delete the last node, we must find the second-last node so that its next pointer can be set to \texttt{NULL}. This requires traversing the list from the head.
Step 4: Final conclusion.
Therefore, deleting the last node of a singly linked list requires traversal.

Answer 2

We're given pointers to both the first and last nodes of a singly linked list, and asked which operation still needs a full traversal despite having both ends directly accessible. In a singly linked list, each node only points forward, there is no link back to a previous node.

1. Delete the first node: The head pointer is simply moved to point to the second node (accessible via the current first node's next pointer), and the old first node is freed. No traversal is needed since we already hold the first node directly.
2. Insert a new node as the first node: The new node's next pointer is set to the current first node, and the head pointer is updated to the new node. This is a constant-time operation using the head pointer alone.
3. Delete the last node: Removing the last node means the new last node (the second-to-last one) must have its next pointer set to null, and the tail pointer updated to it. But a singly linked list has no backward pointer, so the only way to find "the node just before the last one" is to start at the head and walk forward until reaching it, a full traversal.
4. Insert a new node at the end: Since the tail pointer already points directly to the last node, the new node can be attached to its next field and the tail pointer updated to the new node, all without walking the list.

Every operation except one can be done directly through the head or tail pointer alone; the exception is the one that needs to locate a node's predecessor, which a singly linked list can't do without walking from the start.

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