Log In
18 votes

Linked lists are not suitable data structures for which one of the following problems?

  1. Insertion sort

  2. Binary search

  3. Radix sort

  4. Polynomial manipulation

in DS
recategorized by
How is it helpful in case of other algorithms?
@Adiaspirant My ans may address ur concern.

3 Answers

29 votes
Best answer

Linked lists are suitable for:

Insertion sort: No need to swap here just find appropriate place and join the link

Polynomial manipulation: Linked List is a natural solution for polynomial manipulation 

Radix sort: Here we are putting digits according to same position(unit,tens) into  buckets; which can be effectively handled by linked lists.

Not Suitable for:

Binary search: Because finding mid element itself takes $O(n)$ time.

So, Option B is answer.

edited by
B also because Binary Search requires random access which isn't possible in case of Binary Search.
22 votes
B. Because in binary search we need to have access to the mid of the list in constant time. and finding the mid itself in a linked list takes $O(n)$ time which makes no sense to Binary search which otherwise takes $O(\log n)$.
11 votes

the answer is B.

 The binary search algorithm is based on the logic of reducing your input size by half in every step until your search succeeds or input  gets exhausted. The important point here is "the step to reduce input size should take constant time". In a case of an array, it's always a simple comparison based on array indexes that take O(1) time.

But in a case of Linked list, you don't have indexes to access items. To perform any operation on a list item, you first have to reach it by traversing all items before it. So to divide list by half you first have to reach the middle of the list then perform a comparison. Getting to the middle of the list takes O(n/2)[you have to traverse half of the list items] and comparison takes O(1).
Total = O(n/2) + O(1) = O(n/2)

So the input reduction step does not take constant time. It depends on list size. hence violates the essential requirement of Binary search.

edited by
please edit : answer as b

Related questions

1 vote
2 answers
The efficient data structure to insert/delete a number in a stored set of number is Queue Linked list Doubly linked list Binary tree
asked Jul 20, 2016 in DS jothee 1.4k views
20 votes
6 answers
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence $\text{1, 2, 3, 4, 5}$ in that order? $\text{3, 4, 5, 1, 2}$ $\text{3, 4, 5, 2, 1}$ $\text{1, 5, 2, 3, 4}$ $\text{5, 4, 3, 1, 2}$
asked Oct 4, 2014 in DS Kathleen 7.5k views
46 votes
11 answers
In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size $n \times n$ ... this new representation is: $i+j$ $i+j-1$ $(j-1)+\frac{i(i-1)}{2}$ $i+\frac{j(j-1)}{2}$
asked Oct 4, 2014 in DS Kathleen 9k views
1 vote
1 answer
Consider the In-order and Post-order traversals of a tree as given below: In-order: j e n k o p b f a c l g m d h i Post-order: j n o p k e f b c l m g h I d a The Pre-order traversal of the tree shall be a b f e j k n o p c d g l m h i a b c d e f j k n o p g l m h i a b e j k n o p f c d g l m h i j e n o p k f b c l m g h I d a
asked Jul 20, 2016 in DS jothee 2k views