CODEWITHSUNDEEP
cqueue
Bob Dylan
Bob Dylan

Reputation: 17

How to remove a set node from a queue

I am looking to remove a set node from my queue. Say that I search for select node by name-I.D. I know how to remove something from the front of the queue, but am getting confused about how to remove something at a user set point(say midway).

My function:

void retrieveAndRemove(linkedPtr*hd, int size){
linkedPtr temp = *hd;


   if (hd == NULL){
    printf("List is empty!");

   }
    while( temp != NULL){
        if (temp->status == IN_RESTAURANT && temp->size == size){

            //HERE is where I am stuck, how do i now re-arrange the que
            //Such that the node gets removed and the next node is linked
            free(temp);
            return;

        }
        temp = temp->next;
    }

}

Upvotes: 0

Views: 651

Answers (1)

R Sahu
R Sahu

Reputation: 206567

When you need to remove a node from the middle of a linked list you'll need to keep track of the previous node. This will allow you to reset the links in the linked list.

Starting state:

                         Node to be removed
                            |
                            v
+-------+                +-------+             +-------+
| node1 |  -- next -->   | node2 | -- next --> | node3 |
+-------+                +-------+             +-------+

Ending state:

+-------+                                      +-------+
| node1 |                -- next -->           | node3 |
+-------+                                      +-------+

Here's a revised version of your function that should work.

// This wont work for the case when the head needs to be removed.
// void retrieveAndRemove(linkedPtr*hd, int size) {

void retrieveAndRemove(linkedPtr** hd, int size) {

   linkedPtr prev = **hd;
   linkedPtr cur = prev;

   if (hd == NULL){
      printf("List is empty!");
      return;
   }

   // Take care of the case where the item to be removed is at the head.
   if ( cur->status == IN_RESTAURANT && cur->size == size) {
      *hd = cur->next;
      free(cur);
   }

   // Take care of the case where the item to be removed is in the middle.
   while( cur != NULL) {
      if (cur->status == IN_RESTAURANT && cur->size == size){

         // Fix the links.
         prev->next = cur->next;
         free(cur);
         return;
      }
      prev = cur;
      cur = cur->next;
   }
}

Upvotes: 1

Related Questions