Log In

linked list [closed]

1 vote

Let P be a single linked list.Let Q be a pointer to an intermediate node 'X' in the list.What is the worst case time complexity of best known algorithm to delete the node 'X ' from the list

closed as a duplicate of: GATE2004-IT-13
in Programming
closed by
is ans O(n) ?
O(1) as it's given that it's an intermediate node.
@Manu Thakur Suppose you are given a pointer Q which points to the current node (the one that is to be deleted which is intermediate). Now if we want to delete it then the next address of the previous node must point to the next of the present node. Since it is a singly linked list hence we do not have a pointer to the previous node, in order to obtain that pointer we need to traverse the list. This will take o(n).

And intermediate means it can be last but one node also.

Correct me if I am wrong
i think pointer is pointing to the element which we have to delete so it will take O(1)

Suppose we have a linked list as follows

A->B->C->D->E and pointer q is given to the node B as B is to be deleted. =; =;

now our modified linked list is


B is removed successfully in O(1) we can do such removal in O(1) except last node deletion.
Ohh I got my mistake. Thankyou so much @Manu Thakur

Manu Thakur

but by your operation previous node of Q how get connected to Q->next only Q pointer will be point toQ->next

@abhishek node is deleted we can set q to null. because job has been done and we don't require it anymore. And B is already connected to A, we don't need to worry about it. we copied data from Node C and connected it to D.
@abhishek Here content of node to which Q is pointing already changed. Hence to need to again point prev of Q to next of Q.

we need another pointer who will point to previous node of Q

P->next=Q; then again A will point to C


but for this question we do not have to do  @ Manu Thakur sir ??

@abhishek why do you need a pointer the the previous node of the node pointedby q? it is written in the question node to be deleted is an intermediate node.

if question is to delete the last node then we need a pointer which will point to the second last node. hence to delete last TC is O(n) and other than last node each node can be deleted in O(1)

Related questions

0 votes
0 answers
struct node* foo(struct node* a, struct node* b) { struct node* result, *rec; if(a==null) return b; else if(b==null) return a; else { rec=foo(a->next,b->next); result=a; a->next=b; b->next=rec; return result; } }
asked Sep 17, 2018 in Programming Vaishnavi01 253 views
0 votes
1 answer
What kind of linked list is best to answer question like “What is the item at position n?” a) Singly linked list b) Doubly linked list c) Circular linked list d) Array implementation of linked list
asked Aug 19, 2018 in Programming pradeepchaudhary 663 views
5 votes
1 answer
What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list? O(n) O(1) θ(n2) θ(n)
asked Nov 14, 2017 in Programming hacker16 1.9k views
4 votes
1 answer
I was trying to implement the Linked List code in C. It compiles fine but doesn't give any output. What seems to be the error? I think I messed up at passing pointer references as function parameters. My Code (Insert At Beginning): #include <stdio.h> ... to the head node(pointer to pointer) to the function. - Return the modified head node by the function. Please read about Reference Semantics.
asked Apr 26, 2017 in Programming RahulVerma 330 views