Linked Lists

Question 1
A
O(log2 N)
B
O(N)
C
O(N2)
D
Θ(N2 logN)
       Data Structures       Linked Lists       GATE 2016 set-2
Question 1 Explanation: 
In Doubly linked list (sorted)
→ Delete needs O(1) time
→ Insert takes O(N) time
→ Find takes O(N) time → Decrease by takes O(N) time
Now number of each operation performed is given, so finally total complexity,
→ Delete = O(1) × O(N) = O(N)
→ Find = O(N) × O(log N) = O(N log N)
→ Insert = O(N) × O(log N) = O(N log N)
→ Decrease key = O(N) × O(N) = O(N2)
So, overall time complexity is, O(N2).
Question 2

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

A
O(n)
B
O(log2 n)
C
O(logn)
D
O(1)
       Data Structures       Linked Lists       Gate 2004-IT
Question 2 Explanation: 
Worst case complexity for deleting a node from singly linked list is O(1).
Question 3
Linked lists are not suitable data structures of which one of the following problems?
A
Insertion sort
B
Binary search
C
Radix sort
D
Polynomial manipulation
       Data Structures       Linked lists       Gate-1994
Question 3 Explanation: 
In linked list finding an element take O(n) which is not suitable for the binary search. And time complexity of binary search is O(log n).
There are 3 questions to complete.