GATE CS 2002 Q1.5 — Linked Lists

In a singly linked list, elements are accessed sequentially starting from the head node because there is no direct indexing (random access) available.

To search for a target element in a singly linked list of length $n$:

• Best Case: The element is at the first position (head of the list), requiring $1$ comparison.
• Average Case: The element is located somewhere in the middle, requiring approximately $\frac{n}{2}$ comparisons on average.
• Worst Case: The element is either at the very end of the list (the $n$-th node) or is not present in the list at all. In this case, we must traverse and compare all $n$ elements.

Thus, the number of comparisons needed in the worst case is $n$.