GATE CS 1994 Q1.17 — Linked Lists

The correct option is B: Binary search.

Here is a detailed explanation of why linked lists are unsuitable for binary search, while being highly suitable for the other options:

• Binary Search (Option B): Binary search relies on the ability to access the middle element of any subsegment in $O(1)$ time (random access). In a linked list, accessing the $i$-th element requires traversing from the head, taking $O(i)$ time. Consequently, performing a binary search on a linked list of size $N$ takes $O(N)$ time, which defeats the purpose of the algorithm.
• Insertion Sort (Option A): Insertion sort can be efficiently implemented on linked lists. Once the insertion position is found, inserting a node requires only $O(1)$ pointer updates, without needing to shift subsequent elements (unlike in an array).
• Radix Sort (Option C): Radix sort distributes elements into buckets. Linked lists are ideal for representing these buckets because they can grow dynamically, avoiding the overhead of pre-allocating fixed-size arrays for each bucket.
• Polynomial Manipulation (Option D): Polynomials are standard applications of linked lists. Each term of the polynomial (coefficient and exponent) is represented as a node. This allows easy addition, subtraction, and multiplication by dynamically traversing and merging the lists.