GATE CSE
First time here? Checkout the FAQ!
x

Linked List [closed]

+2 votes
1.6k 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.5k points) 6 24 35
closed by | 1.6k 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 (34.8k points) 11 82 292
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,,, :)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23324 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7808 Points

  4. srestha

    6222 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4958 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4286 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points


Recent Badges

Popular Question iarnav
Notable Question makhdoom ghaya
Popular Question LavTheRawkstar
Avid Voter atul_21
Popular Question hem chandra joshi
100 Club nikhil_cs
Notable Question Sukannya
Notable Question Sourabh Kumar
Notable Question shikharV
Nice Comment Sachin Mittal 1
27,287 questions
35,134 answers
83,911 comments
33,223 users