Log In

Linked List [closed]

4 votes
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
in DS
closed by

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. 

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

2 votes
2 answers
Why linked list not suitable for binary search?
asked Apr 4, 2016 in DS Anjali Raghu 416 views
0 votes
0 answers
why we use double pointer struct Node** head here? can anyone explain with details /* Given a reference (pointer to pointer) to the head of a DLL and an int, appends a new node at the end */ void append(struct Node** head_ref, int new_data) { struct Node* new_node = ( ... new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; new_node->prev = last; return; }
asked May 24, 2019 in DS Arun Rout 234 views
0 votes
2 answers
Can somebody write the code or algorithm, how merge sort works efficiently in linked list? Is Heap sort most inefficient in Linked List Sorting? Elaborate plz
asked Apr 29, 2019 in DS srestha 198 views
0 votes
1 answer
What does the following program do on two linked lists? Struct node *myFun (struct node * a, struct node * b) { Struct node *new = NULL ; If (a = = NULL) return (b) ; if (b = = NULL) return (a) ; If (a → data <= b → ... merges two linked lists by selecting the alternate nodes merges two sorted linked lists into final sorted linked list merges two linked lists by selecting the nodes in reverse.
asked Dec 27, 2018 in DS sharadsingh 220 views