double linked list help

[b][red]This message was edited by kkhan at 2003-8-31 19:31:38[/red][/b][hr]
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.

edit:-

i made some more changes and it goes to the second line(thank god) but then it outputs this
6 1 5 7

instead of 6 7 1 5 7 . Any other helpful ideas folks, the modifed methods are now reflected in the code.



The .h file
[code]
#ifndef _H_dList
#define _H_dList
#include

template
struct nodeType
{
Type info;
nodeType *next;
nodeType * previous;
};

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

dList(const dList& otherList);

~dList();

const dList& operator=(const dList& 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& otherList);
};




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

//destructor
template
dList::~dList()
{
nodeType* temp;

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

//copy constructor
template
dList::dList(const dList& otherList)
{
copyList(otherList);
}

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


nodeType* 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
Type dList::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
Type dList::back()const
{
assert(first != NULL);
return last->info;
}


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

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

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

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

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

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

while(old_temp != NULL)
{
new_temp->next= new nodeType;
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
void dList::sort()
{
for(nodeType* temp=first;temp != NULL; temp=temp->next)
{
nodeType* min = temp;

for(nodeType* 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
void dList::push_back(const Type& e)
{
nodeType* temp = new nodeType;
temp->info=e;
temp->previous=NULL;
temp->next=NULL;

if(first==NULL && last==NULL)
{
first=last=temp;
count++;
}

else
{
temp->previous=last;
last->next=temp;
last=temp;
count++;
}


}


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

if(first==NULL && last==NULL)
{
first=last=temp;
count++;
}

else
{
temp->next=first;
first->previous=temp;
first=temp;
count++;
}

//deletes the back node from the list
//does nothing if list is empty
template
void dList::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
void dList::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
void dList::erase(nodeType* 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
void dList::remove(const Type& e)
{
nodeType* temp = new nodeType;

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
void dList::insert(nodeType* p, const Type& e)
{
assert( p != NULL);

nodeType* temp = new nodeType;
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
[/code]

tester file
[code]
#include
using namespace std;
#include "dList.h"

int main()
{
dList 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 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);
}
[/code]
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories