Question

Consider a procedure LIST-SEARCH (L, K) finds the first element with key K in list L by simple linear search, returning a pointer to its element. Arrange the following according to correct order of execution.
• [A.] x = L.head
• [B.] while x $\neq$ NIL and x.key $\neq$ K
• [C.] return x
• [D.] x = x.next
Choose the correct answer from the options given below:

• A. A, B, D, C
• B. B, C, D, A
• C. A, D, B, C
• D. A, B, C, D

Hint:

Traversal always follows: Initialize → Check → Move → Return.

Answer 1

The Correct Option is A

Concept: Linear search in a linked list involves sequential traversal.

Step 1: Initialize pointer. \[ x = L.head \] \[ \Rightarrow A \]

Step 2: Check condition.
• Continue until:
• End of list OR element found \[ \text{while } x \neq NIL \text{ and } x.key \neq K \] \[ \Rightarrow B \]

Step 3: Move to next node. \[ x = x.next \] \[ \Rightarrow D \]

Step 4: Return result. \[ \text{return } x \] \[ \Rightarrow C \]

Step 5: Final sequence. \[ A \rightarrow B \rightarrow D \rightarrow C \] \[ \boxed{(1)} \]