CODEWITHSUNDEEP
cdata-structureslinked-list
vijay
vijay

Reputation: 2034

delete a particular element from a single linked list (no access to header of list)

I need to delete an element from linked list where address of that element is given.Something like this

1->2->3->4->5 a1 a2 a3 a4 a5 where a1,a2..a5 are addresses of elements 1,2 ..5 respectively. sum1 just says delete(a3) N since I have no access to header of given list. I cant traverse the whole linked list and compare the address with the asked address.

Question is how I delete a particular element from the given list with no other information given.

Upvotes: 2

Views: 856

Answers (4)

Anshul garg
Anshul garg

Reputation: 233

as you don't have header of list you can't traverse list
but you are provided with node to delete
so you can copy next node into it and delete next node

suppose a1 -> to delete
if(a1 && a1->next)
{
   a1=a2;
delete a1;
} 
else if(a1)
{
   delete a1;
}
else
 return NULL;

Upvotes: 0

Roee Gavirel
Roee Gavirel

Reputation: 19445

this can only work if you don't receive the last value of the list:

void delete(pointerType x)
{
if (x->next == null) return;//this algorithm won't work

//in any other case:
x->value = x->next->value;
pointerType toDelete = x->next;
x->next = x->next->next;
delete toDelete;
}

Upvotes: 1

Frenzy Li
Frenzy Li

Reputation: 156

For the following two reasons:

  • You don't have access to 2->next. This means you can't just simply delete element 3.
  • Treating the list like an array is a bad idea provided that your list is VERY long.

You have to work on a local scale. My solution in words is:

  1. assign a4 to a3 (so 2->next is a4 and the new a3->next = a5).
  2. delete the old a4

Hope that helps.

Upvotes: 0

Luchian Grigore
Luchian Grigore

Reputation: 258558

Classic interview question.

You don't delete that element, but copy the next element into it:

So you do:

  • a3 = a4
  • delete a4

Upvotes: 3

Related Questions