double linked list help

[kashif]

Im having some trouble with this doubly linked list that i made. For some reasons it has an assertion when the list isnt empty after the first output of 3 & 2.
can someone pls help me out with this or something major in this
program. I am also attaching the files as a zip file.

The .h file

#ifndef _H_dList
#define _H_dList
#include<cassert>

template<class Type>
struct nodeType
{
Type info;
nodeType<Type> *next;
nodeType<Type> * previous;
};

template<class Type>
class dList
{
public:
typedef nodeType<Type> *Ptr;
public:
dList();

dList(const dList<Type>& otherList);

~dList();

const dList<Type>& operator=(const dList<Type>& otherList);
void push_front(const Type& e);
void push_back(const Type& e);
void insert(Ptr p, const Type& e);
void pop_front();
void pop_back();
void erase(Ptr p);
void remove(const Type& e);
Type front() const;
Type back() const;

Ptr begin() const
{
if(!empty())return first;

return NULL;
}

Ptr rbegin() const
{

if(!empty())return last;

return NULL;
}

bool empty() const;
int size() const;
void sort();

protected:
int count;
Ptr first;
Ptr last;
private:
void copyList(const dList<Type>& otherList);
};




// default constructor
template<class Type>
dList<Type>::dList():first(NULL),last(NULL),count(0)
{
}

//destructor
template<class Type>
dList<Type>::~dList()
{
nodeType<Type>* temp;

while(first!=NULL)
{
temp=first;
first=first->next;
delete temp;
}
last=NULL;
count=0;
}

//copy constructor
template<class Type>
dList<Type>::dList(const dList<Type>& otherList)
{
copyList(otherList);
}

//overloaded operator =
template<class Type>
const dList<Type>& dList<Type>::operator=(const dList<Type>& otherList)
{
if(this != &otherList)
{


nodeType<Type>* temp;

while(first!=NULL)
{
temp=first;
first=first->next;
delete temp;
}

last=NULL;
count=0;
copyList(otherList);
}
return *this;
}


//returns info in the front (first) node in the list
//asserts first!= NULL so that if list is empty, program is terminated.
template<class Type>
Type dList<Type>::front()const
{
assert(first != NULL);

return first->info;
}

//returns info in the back (last) node in the list
//asserts first!= NULL so that if list is empty, program is terminated.
template<class Type>
Type dList<Type>::back()const
{
assert(first != NULL);
return last->info;
}


//returns true if list is empty, false otherwise
template<class Type>
bool dList<Type>::empty()const
{
return (first == NULL);
}

//returns current size
template<class Type>
int dList<Type>::size()const
{
return count;
}

//performs a deep copy
template<class Type>
void dList<Type>::copyList(const dList<Type>& otherList)
{
count=otherList.count;

if(count==0)first=last=NULL;

else
{
first = new nodeType<Type>;
first->info=otherList.first->info;

nodeType<Type>* new_temp = first;
nodeType<Type>* old_temp = otherList.first->next;

while(old_temp != NULL)
{
new_temp->next= new nodeType<Type>;
new_temp->next->info=old_temp->info;
new_temp->next->previous = new_temp;
new_temp=new_temp->next;
old_temp=old_temp->next;
}
last=new_temp;
}
}

//sorts list in ascending order
template<class Type>
void dList<Type>::sort()
{
for(nodeType<Type>* temp=first;temp != NULL; temp=temp->next)
{
nodeType<Type>* min = temp;

for(nodeType<Type>* current = min; curr != NULL; current=current->next)
{
if(current->info < min->data)min=current;
}

Type temp_var=temp->data;
temp->data=min->data;
min->data=temp_var;
}
}

//inserts node with info e at the back of the list
template<class Type>
void dList<Type>::push_back(const Type& e)
{
nodeType<Type>* temp = new nodeType<Type>;
temp->info=e;

if(count>0)last->next=temp;
else first=temp;

temp->previous=last;
last=temp;

count++;
}


//inserts node with info e at the front of the list
template<class Type>
void dList<Type>::push_front(const Type& e)
{
nodeType<Type>* temp= new nodeType<Type>;
temp->info=e;

if(count>0)first->previous=temp;
else first=temp;

temp->next=first;
first=temp;
}


//deletes the back node from the list
//does nothing if list is empty
template<class Type>
void dList<Type>::pop_back()
{
if(!empty())
{


if(last==first)
{
delete first;
first=last=NULL;
}

else
{
last=last->previous;
delete last->next;
last->next=NULL;
}
count--;
}
}

//deletes the front node from the list
//does nothing if list is emoty
template<class Type>
void dList<Type>::pop_front()
{
if(!empty())
{


if(first==last)
{
delete first;
last=last=NULL;
}

else
{
first=first->next;
delete first->previous;
first->previous=NULL;
}
count--;

}
}

