Question 1 |

What is the time complexities of finding median element from a sorted singly linked list?

Note: The median of a finite list of numbers is the "middle" number, when those numbers are listed in order from smallest to greatest.

Note: The median of a finite list of numbers is the "middle" number, when those numbers are listed in order from smallest to greatest.

O(\log n) | |

O(n) | |

O(1) | |

O(n^2) |

Question 1 Explanation:

Median element is present at middle of the sorted link list. Hence, it require the traversal of n/2 nodes from the starting of link list.

Hence, it takes O(n).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Hence, it takes O(n).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 2 |

What is the time complexity to search an element from a sorted single link list?

NOTE/HINT : Binary search concept with sorted array.

NOTE/HINT : Binary search concept with sorted array.

O(\log n) | |

O(n) | |

O(1) | |

O(n^2) |

Question 2 Explanation:

Binary search technique can be used in sorted array but not in link list. As binary search requires the middle element in O(1) time which is not possible in link list while it is possible in array. Hence, only sequential search is possible to search an element from sorted link list which require O(n).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 3 |

What are the time complexities of finding 7th smallest element from beginning and 7th largest element from end in a sorted singly linked list?

Let n be the number of nodes in linked list, you may assume that n > 7

Let n be the number of nodes in linked list, you may assume that n > 7

O(1) O(1) | |

O(1) O(n) | |

O(n) O(1) | |

O(n) O(n) |

Question 3 Explanation:

In sorted single link list, 7th smallest element is present as 7th node from the starting. Hence, only we have to traverse 7 node from the starting node irrespective of number of node in link list n. Hence, it can be found on O(1).

In sorted single link list, 7th largest element is present as 7th node from the end of link list. To find that element, we have to traverse the link list starting to end. Hence, it will take O(n).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

In sorted single link list, 7th largest element is present as 7th node from the end of link list. To find that element, we have to traverse the link list starting to end. Hence, it will take O(n).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 4 |

What is the time complexity to delete a node pointed by pointer P from a single link list?

O(n^2) | |

O(n) | |

O(1) | |

O(\log n) |

Question 4 Explanation:

As shown in the above figure, to delete node pointed by P we requires the pointer of previous node of P. To get the pointer of previous node of P, we have to start traversal from starting to that node. Hence, it will depends on number of node in link list. Hence, it will take O(n).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 5 |

What is the time complexity to delete a node pointed by pointer P from a double link list?

O(n^2) | |

O(n) | |

O(1) | |

O(\log n) |

Question 5 Explanation:

As shown in the above figure, to delete node pointed by P we requires the pointer of previous node of P. It can be found in O(1) as P -> prev.

So, total two pointer need to be change as shown on above figure. That can be done in O(1).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 6 |

What is the time complexity to find intersection of two single link list each of length n?

O(n^2) | |

O(n) | |

O(1) | |

O(\log n) |

Question 6 Explanation:

For finding intersection of two link list, we select one element from one link list and search it in second link list. If that element is present then added in resultant link list otherwise it is ignored. This can be done in O(n) time. Now, we have to repeat that procedure for each element of first link list. So total time complexity is n* O(n) = O(n^2)

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 7 |

What is the time complexity of deleting the first element from a circular single link list?

O(n^2) | |

O(n) | |

O(1) | |

O(\log n) |

Question 7 Explanation:

To delete the first node of the link list, we have to update the last node's next pointer. To update the pointer, we have to reach at the last node. This traversal to last node require the O(n) time. Then pointers can be updated in O(1) time. SO total time require is O(n).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 8 |

What is the time complexity of deleting the first element from a circular double link list?

O(n^2) | |

O(n) | |

O(1) | |

O(\log n) |

Question 8 Explanation:

To delete the first node of the link list, we have to update the last node's next pointer. To update the pointer, we have to reach at the last node. We can reach to last node from the head node in O(1) time using last = head -> prev.

Then pointers can be updated in O(1) time. So total time require is O(1).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Then pointers can be updated in O(1) time. So total time require is O(1).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 9 |

What is the time complexity of reverse the single link list?

O(n^2) | |

O(n) | |

O(1) | |

O(\log n) |

Question 9 Explanation:

```
Algorithm to reverse a Singly Linked List
%%Input : head node of the linked list
Begin:
If (head != NULL) then
prevNode = head
head = head.next
curNode = head
prevNode.next = NULL
While (head != NULL) do
head = head.next
curNode.next = prevNode
prevNode = curNode
curNode = head
End while
head = prevNode
End if
End
```

This can be run in O(n) time.Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 10 |

What is the time complexity to insert a node at the first position in

(1) Single Link List

(2)Double Link list

(3) Circular Single Link list

(4)Circular Double Link List

(1) Single Link List

(2)Double Link list

(3) Circular Single Link list

(4)Circular Double Link List

O(1) O(1) O(1) O(1) | |

O(1) O(1) O(n) O(n) | |

O(1) O(1) O(n) O(1) | |

O(1) O(n) O(n) O(1) |

Question 10 Explanation:

Consider "head" as the pointer of the first node and "Newnode" as pointer to the node which we want t0 insert

(1) Single Link List

Newnode -> next = head

head=Newnode

This can be done in O(1)

(2)Double Link list

Newnode -> next = head

head -> prev = Newnode

head=Newnode

This can be done in O(1)

(3) Circular Single Link list

It required the pointer of the last node(assume it is "last") which can be found in O(n) time by traversing the link list to last node. After that pointers can be updated in O(1) time as follow:

last -> next = Newnode

Newnode -> next = head

head = Newnode

So Total time is O(n)

(4)Circular Double Link List

It required the pointer of the last node(assume it is "last") which can be found in O(1) time using last = head ->prev

After that pointers can be updated in O(1) time as follow:

last -> next = Newnode

Newnode -> next = head

Newnode -> prev = last

head -> prev = Newnode

head = Newnode

So Total time is O(1).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

(1) Single Link List

Newnode -> next = head

head=Newnode

This can be done in O(1)

(2)Double Link list

Newnode -> next = head

head -> prev = Newnode

head=Newnode

This can be done in O(1)

(3) Circular Single Link list

It required the pointer of the last node(assume it is "last") which can be found in O(n) time by traversing the link list to last node. After that pointers can be updated in O(1) time as follow:

last -> next = Newnode

Newnode -> next = head

head = Newnode

So Total time is O(n)

(4)Circular Double Link List

It required the pointer of the last node(assume it is "last") which can be found in O(1) time using last = head ->prev

After that pointers can be updated in O(1) time as follow:

last -> next = Newnode

Newnode -> next = head

Newnode -> prev = last

head -> prev = Newnode

head = Newnode

So Total time is O(1).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

There are 10 questions to complete.

Helpful to revise my deta structure knowledge.