Link List Data Structure Mock Test – 2

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.
A
O(\log n)
B
O(n)
C
O(1)
D
O(n^2)
   Data Structure
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
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.
A
O(\log n)
B
O(n)
C
O(1)
D
O(n^2)
   Data Structure
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
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
A
O(1) O(1)
B
O(1) O(n)
C
O(n) O(1)
D
O(n) O(n)
   Data Structure
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
Question 4
What is the time complexity to delete a node pointed by pointer P from a single link list?
A
O(n^2)
B
O(n)
C
O(1)
D
O(\log n)
   Data Structure
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?
A
O(n^2)
B
O(n)
C
O(1)
D
O(\log n)
   Data Structure
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?
A
O(n^2)
B
O(n)
C
O(1)
D
O(\log n)
   Data Structure
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
Question 7
What is the time complexity of deleting the first element from a circular single link list?
A
O(n^2)
B
O(n)
C
O(1)
D
O(\log n)
   Data Structure
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?
A
O(n^2)
B
O(n)
C
O(1)
D
O(\log n)
   Data Structure
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
Question 9
What is the time complexity of reverse the single link list?
A
O(n^2)
B
O(n)
C
O(1)
D
O(\log n)
   Data Structure
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
A
O(1) O(1) O(1) O(1)
B
O(1) O(1) O(n) O(n)
C
O(1) O(1) O(n) O(1)
D
O(1) O(n) O(n) O(1)
   Data Structure
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
There are 10 questions to complete.

1 thought on “Link List Data Structure Mock Test – 2”

Leave a Comment