Problem with script!

it compiles and runs, but in one moment it gives me an unhandled exception. I tracked the problem till i found it. it is the line in bold in my code. Whats wrong with it?

"LinkedList.h"

Code:

---

#include <iostream>

using namespace std;

template<typename T>
struct LinkedNode
{
        T data;
        LinkedNode* next;
        LinkedNode* prev;
};

template<typename T>
class LinkedList
{
public:
LinkedList();
~LinkedList();
LinkedList(const LinkedList& rhs);
LinkedList& operator=(const LinkedList& rhs);
bool isEmpty();
LinkedNode<T>* getFirst();
LinkedNode<T>* getLast();
void insertFirst(T data);
void insertLast(T data);
bool insertAfter(T tKey, T tData);
void removeFirst();
void removeLast();
bool remove(T removalCandidate);
void destroy();
private:
LinkedNode<T>* mFirst;
LinkedNode<T>* mLast;
};
template<typename T>
LinkedList<T>::LinkedList()
: mFirst(), mLast()
{
}
template<typename T>
LinkedList<T>::~LinkedList()
{
        destroy();
}
template<typename T>
LinkedList<T>::LinkedList(const LinkedList &rhs)
{
        destroy();
        *this = rhs;
}
template<typename T>
LinkedList<T>& LinkedList<T>::operator =(const LinkedList<T> &rhs)
{
        if(this = &rhs)
                return *this;
        destroy();
        mFirst = rhs.mFirst;
        mLast = rhs.mLast;
        return this*;
}
template<typename T>
bool LinkedList<T>::isEmpty()
{
        if(mFirst == 0)
                return true;
        else
                return false;
}
template<typename T>
LinkedNode<T>* LinkedList<T>::getFirst()
{
        return mFirst;
}
template<typename T>
LinkedNode<T>* LinkedList<T>::getLast()
{
        return mLast;
}
template<typename T>
void LinkedList<T>::insertFirst(T tData)
{
LinkedNode<T>* newNode = new LinkedNode<T>();
newNode->data = tData;

if(isEmpty())
mLast = newNode;

else
mFirst->prev = newNode;

newNode->next = mFirst;

mFirst = newNode;
}
template<typename T>
void LinkedList<T>::insertLast(T tData)
{
        LinkedNode<T>* newNode = new LinkedNode<T>();
        newNode->data = tData;

        if(isEmpty())
                mFirst = newNode;
        else
                mLast->next = newNode;
        newNode ->prev = mLast;
        newNode ->next = 0;
        mLast = newNode;
}
template<typename T>
bool LinkedList<T>::insertAfter(T tKey, T tData)
{
if(isEmpty())
return false;

LinkedNode<T>* current = mFirst;

while(current->data != tKey)
{

current = current->next;

if(current == 0)
return false;
}

LinkedNode<T>* newNode = new LinkedNode<T>();
newNode->data = tData;

if(current == mLast)
{
newNode->next = 0;
mLast = newNode;
}

else
{
newNode->next = current->next;
current->next->prev = newNode;
}
newNode->prev = current;
current->next = newNode;
return true;
}
template<typename T>
void LinkedList<T>::removeFirst()
{
        LinkedNode<T>* oldNode = mFirst;
        mFirst = mFirst->next;
        delete oldNode;
        oldNode = 0;

}
template<typename T>
void LinkedList<T>::removeLast()
{
        LinkedNode<T>* oldNode = mLast;
        delete oldNode;
        mLast = mLast->prev;
}
template<typename T>
bool LinkedList<T>::remove(T removalCandidate)
{
        if(isEmpty())
                return false;
LinkedNode<T>* current = mFirst;
while(current->data != removalCandidate)
{

current = current->next;

if(current == 0)
return false;
}
if(current == mLast)
{
current->prev->next = 0;
mLast = current->prev;
}
else
{
current->prev->next = current->next;
current->next->prev = current->prev;
}
delete current;
current = 0;

return true;
}
template<typename T>
void LinkedList<T>::destroy()
{

if(mFirst != 0)
{

LinkedNode<T>* current = mFirst;

while(current != 0)
{

LinkedNode<T>* oldNode = current;

current = current->next;

delete oldNode;
oldNode = 0;
}
}
}

---

"Main.cpp"

Code:

---

#include "LinkedList.h"
#include <iostream>
#include <string>
using namespace std;
int main()
{
LinkedList<int> myIntList;
// Insert to the front of the list.
myIntList.insertFirst(4);
myIntList.insertFirst(3);
myIntList.insertFirst(2);
myIntList.insertFirst(1);
// Insert to the back of the list.
myIntList.insertLast(5);
myIntList.insertLast(7);
myIntList.insertLast(8);
myIntList.insertLast(9);
// Forgot to add 6 to the list, insert before 7. But first
// we must get an iterator that refers to the position
// we want to insert 6.
cout << "Before deletion..." << endl;
myIntList.insertAfter(5, 6);
// Print the list to the console window.
for(LinkedNode<int>* i = myIntList.getFirst(); i != myIntList.getLast()->next; i = i->next)
cout << i->data << " ";
cout << endl;
// Remove the first node in the list.
myIntList.removeFirst();
// Remove the last node in the list.
myIntList.removeLast();
// Remove the node that has a value of 5
myIntList.remove( 1 );
// Print the list to the console window.
cout << "After deletion..." << endl;
for(LinkedNode<int>* i = myIntList.getFirst(); i != myIntList.getLast()->next; i = i->next)
cout << i->data << " ";
cout << endl;
system("PAUSE");
}

