0 votes 0 votes In a linked list with $n$ nodes, the time taken to insert an element after an element pointed by some pointer is: $(A) O(1)$ $(B) O(logn)$ $(C) O(n)$ $(D) O(nlogn)$ DS data-structures linked-list + – Lakshman Bhaiya asked Oct 17, 2018 edited Oct 17, 2018 by Lakshman Bhaiya Lakshman Bhaiya 25.3k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes To insert an element after an element pointed by some pointer in a linked list will take constant time (only the next pointers of the newly inserted node and the node pointed to by the pointer needs to be changed). So ans is option (a) O(1). Somoshree Datta 5 answered Oct 17, 2018 Somoshree Datta 5 comment Share Follow See all 8 Comments See all 8 8 Comments reply Lakshman Bhaiya commented Oct 17, 2018 reply Follow Share Suppose element pointed by some pointer is last node(tail),From the head node we traverse the entire list and reached the last node(tail). So.it takes $O(n)$ times and some pointer manipulation time. So final Time complexity is $T(n)=O(n)$ 1 votes 1 votes Lakshman Bhaiya commented Oct 17, 2018 reply Follow Share But the answer is $(A)$ 0 votes 0 votes Somoshree Datta 5 commented Oct 17, 2018 reply Follow Share ya its right.. Why would you traverse the linked list again? Pointer is already given to the node where insertion needs to be performed. So it becomes a constant time operation. 0 votes 0 votes Lakshman Bhaiya commented Oct 17, 2018 reply Follow Share I think already some pointer pointed the element (it is given in the question), so we simply insert the new node. So it takes $O(1)$ times. 0 votes 0 votes Verma Ashish commented Oct 17, 2018 reply Follow Share @LakshmanLakshman how can it be O(n) if pointer is pointing to last node.. Then also we can insert in O(1) time.. isn't it? 0 votes 0 votes Somoshree Datta 5 commented Oct 17, 2018 reply Follow Share @Verma Ashish yes it will take constant time 0 votes 0 votes Lakshman Bhaiya commented Oct 17, 2018 reply Follow Share @Verma Ashish see my above comment. Yeah, it takes $O(1)$ times because already some pointer pointed to the element.(If some pointer does not point the element and we want to insert the element at the end of the linked list(tail sometimes it is called rear of the linked list) , it takes $O(n)$, because we traverse the entire list, from the start node(head, sometimes it is called front of the linked list) 0 votes 0 votes Navneet Kalra commented Oct 17, 2018 reply Follow Share Let the pointer pointing to element be x now we create a new node y now to insert y we point next pointer of y to the node pointed by next pointer of x and then point the next pointer of x to y....we are done inserting the element 0 votes 0 votes Please log in or register to add a comment.