Tutorial :How to remove an item from a structure array in C++?



Question:

I have the following array structure (linked list):

    struct str_pair          {           char ip  [50] ;           char uri [50] ;           str_pair *next ;         } ;    str_pair *item;  

I know to create a new item, I need to use

item = new str_pair;  

However, I need to be able to loop through the array and delete a particular item. I have the looping part sorted. But how do I delete an item from an array of structures?


Solution:1

What you've shown is not an array of struct, but a linked list of struct containing arrays (of type char).


An array of struct would look like this:

str_pair array_of_structs[10];      // or:  str_pair* dynamically_allocated_array_of_structs = new str_pair[10];  

If you actually have something like this, you don't need to delete single items from an array. Let's say you've initialized your array as follows:

str_pair* array_of_structs = new str_pair[10];  

Then you delete the whole array (including all of its items) using:

delete[] array_of_structs;  

Again, you can't delete single items in an array allocated with new[]; you perform a delete[] on the whole array.


If, on the other hand, you intended to say "linked list of struct", then you'd generally delete an item similarly to the following:

str_pair* previous_item = ...;  str_pair* item_to_delete = previous_item->next;    if (item_to_delete != 0)  {      previous_item->next = item_to_delete->next;  // make the list "skip" one item      delete item_to_delete;                       // and delete the skipped item  }  

Or, in English: Find the item (A) preceding the item which you want to delete (B), then adjust A's "next" pointer so that B will be skipped in the list, then delete B.

You need to be careful with special cases, i.e. when the item to be removed from the list is the first item or the last one. The above code is not sufficient when you want to delete the first item in the list, because there will be no previous_item. In this case, you'd need to change the pointer to the list's first element to the second element.


Your code:

void deleteitem(char *uri)  {      str_pair *itemtodelete;      curr = head;        while (curr->next != NULL) {      if ((strcmp(curr->uri, uri)) == 0) {          itemtodelete = curr;          curr = itemtodelete->next;          delete itemtodelete;            curr = head;          return;      }        curr = curr->next;      }  }  

Some things are wrong here:

  • If head is null, the test curr->next != NULL will cause a segfault. (You must never dereference a null pointer!)

  • Your code for removing an item from the list is completely incorrect. Worst of all, you delete a node without changing the previous item's next pointer. The previous item will thus reference an item that's no longer there.

  • A detail: curr = head; before the return statement doesn't do anything useful at all.

Suggested code:

Do it in two steps: One function to find the node to be deleted via its attached uri, and one function to remove the node. You could separate it even better than the code below does, but it should be a starting point:

str_pair* finditemwithuri(char* uri)  {      str_pair* current = head;      while (current)      {          if (strcmp(current->uri, uri) == 0) return current;          current = current->next;      }      return 0;  }    void deleteitem(char* uri)  {      // find linked list node with that uri; abort if uri not in list      str_pair* itemtodelete = finditemwithuri(uri);      if (!itemtodelete) return;        // special case: node to be deleted is the list's head      if (itemtodelete == head)      {          head = itemtodelete->next;          delete itemtodelete;          return;      }        // else, iterate over list nodes      // up to the one preceding the node to be deleted      str_pair* current = head;      while (current)      {          if (itemtodelete == current->next)          {              current->next = itemtodelete->next;              delete itemtodelete;              return;          }          current = current->next;      }  }  


Solution:2

Just use std::list. There's no reason to manually write such a construct.

http://msdn.microsoft.com/en-us/library/802d66bt(VS.80).aspx

std::list offers remove.


Solution:3

You can delete it using the ordinary delete keyword, but that will not shift all other members of the array. If you want this kind of behaviour take a look at std::vector or something like that.


Solution:4

It is maybe off topic, but why dont you use the std::list library ?


Solution:5

As others have pointed out, this is a Linked List, not an array. To answer your question for linked lists:

To insert an item:

str_pair* p = // iterate over the linked list to your insertion point  str_pair* item = new str_pair;  item->next = p->next;  p->next = item;  

That inserts a new str_pair after p.

To remove an item:

str_pair* p = // iterate to just before your deletion point  str_pair* item = p->next;  p->next = p->next->next;  delete item;  

This will remove the element after p

To do this with your code:

void deleteitem(char *uri)  {      str_pair *previous = NULL;      curr = head;        while (curr != NULL) {          if ((strcmp(curr->uri, uri)) == 0) {                // modify the previous element to skip over our deleted one              if (previous)                  previous->next = curr->next;              else                  head = curr->next;                // safely delete the element, now that no one points to it              delete curr;                curr = head;              return;          }            // always remember our previous element, so we can fix its 'next' pointer          previous = curr;          curr = curr->next;      }  }  

You need a better add method too:

void additem(char *uri, char *ip)  {      curr = head;        // traverse the list until we're at the last item      while (curr->next != NULL) {          curr = curr->next;      }        // attach a new element to the list      curr->next = new str_pair;        // go to that new element      curr = curr->next;        // set the values of the new element      strcpy(curr->ip, ip);      strcpy(curr->uri, uri);      curr->next = NULL;        curr = head;    }  

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »