views:

312

answers:

3

Hello My C++ is a little rusty but I have made a program that reverses a linked list and now I am trying to write the proper destructors for it but I don't know exactly what to destroy. Here are my class definitions:

class LinkedList
{
    private:ListElement *start;
    public:LinkedList();
    public:void AddElement(int val);
    public:void PrintList();
    public:void InvertList();
};

class ListElement
{
    public:int value;
    public:ListElement * link;
    public:ListElement(int val);
    public:ListElement();
};


class Stack
{

private:ListElement ** stack;
private:int index;
public:Stack(int size);
public:void push(ListElement * le);
public:ListElement * pop();

};

The stack is for when I reverse the list. Anyway ... How would I go about writing the destructors for these? I was thinking:

For the ListElement make the value 0 and the link 0(NULL).

For the LinkedList go through the elements and call up the ListElementDestructor for all of them.

I am not very sure about this because as I understand the destructor automatically calls the destructors of the member objects so would only writing an empty destructor for LinkedList suffice in this case? I don't know ... that is why I am asking

For the stack I don't know ... the pointers are already 0(NULL) after the list is inversed because they are all poped.

I am a bit confused. Can anyone help? Thank you in advance.

+8  A: 

You destroy things that need destroying. If your class created objects using new, you probably need a destructor that deletes them using a destructor. Note that containers like LinkedList should contain only elements that have been dynamically allocated or ones that are not. If you mix the two, or mix originals and copies, as I suspect you are doing, you probably need to use smart pointers or reference counting.

Secondly, if you really need to reverse a singly-linked list (something in 30 years of programming I've never needed to do), you are simply using the wrong data structure - you should be using a doubly linked list, in which case there is no need to do anything.

And thirdly, can I say that your C++ style is non-idiomatic and to me nearly unreadable - making C++ look like Java is NOT a good idea. Change to:

class LinkedList
{
    private:
       ListElement *start;
    public:
       LinkedList();
       void AddElement(int val);
       void PrintList();
       void InvertList();
};
anon
Well ... I actually got this as a question for a job interview once: "Write the appropiate code(including class structure) to reverse a single linked list". I emphasise "single-linked list". I also did this in high-school in Pascal and in college in Java. Sorry for making C++ look like Java I really didn't mean to I guess I just got used to writing things this way.
Para
+1  A: 

For the ListElement make the value 0 and the link 0(NULL).

You don't need to reset any of the values in the destructor, as values won't exist after the destructor executed.

The main thing you need to be sure of is that all elements allocated on the heap (i.e Using new) are deleted using delete (or delete [] in the case of arrays).

For the LinkedList go through the elements and call up the ListElementDestructor for all of them.

For a object allocated on the stack it is automatically called when the object goes out of scope.
For a dynamically allocated object (i.e created using new) the destructor is called when it is deleted using delete. In other words, you don't need to call any destructors as they are called automatically if you clean up your objects correctly.

Given (I assume) that you are allocating new ListElements on the heap in the LinkedList class, you should ensure that in the LinkedList destructor, every ListElement is deleted in the destructor by walking down the list and calling delete on every ListElement (after you have retrieved the address of the next list element from it of course). Something like this:

ListElement* current = list.start;    
while( current ){
    ListElement* next = current->next;
    delete current;
    current = next;
}

There is nothing in the ListElement class that needs cleaning up, as although it has a pointer to the next element the deletion should probably be handled in the LinkedList class, which means it doesn't need a destructor.
It isn't required that you write a destructor for every class, as the compiler will automatically generate an empty one for you.

As I said in the comments, you shouldn't be using a stack for reversing a linked list. You should just be swapping the direction of the pointers.
An quick example of roughly the sort of thing you would want.

ListElement* previous = 0;
ListElement* current = list.start;

while( current->next ){
    //copy the address of current item on the list
    ListElement* next = current->next;

    //point the current list item to the previous list item
    current->next = previous;

    //set the current list item to the next list item
    current = next;

    //and the previous list item to the current one
    previous = current;
}
//set the start of the list to what was the end
list.start = current;
Yacoby
This is the way I learnt to do it in high-school with a stack. If you could show me how to reverse the pointers I would be much obliged. I had no idea this could be done any other way. This is just the first thing the popped into my head. I am opened to any other solution. I would appreciate one in fact.
Para
@Para I have edited into my post some rough (and untested) code for reversing a linked list by swapping the pointers. Even if it doesn't work 100% correctly it should give you an idea of how to go about it.
Yacoby
+1  A: 

The LinkedList class creates ListElements. So you need to loop from start to the end of the list (unless it is empty.) and :

delete currentElement;

In the LinkedList destructor. Since the ListElement stores value as an 'int', you don't really need to free up memory here. Just as you thought.

Again, no need to free memory in the Stack class' destructor. In general, delete whatever you new! And let one person(class) be responsible for the job!

batbrat