//deletes the node pointed to by p in the list
//asserts p!=NULL
template<class Type>
void dList<Type>::erase(nodeType<Type>* p)
{
assert(p != NULL);

if(p==first)pop_front();
if(p==last)pop_back();

else
{
p->previous->next=p->next;
p->next->previous=p->previous;
delete p;
}
count--;
}

//deletes all occurences of e in the list
template<class Type>
void dList<Type>::remove(const Type& e)
{
nodeType<Type>* temp = new nodeType<Type>;

temp=first;

while(temp != NULL)
{
if(temp->info==e)
{
erase(temp);
count--;
}
temp=temp->next;
}
}

//inserts noce with e immediately before node pointed by p
//asserts p!= NULL
template<class Type>
void dList<Type>::insert(nodeType<Type>* p, const Type& e)
{
assert( p != NULL);

nodeType<Type>* temp = new nodeType<Type>;
temp->info=e;
temp->next=NULL;
temp->previous=NULL;


if(p==first && p==last)
{
first=last=temp;
}

if(p==first)push_front(e);
if(p==last)push_back(e);

else
{
temp->previous=p->previous;
p->previous->next=temp;
temp->next=p;
}
count++;
}
#endif


tester file

#include <iostream>
using namespace std;
#include "dList.h"

int main()
{
dList<int> dl;

int k = 1;
dl.push_front(k);
k++;
dl.push_back(k);
k++;
dl.push_front(k);
k++;
//dl now contains the values 3 1 2

cout<<dl.front()<<" "<<dl.back()<<endl; //outputs 3 2

dl.pop_front();

dl.pop_back();
//dl now contains 1

cout<<dl.front()<<" "<<dl.back()<<endl; //outputs 1 1

dl.push_front(k);
k++;
dl.push_back(k);
k++;
dl.push_front(k);
k++;
//dl now contains 6 4 1 5

dList<int>::Ptr p;

p = dl.begin();
p = p->next; //p points to 4
dl.insert(p, k);
dl.erase(p); //dl now contains 6 7 1 5
dl.push_back(k); //dl now contains 6 7 1 5 7
for (p = dl.begin(); p != NULL; p = p->next) //outputs 6 7 1 5 7
cout<<p->info<<" ";
cout<<endl;

dl.remove(k); //dl now contains 6 1 5

dList<int> dl2(dl); //copy constructor - dl2 now is a copy of dl

dl2.pop_back(); //dl still contains 6 1 5 and dl2 contains 6 1

dList<int> dl3;

dl3 = dl2; //dl3 is now a copy of dl2

dl3.pop_front(); //dl2 still contains 6 1 and dl3 contains 1

for (p = dl.begin(); p != NULL; p = p->next) //outputs 6 1 5
cout<<p->info<<" ";
cout<<endl;

for (p = dl2.begin(); p != NULL; p = p->next) //outputs 6 1
cout<<p->info<<" ";
cout<<endl;

for (p = dl3.begin(); p != NULL; p = p->next) //outputs 1
cout<<p->info<<" ";
cout<<endl;

for (p = dl.rbegin(); p != NULL; p = p->previous) //outputs 5 1 6
cout<<p->info<<" ";
cout<<endl;

dl3.pop_back(); //dl3 is now empty

cout<<dl.size()<<" "<<dl2.size()<<" "<<dl3.size()<<endl;
//outputs 3 2 0

if (!dl.empty()) cout<<"dl is not empty"<<endl;
if (dl3.empty()) cout<<"dl3 is empty"<<endl;

cout<<"Press the enter key to finish"<<endl;
char ch;
cin.get(ch); //pause at end
return(0);
}

[Flangazor]

push_front doesn't increment the count. Also, when count>0 fails in the pushes, you should also be setting last to the same value as first.

On my local copy, I changed the else to first=last=temp; to keep it in line with your style. There are more errors I am debugging for you.

Edit:

#ifndef _H_dList
#define _H_dList
#include<cassert>

template<class Type>
struct nodeType
{
Type info;
nodeType<Type> *next;
nodeType<Type> * previous;
nodeType(): next(NULL), previous(NULL){}
};

template<class Type>
class dList
{
public:
typedef nodeType<Type> *Ptr;
public:
dList();

dList(const dList<Type>& otherList);

~dList();

const dList<Type>& operator=(const dList<Type>& otherList);
void push_front(const Type& e);
void push_back(const Type& e);
void insert(Ptr p, const Type& e);
void pop_front();
void pop_back();
void erase(Ptr p);
void remove(const Type& e);
Type front() const;
Type back() const;

Ptr begin() const
{
if(!empty())return first;

return NULL;
}

Ptr rbegin() const
{

if(!empty())return last;

return NULL;
}

bool empty() const;
int size() const;
void sort();

protected:
int count;
Ptr first;
Ptr last;
private:
void copyList(const dList<Type>& otherList);
};




// default constructor
template<class Type>
dList<Type>::dList():first(NULL),last(NULL),count(0)
{
}

//destructor
template<class Type>
dList<Type>::~dList()
{
nodeType<Type>* temp;

while(first!=NULL)
{
temp=first;
first=first->next;
delete temp;
}
last=NULL;
count=0;
}