---

This code is supposed to simulate the std::list class.

Just looking at that function with the bolded line you can see the problem. Try drawing the memory and pointers out on a piece of paper. When the data gets deleted cross out the picture of that spot in memory. Do you see what happens?

This is a bit off-topic, but I cringe a little when I see the word "script". This is C++ source code, or informally, just "code".

I don't actually know the technical definition of script, but it's usually used for simpler interpreted languages, or something like a sequence of instructions in an automated batch file.

From Wikipedia:

Quote:

---

A scripting language, script language or extension language, is a programming language that allows some control of a single or many software application(s). "Scripts" are often treated as distinct from "programs", which execute independently from any other application.

---

daved, any possible solution?
thank you !

You'd get more interest if you learnt to indent the code properly.
It's a mess.

You can't use the next pointer of a node that you've already deleted. The purpose of the temporary pointer oldNode is to hang onto that node while you're replacing it in the list. Delete it after you are finished using it.

Also, I don't see any reason to assign 0 to oldNode since it will cease to exist at the end of removeFirst() anyway.

well i fixed that like this:

Code:

---

        LinkedNode<T>* oldNode = mFirst;
        mFirst = mFirst->next;
        delete oldNode;
        oldNode = 0;

---

but now im having some problems in other place.(its the one in bold now). ive been testing what could be wrong and i saw that ouside the loop while "current" worked fine, but inside, al int variable values were changed...i dont know why.

Please don't edit original posts to different content as it makes it impossible to understand the following replies. Instead post the new code (and preferably properly indented, so it can actually be read.

However it seems that you are not updating the object properly when you remove the first node - btw by the time you try to erase 1, 1 isn't in the list anymore.

Perhaps you might also try to take advantage of already having a removeFirst and removeLast functions:

Code:

---

def erase (value):
    do the search
    if found:
        if found == first:
            eraseFirst()
        else if found == last:
            eraseLast()
        else:
            do middle erasure
        return true
    return false

---

Thank you anon! i dont know how, but you always know how to solve my problems. This is how i fixed the problem:

Code:

---

template<typename T>
void LinkedList<T>::removeFirst()
{
        LinkedNode<T>* oldNode = mFirst;
        mFirst = mFirst->next;
        mFirst->prev = 0;
        delete oldNode;
        oldNode = 0;
}
template<typename T>
void LinkedList<T>::removeLast()
{
        LinkedNode<T>* oldNode = mLast;
        mLast = mLast->prev;
        mLast->next = 0;
        delete oldNode;

}
template<typename T>
bool LinkedList<T>::remove(T removalCandidate)
{
        if(isEmpty())
                return false;
LinkedNode<T>* current = mFirst;

while(current->data != removalCandidate)
{
current = current->next;

if(current == 0)
return false;
}
if(current == mLast)
{
removeLast();
}
else if (current == mFirst)
{
removeFirst();
}
else
{
current->prev->next = current->next;
current->next->prev = current->prev;
}
delete current;
current = 0;

return true;
}

---

oh and how can i do my code to be more readable so you can understand it better?

Quote:

---

Originally Posted by Cherry65

oh and how can i do my code to be more readable so you can understand it better?

---

One of the first steps would be to indent it more consistently and use blank lines as logical separators, e.g.,

Code:

---

template<typename T>
void LinkedList<T>::removeFirst()
{
    LinkedNode<T>* oldNode = mFirst;
    mFirst = mFirst->next;
    mFirst->prev = 0;
    delete oldNode;
    oldNode = 0;
}

template<typename T>
void LinkedList<T>::removeLast()
{
    LinkedNode<T>* oldNode = mLast;
    mLast = mLast->prev;
    mLast->next = 0;
    delete oldNode;
}

template<typename T>
bool LinkedList<T>::remove(T removalCandidate)
{
    if (isEmpty())
        return false;

    LinkedNode<T>* current = mFirst;

    while (current->data != removalCandidate)
    {
        current = current->next;

        if (current == 0)
            return false;
    }

    if (current == mLast)
    {
        removeLast();
    }
    else if (current == mFirst)
    {
        removeFirst();
    }
    else
    {
        current->prev->next = current->next;
        current->next->prev = current->prev;
    }

    delete current;
    current = 0;

    return true;
}

---

When run through a source code formatter (some IDEs have it), the function looks like this:

Code:

---

template<typename T>
bool LinkedList<T>::remove(T removalCandidate)
{
    if (isEmpty())
        return false;
    LinkedNode<T>* current = mFirst;

    while (current->data != removalCandidate) {
        current = current->next;

        if (current == 0)
            return false;
    }
    if (current == mLast) {
        removeLast();
    } else if (current == mFirst) {
        removeFirst();
    } else {
        current->prev->next = current->next;
        current->next->prev = current->prev;
    }
    delete current; //this, BTW, might already be deleted by RemoveFirst or RemoveLast
    current = 0; //current is a local variable and goes out of scope, this has no purpose here

    return true;
}

---

It shouldn't be hard to adopt a style and keep to it manually either.