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