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.