GATE CSE
First time here? Checkout the FAQ!
x

Linked List [closed]

+2 votes
551 views
Linked Lists are not suitable for _____.

A.    Binary Search
B.    Polynomial Manipulation
C.    Insertion
D.    Radix Sort
closed as a duplicate of: GATE1994-1.17, UGCNET-Sep2013-II-32
asked in DS by Active (1.4k points)  
closed by | 551 views

1 Answer

+4 votes
Best answer

Correct Answer would be A) Binary Search

Because, Its will take $O(n/2)$ times for finding the middle element of the Linked list. 

 

answered by Veteran (33.9k points)  
selected by
Why can;t we use binary search on a Linked List if all the elements of Linked List are in sorted order ?
In sorted order, still we have to traverse to the middle of linked list which takes O(n/2) which is O(n) only .

but, this can be made O(log n) by augmenting linked list with extra pointers like DLL, called skip list so that we can move in both the directions. which can give O(log n ) but not always, bcoz still worst is O(n).
@kapil then why do we use binary search in sorted array ? we use the same concept there rt ? we can apply binary search on sorted array to get down the complexity upto O(logn) .don't we need to traverse there ?
Sir, array uses indexing mechanism, we can directly goto a[ i ] and hence by direct access , we can compare our search element to middle element and then recur for left or right half..

@kapil thanks ...this indicates i know nothing about anything laugh

@shekhar sir,

your doubts help me very much to revise all the concepts and be up to date...

keep it up sir,,, :)

Related questions



Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Arnab Bhadra

    1502 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1481 Points

  5. junaid ahmad

    1432 Points

  6. Debashish Deka

    1384 Points

  7. Rupendra Choudhary

    1220 Points

  8. rahul sharma 5

    1220 Points

  9. Arjun

    1158 Points

  10. srestha

    1006 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. Arjun

    198 Points

  2. akankshadewangan24

    152 Points

  3. Debashish Deka

    138 Points

  4. Hira Thakur

    130 Points

  5. Soumya29

    104 Points


23,399 questions
30,111 answers
67,489 comments
28,424 users