The Gateway to Computer Science Excellence
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)$

in DS by
edited by | 178 views

1 Answer

+1 vote
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).
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). takes $O(n)$ times and some pointer manipulation time.

So final Time complexity is $T(n)=O(n)$
But the answer is $(A)$
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.
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.
@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?
@Verma Ashish yes it will take constant time

@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)


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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,314 questions
60,435 answers
95,251 users