C++ Linked list destroy function

Question

Hi again, this is kinda a continue of my last question about linked list. I have worked a little more on it and I got stuck at some functions I need to implement. The one I have question on right now is the destroy() function.

It is supposed to release memory of every list_ item . The approach is to remove every list_item recursivly from the front to the end until NULL is found. However for some reason it will only delete the key value from the struct. The node still there though.

Here's the code The reason I have commented the delete(my_ this) in list_ destroy() is to check so the list_item is deleted.

#include <iostream>

using namespace std;

struct list_item
{
    int key;                // identifies the data
    double value;           // the data stored
    struct list_item* next; // a pointer to the next data
};

// Why do you need this? And why would you want it anyway?
struct my_list
{
    struct list_item* first; // a pointer to the first element of the list
};

//+-----------------------------------------------------
//| Module:      list_init
//| Description: Initiate the list to an empty list
//| Input:       A pointer to the uninitialized list
//| Result:      The list is empty
//| Conditions:  Assumes the list is uninitialized
//+-----------------------------------------------------
void list_init(struct my_list* my_this)
{
    // ADD YOUR CODE HERE (approx 1 line)
    //set the list NULL at beginning
    my_this->first = NULL;
}

//+-----------------------------------------------------
//| Module:      list_add
//| Description: Insert a new key, value pair in a sorted list
//| Input:       The list to insert in and the key, value to insert
//| Result:      The list is sorted according to keys and include the
//|              new key, value pair
//| Conditions:  The list is assumed to be sorted before the insert
//|              Duplicate keys are allowed. The order of duplicate
//|              keys is undefined
//+-----------------------------------------------------
void list_add(struct my_list* my_this, int key, double value)
{
    // ADD YOUR CODE HERE (approx 23 lines)

    //create new list_item node
    list_item* new_node;

    //allocate memory to it
    new_node = new list_item;

    //adding values
    new_node->key = key;
    new_node->value = value;

    if ( my_this->first != NULL)
    {
        new_node->next = my_this->first;
    }
    else
    {
        new_node->next = NULL;
    }
    my_this->first = new_node;

}

//+-----------------------------------------------------
//| Module:      list_remove
//| Description: Remove the value with key from a sorted list
//| Input:       The list to remove from and the key of the value to remove
//| Result:      The list is sorted and do not contain a value with that key
//| Conditions:  The list is assumed to be sorted before the insert
//|              If duplicates of the key to remove exist only is removed.
//|              It is undefined which of the duplicates that are removed.
//+-----------------------------------------------------
void list_remove(struct my_list* my_this, int key)
{
    // ADD YOUR CODE HERE (approx 23 lines)
    list_item *curr;

    //allokera minne
    curr = new list_item;
    curr = my_this->first;

    list_item *prev = new list_item;

    for(int i=0; i<key;i++)
    {
      prev = curr;
      curr = curr->next;

    }
    prev->next = curr->next;
    delete(curr);
}

//+-----------------------------------------------------
//| Module:      destroy
//| Description: First destroy any next list item, then release the
//|              memory of the specified list item.
//|              This will recursively destroy an list starting on this item.
//| Input:       The list item to relese memory for (delete)
//| Result:      The memory used by the list item, and any linked items,
//|              are reclaimed by the OS
//|              Further use of the list item is invalid
//| Conditions:  The item is a pointer allocated with new and not
//|              deleted before
//+-----------------------------------------------------
void destroy(struct list_item* item)
{
    // ADD YOUR CODE HERE (approx 5 lines)
    list_item *temp = new list_item;


    if(item)
    {
        temp = item;
        item = temp->next;
        delete(temp);
        destroy(item);
    }


}

//+-----------------------------------------------------
//| Module:      list_destroy
//| Description: Free the memory of an entire list.
//| Input:       The list to destroy.
//| Result:      All memory used by the list is reclaimed by the OS.
//|              The list will become a valid but empty list.
//| Conditions:  The list is initiated and valid.
//+-----------------------------------------------------
void list_destroy(struct my_list* my_this)
{
  // ADD YOUR CODE HERE (approx 2 lines)
  destroy(my_this->first);
//  delete(my_this);
}

//+-----------------------------------------------------
//| Module:      clone
//| Description: First create a new copy of the specified list
//|              then append to the new item a clone of the next.
//|              This will recursively create a copy of a entire
//|              list starting on this item.
//| Input:       The list item to clone.
//| Result:      A copy of the specified item and any linked items.
//| Conditions:  The item is valid.
//+-----------------------------------------------------
struct list_item* clone(struct list_item* item)
{
  // ADD YOUR CODE HERE (approx 10 lines)

  return item;
}