//copy constructor
template<class Type>
dList<Type>::dList(const dList<Type>& otherList)
{
copyList(otherList);
}

//overloaded operator =
template<class Type>
const dList<Type>& dList<Type>::operator=(const dList<Type>& otherList)
{
if(this != &otherList)
{


nodeType<Type>* temp;

while(first!=NULL)
{
temp=first;
first=first->next;
delete temp;
}

last=NULL;
count=0;
copyList(otherList);
}
return *this;
}


//returns info in the front (first) node in the list
//asserts first!= NULL so that if list is empty, program is terminated.
template<class Type>
Type dList<Type>::front()const
{
assert(first != NULL);

return first->info;
}

//returns info in the back (last) node in the list
//asserts first!= NULL so that if list is empty, program is terminated.
template<class Type>
Type dList<Type>::back()const
{
assert(first != NULL);
return last->info;
}


//returns true if list is empty, false otherwise
template<class Type>
bool dList<Type>::empty()const
{
return (first == NULL);
}

//returns current size
template<class Type>
int dList<Type>::size()const
{
return count;
}

//performs a deep copy
template<class Type>
void dList<Type>::copyList(const dList<Type>& otherList)
{
count=otherList.count;

if(count==0)first=last=NULL;

else
{
first = new nodeType<Type>;
first->info=otherList.first->info;

nodeType<Type>* new_temp = first;
nodeType<Type>* old_temp = otherList.first->next;

while(old_temp != NULL)
{
new_temp->next= new nodeType<Type>;
new_temp->next->info=old_temp->info;
new_temp->next->previous = new_temp;
new_temp=new_temp->next;
old_temp=old_temp->next;
}
last=new_temp;
}
}

//sorts list in ascending order
template<class Type>
void dList<Type>::sort()
{
for(nodeType<Type>* temp=first;temp != NULL; temp=temp->next)
{
nodeType<Type>* min = temp;

for(nodeType<Type>* current = min; curr != NULL; current=current->next)
{
if(current->info < min->data)min=current;
}

Type temp_var=temp->data;
temp->data=min->data;
min->data=temp_var;
}
}

//inserts node with info e at the back of the list
template<class Type>
void dList<Type>::push_back(const Type& e)
{
nodeType<Type>* temp = new nodeType<Type>;
temp->info=e;

if(count>0)last->next=temp;
else
{
first=last=temp;
}

temp->previous=last;
temp->next=NULL;
last=temp;

count++;
}


//inserts node with info e at the front of the list
template<class Type>
void dList<Type>::push_front(const Type& e)
{
nodeType<Type>* temp= new nodeType<Type>;
temp->info=e;

if(count>0)first->previous=temp;
else
{
first=last=temp;
}

temp->next=first;
temp->previous=NULL;
first=temp;

count++;
}


//deletes the back node from the list
//does nothing if list is empty
template<class Type>
void dList<Type>::pop_back()
{
if(!empty())
{


if(last==first)
{
delete first;
first=last=NULL;
}

else
{
last=last->previous;
delete last->next;
last->next=NULL;
}
count--;
}
}

//deletes the front node from the list
//does nothing if list is emoty
template<class Type>
void dList<Type>::pop_front()
{
if(!empty())
{


if(first==last)
{
delete first;
last=last=NULL;
}

else
{
first=first->next;
delete first->previous;
first->previous=NULL;
}
count--;

}
}

//deletes the node pointed to by p in the list
//asserts p!=NULL
template<class Type>
void dList<Type>::erase(nodeType<Type>* p)
{
assert(p != NULL);

if(p==first)
{
pop_front();
p=first; // first has moved, so reassign p
}
if(p==last)
{
pop_back();
p=last; // last has moved so reassign p
}

else
{
p->previous->next=p->next;
p->next->previous=p->previous;
delete p;
count--;
}

}

//deletes all occurences of e in the list
template<class Type>
void dList<Type>::remove(const Type& e)
{
nodeType<Type>* temp;

temp=first;

while(temp != NULL)
{
if(temp->info==e)
{
if(temp==last)
{
erase(temp);
return;
}
else
{
temp=temp->next;
erase(temp->previous);
}
}
temp=temp->next;
}
}

//inserts noce with e immediately before node pointed by p
//asserts p!= NULL
template<class Type>
void dList<Type>::insert(nodeType<Type>* p, const Type& e)
{
assert( p != NULL);

nodeType<Type>* temp = new nodeType<Type>;
temp->info=e;
temp->next=NULL;
temp->previous=NULL;


if(p==first && p==last)
{
first=last=temp;
}

if(p==first)push_front(e);
if(p==last)push_back(e);

else
{
temp->previous=p->previous;
p->previous->next=temp;
temp->next=p;
}
count++;
}
#endif

Since the code works on the basis of pointers being NULL, there were several instances where you didn't initialise or uninitialise pointers to NULL. diff the file to see where.

gl hf