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.
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).
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).
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
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).
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).
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).
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)
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).
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).
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
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
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).
Helpful to revise my deta structure knowledge.