C++ Linked list copy and clone function

Question

Hi,this is also a continuation from my linked list questions

I did not get the answer regarding delete. When delete is called is the actual value deleted or is it just the pointer to it?

For my question this time is about the clone() and list_copy() functions. What I want to do with those function is to;

1. first call the list _copy() to copy one struct into a new struct.

2. list _copy() calls clone() which will recursively clone all nodes

The issue I have with the function now is that it will copy. However I only get a new struct which points to the same values instead for an independent new struct. I wonder what the problem is?

#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)
    if(item)
    {
        list_item *temp = item;
        item = temp->next;
        cout << "Destroy item" << endl;
        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);
  cout << "Destroy list" << endl;
  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)

    list_item *new_node = new list_item;

    if(item != NULL)
    {
        new_node->key = item->key;
        new_node->value = item->value;
        new_node->next = item->next;

        cout <<"Clone "<< item->key << ". " << item->value << endl;
        clone(item->next);
    }
    else
    {
        new_node->next = NULL;
        cout << "END" << endl;
    }

    return new_node;
}

//+-----------------------------------------------------
//| 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)

    //copy of the list which will be returned
    my_list *foo = new my_list;


    list_item *temp = new list_item;
    list_item *temp2 = new list_item;


    temp = my_this->first; //head

    temp2 = clone(temp);

    foo->first = temp2;

    //this is to check whether clone() worked
    while(temp2)
    {
        cout << "Did it work? " << temp2->value << endl;
        temp2=temp2->next;
    }

    return *foo;

}


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);




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



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


    cout << endl << endl;


    list_destroy(list);

    cout << endl << "Print list1" << 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

Say you have small slips of paper. Your friend is writing letters on them to spell creative messages. When he asks you for some number of slips, that's like calling the new operator. When he's done and gives them back to you, that's delete. Nothing has been destroyed: it's a question of ownership.

After he gives them back, your friend may still be able to identify a particular slip he was using. This is like having pointer to that slip, but you may give it to someone else. There's no guarantee that the letter he wrote on it will stay there after he gives it back to you.

Answer 2

You have a lot of code here. Hard to see every thing

new_node->next = item->next;

next is a pointer. So what you do here, is you copy the value of the pointer (the adress in to the memory), but not the value. Therefor, both structures (the orginal and the clone) point to the same place.

Key and value aren't pointers, so their value will be copied and it actually clones the data.

Note that when calling clone inside of your clone function, there is no pointer to the memory allocation. So you won't be able to call delete on it, and you will have a memory leak.

EDIT This might be a solution:

list_item* clone(list_item* item)
{
    list_item *new_node = new list_item;

    if(item != NULL)
    {
        new_node->key = item->key;
        new_node->value = item->value;
        //NOTE: this is probably what you want
        new_node->next = clone(item->next);
        cout <<"Clone "<< item->key << ". " << item->value << endl;
    }

    // NOTE: the clone of NULL should be NULL, not a new list item !
    return new_node;
}

However, as it is for educational purpose (otherwise you would use std::list), try to make an effort to develop in C, not in C++. Every time you add a new function or member, run valgrind to be sure there is no problem. Only then go over implementing a new function.

Answer 3

I will answer this questions from a purely C++/object oriented point of view (the question is tagged as C++), even if your code is much closer to C and maybe you are expecting a C solution. It seems from the comments that this is some kind of exercise that you are trying to implement, and the comments seem to be for a C course.

I did not get the answer regarding delete. When delete is called is the actual value deleted or is it just the pointer to it?

When you delete a pointer the destructor (for class types) of the instance pointed is called and then the memory is deallocated. For any class (structs are also classes) for which you did not provide a destructor the compiler will generate one for you.

The implicitly generated destructor will call each subobject's destructors (if present), but it won't delete anything (that is, no memory will be deallocated).

If your classes need to manage resources (including memory) you should use RAII techniques for that. The two simplest ways of doing so are implementing your own destructor, or else storing resources in RAII objects (usually smart pointers).

In C, there is no such thing as the destructor, nor RAII... but the same fact holds true: it will not free the rest of the list for you, you have to manually work the deletion of the rest of the elements in the list.

The issue I have with the function now is that it will copy. However I only get a new struct which points to the same values instead for an independent new struct. I wonder what the problem is?

The simplest answer is that you should provide a copy constructor that copies the tail of the list.