Thread: doubly linked list error.

  1. #1
    Registered User
    Join Date
    Mar 2003
    Posts
    134

    doubly linked list error.

    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
    Code:
    #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;
    	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<class Type>
    void dList<Type>::push_front(const Type& e)
    {
    	nodeType<Type>* temp= new nodeType<Type>;
    	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<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
    Code:
    #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);
    }
    Last edited by noob2c; 08-31-2003 at 07:47 PM.

  2. #2
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    I don't know about your problem, I don't have time to go through the code.

    But I do know that you shouldn't be writing all that code in the header. Headers are only for declarations, you should create another .cpp file and define all the functions there.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  3. #3
    Registered User
    Join Date
    Mar 2003
    Posts
    134
    yeah , but it uses templates and thus the definitions have to be written in the header file

  4. #4
    *******argv[] - hu? darksaidin's Avatar
    Join Date
    Jul 2003
    Posts
    314
    Thats a lot of code. I just had a quick glance and saw that you delete pointers without setting them to NULL afterwards. I know this is not neccessary if the pointers are local variables or you don't use them again etc, but I always felt like setting pointers to NULL after using them safed me from a lot of trouble.
    Maybe you should give it a try and see if your problem still exists. If not, you're deleting a pointer twice somewhere. This may or may not be a problem, depending on what other code is called multiple times.
    If not - well I'm just a C++ newbie...
    [code]

    your code here....

    [/code]

  5. #5
    Registered User
    Join Date
    Mar 2003
    Posts
    134
    yeah i realized abt the fact of a lot of code, so thats why i posted it in zip file.

    am a n00b here as well

  6. #6
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,090
    I'd start by looking at your push_front method. You are pushing something, but you don't increment the count like you do in the push_back method. Also, look at what you are setting the next and previous pointers to in those methods. For example, you should probably set the temp->next = first; before you manipulate the other pointers. If you have a debugger that allows you to see what each value is after each push_front or push_back, you can see whether those methods are doing what you want.

    That's just a start to get you past the first few errors. Hope it helps.

  7. #7
    Registered User
    Join Date
    Mar 2003
    Posts
    134
    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.
    Last edited by noob2c; 08-31-2003 at 07:46 PM.

  8. #8
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    yeah , but it uses templates and thus the definitions have to be written in the header file
    I'm beginning to see why people dislike Herb Shildt so much. I didn't know that. Add to that the fact I spent about an hour looking for a book errata page and couldn't find it (maybe there were too many to list them all? ). Thank goodness I'm getting stroustrup's book next week.

    So why can't templated functions span multiple files?

    Sorry noob2c not trying to OT your post.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  9. #9
    *******argv[] - hu? darksaidin's Avatar
    Join Date
    Jul 2003
    Posts
    314
    Originally posted by HybridM
    I'm beginning to see why people dislike Herb Shildt so much. I didn't know that. Add to that the fact I spent about an hour looking for a book errata page and couldn't find it (maybe there were too many to list them all? ). Thank goodness I'm getting stroustrup's book next week.

    So why can't templated functions span multiple files?

    Sorry noob2c not trying to OT your post.
    I assume it is because templates are made real classes at compiletime or shorty before. I think it's done by some kind of preprocessor that replaces all occurances of the "variable type" with the type you selected for your instance of the template class. Therefore, you cannnot compile templates which explains why it doesn't make sense to put them in a cpp. If you compiled them, it wouldn't be templates anymore because the "variable type" would have to be replaced with a specific type (or you have to come up with some kind of intermediate code that supports variable types but that would just reduce compiletime because in the end it would have to be converted to a normal class anyway).
    But thats just an assumption - I haven't done anything with templates yet.
    Last edited by darksaidin; 09-01-2003 at 04:36 AM.
    [code]

    your code here....

    [/code]

  10. #10
    Registered User
    Join Date
    Mar 2003
    Posts
    134
    yup, the dark hit it on the spot, since it is a general type of "template" it looks for Type in the code and replaces it with say example "int".

    PPl any more ideas for the code????

    edit:-

    I think im having trouble with these two peice of code, any ideas ppl?:-

    Code:
    //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++;
    }
    Last edited by noob2c; 09-01-2003 at 10:03 AM.

  11. #11
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    Makes sense. Thanks.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  12. #12
    Registered User dalek's Avatar
    Join Date
    May 2003
    Posts
    135
    So why can't templated functions span multiple files?
    They can if your compiler supports the C++ keyword "export". However I have noticed that Visual C++ as of the latest version does not yet support this keyword. The export keyword tells the compiler that you are providing a seperately compiled template. However I am not sure of the exact syntax as I have never owned a compiler that supports it!
    I assume it is because templates are made real classes at compiletime or shorty before.
    I believe that is correct.
    Last edited by dalek; 09-01-2003 at 06:35 PM.

  13. #13
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,090
    Code:
        nodeType<Type>* temp = new nodeType<Type>;
        temp=first;
    First: In that code you allocate memory for a new node, then immediately set the pointer to something else. If you don't need a new node, don't create one. This won't cause an "error", but it causes a memory leak so you should fix it.

    Code:
            erase(temp);
            count--;
        ...
        temp=temp->next;
    Second: Unless you changed your erase method from above, you decrement the count both here and in erase. From your original code there are several places you are doing this. Figure out where the count needs to be incremented and decremented and make sure it only happens once per addition/deletion. Again, if you are going to keep a count, use the debugger to make sure the count is always correct as you step through the code.

    Third: In your original erase, you delete the passed in pointer. Then in remove above, you use the temp pointer that you just passed to erase, even though the data that was pointed to was deleted. That will probably cause a crash.

    Try fixing those things if you haven't already, especially the third one. Good luck.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  2. Errors including <windows.h>
    By jw232 in forum Windows Programming
    Replies: 4
    Last Post: 07-29-2008, 01:29 PM
  3. Avoiding Global variables
    By csonx_p in forum Windows Programming
    Replies: 32
    Last Post: 05-19-2008, 12:17 AM
  4. Why wont my function exit correctly?
    By LightsOut06 in forum C Programming
    Replies: 2
    Last Post: 10-09-2005, 09:23 PM
  5. C++ compilation issues
    By Rupan in forum C++ Programming
    Replies: 1
    Last Post: 08-22-2005, 05:45 AM