//+-----------------------------------------------------
//| Module:      list_copy
//| Description: Copy an entire list
//| Input:       The list to copy
//| Result:      A new and valid list that are an independent copy
//| Conditions:  The list is initiated and valid.
//+-----------------------------------------------------
struct my_list list_copy(struct my_list* my_this)
{
    // ADD YOUR CODE HERE (approx 3 lines)
    my_list *copy = new my_list;
    copy = my_this;
    return *copy;

}


struct my_iterator
{
   struct list_item* current; // a pointer to the "current" list element
};

//+-----------------------------------------------------
//| Module:      list_begin
//| Description:
//| Input:
//| Result:
//| Conditions:
//+-----------------------------------------------------
struct my_iterator list_begin(struct my_list* my_this)
{
  struct my_iterator i;
  i.current = my_this->first;
  return i;
}

//+-----------------------------------------------------
//| Module:      iterator_end
//| Description:
//| Input:
//| Result:
//| Conditions:
//+-----------------------------------------------------
bool iterator_end(struct my_iterator* i)
{
  return i->current == NULL;
}

//+-----------------------------------------------------
//| Module:      iterator_next
//| Description:
//| Input:
//| Result:
//| Conditions:
//+-----------------------------------------------------
void iterator_next(struct my_iterator* i)
{
  i->current = i->current->next;
}

//+-----------------------------------------------------
//| Module:      iterator_get_key
//| Description:
//| Input:
//| Result:
//| Conditions:
//+-----------------------------------------------------
int iterator_get_key(struct my_iterator* i)
{
  return i->current->key;
}

//+-----------------------------------------------------
//| Module:      iterator_get_value
//| Description:
//| Input:
//| Result:
//| Conditions:
//+-----------------------------------------------------
double iterator_get_value(struct my_iterator* i)
{
  return i->current->value;
}

//+-----------------------------------------------------
//| Module:      main
//| Description:
//| Input:
//| Result:
//| Conditions:
//+-----------------------------------------------------
int main()
{
    // ADD YOUR CODE HERE (approx 50 lines)
    my_list*list = NULL;
    list = new my_list;

    list_init(list);
    //list->first = NULL;


    int key = 0;
    double value = 0;

    int i =0;
    while(i <5)
    {
        ++i;
        cin>> value;
        value = (int) value;
        key = (int) value;

        list_add(list,key,value);
        cout << "Adding" << endl;


    }
//    my_list *list2 = new my_list;
//    list_init(list2);
//    list2 = list_copy(list);


    //destroy the list and its content
    list_destroy(list);

    list_remove(list, 3);
    cout << endl << "Print list" << endl;
    for(my_iterator i = list_begin(list); !iterator_end(&i); iterator_next(&i))
    {
        cout << iterator_get_key(&i) << " " << iterator_get_value(&i) << endl;
    }



    list_destroy(list);
    cout << endl << "Print list" << endl;
    for(my_iterator i = list_begin(list); !iterator_end(&i); iterator_next(&i))
    {
        cout << iterator_get_key(&i) << " " << iterator_get_value(&i) << endl;
    }

//    list_destroy(list2);
    return 0;
}

Answer 1

The main contents of your destroy() functions are nearly correct - the only real error is the allocation of the new list_item that is written to temp and overwritten at once if the item parameter is not NULL. Why do you think the list items are not deleted when you call delete on them? (NB: The pointers aren't set to NULL by the delete call, but the objects pointed to are deleted nonetheless.) Please clarify!

BTW, your recursive method of destroying an entire list works only for lists up to a certain length - for long lists you may get a Stack overflow error because there are too many nested calls of destroy(). Better use a loop for this.

Answer 2

The following should do the trick:

void destroy(struct list_item* item)
{
  struct list_item *temp;
  while (item)
  {
     temp = item;
     item = temp->next;
     delete(temp);
  }
}

Or if you prefer the recursive solution:

void destroy(struct list_item* item)
{
  if (item) {
    destroy(item->next);
    delete(item);
  }
}

Answer 3

After deleting all the nodes, you need to set the first pointer to NULL. Since you aren't doing this, your code is accessing freed memory after the destroy operation.

Answer 4

Ok. You should not be allocating a new list item in the destroy function. Instead I would do:

void destroy(struct list_item* item)
{
    // ADD YOUR CODE HERE (approx 5 lines)
    if(item)
    {
        list_item *temp = item;
        item = temp->next;
        delete temp;
        destroy(item);
    }

The delete operator is not a function so you can leave off the parentheses. It is also a bit unusual to do this as a recursive function. It is not wrong, but it is more normal to have the code be more like:

void destroy(struct list_item* item)
{
    // ADD YOUR CODE HERE (approx 5 lines)
    while(item)
    {
        list_item *temp = item;
        item = temp->next;
        delete temp;
    }