Back to For Beginners

Linked list explosion

For Beginners

Started by PrestoChung October 12, 2010 09:20 AM

5 comments, last by Steve132 13 years, 6 months ago

PrestoChung

334

Author

October 12, 2010 09:20 AM

When my program closes, a number of linked lists of unsigned integers are destructed. I put some console output into the destructor and pinpointed the line where I am getting a debug assertion error.

I'm going to post the LinkedList class below. I found the error to occur while clearing a list with 1 element. If I ignore the fact that the integer value of the element seems anomalous, and for some reason the element next & previous pointers point to DDDDDDDD, the actual address of the element is 003B6070 which is, I think, a normal address for something allocated to the free store.

The error occurs during the line that is supposed to delete the element:

PopFront():

if (First_ == Last_){				delete First_; //CRASH				First_ = 0;				Last_ = 0;				Length_ = 0;			}

I've double-checked all the insert/removal methods of the LinkedList and I can't find the problem.

In PopFront or PopBack, the ends of the list are set to null terminators. The only other places where elements are deleted without calling the PopFront or PopBack functions are in the RemoveAt() and Remove() functions which remove at an index or a particular value respectively. When they determine the element is not on the front or the end of the list, they remove it (delete it) and tie the preceding and following elements together.

Here's the element and the list classes:

class ListElem{public:	unsigned int Value()const{return Value_;}	ListElem* Next()const{return Next_;}	ListElem* Prev()const{return Prev_;}	void SetValue(const unsigned int& value_){ Value_ = value_; }	void SetPrev(ListElem* prev_){ Prev_ = prev_; }	void SetNext(ListElem* next_){ Next_ = next_; }	void Isolate(){ Next_=0; Prev_=0; }	bool IsIsolated(){ 		if	((Next_!=0) && (Prev_!=0))	{			return false;		}		else return true;	}	void PrintMe()const{		std::cout << "List Elem PrintMe:  Address: " << this << std::endl;		if(this == 0){			return;		}		else{			std::cout << "Value: " << Value_ << std::endl;			std::cout << "Next: " << Next_ << std::endl;			std::cout << "Prev: " << Prev_ << std::endl;		}	}	ListElem(const unsigned int& value_):Value_(value_),Next_(0),Prev_(0){}	ListElem(const unsigned int& value_, ListElem* prev_):Value_(value_),Next_(0),Prev_(prev_){}	ListElem(const unsigned int& value_, ListElem* prev_, ListElem* next_):Value_(value_),Prev_(prev_),Next_(next_){}	ListElem(ListElem* next_, const unsigned int& value_):Value_(value_),Next_(next_),Prev_(0){}private:	unsigned int Value_;	ListElem* Next_;	ListElem* Prev_;};class LinkedList{public:	LinkedList& Insert(const unsigned int& value_){		if (Length_ == 0){			First_ = new ListElem(value_);			Last_ = First_;		}		else if (First_ == Last_){			if(value_<=First_->Value()){				First_ = new ListElem(Last_, value_);				Last_->SetPrev(First_);			}			else{				Last_ = new ListElem(value_, First_);				First_->SetNext(Last_);			}		}		else{			if(value_ <= First_->Value()){				First_->SetPrev(new ListElem(First_, value_));				First_ = First_->Prev();			}			else if(value_ >= Last_->Value()){				Last_->SetNext(new ListElem(value_, Last_));				Last_ = Last_->Next();			}			else{				ListElem* curr_ = First_->Next();				while (value_ > curr_->Value()){					curr_ = curr_->Next();				}				curr_->Prev()->SetNext(new ListElem(value_, curr_->Prev(), curr_));				curr_->SetPrev(curr_->Prev()->Next());			}		}		++Length_;		return *this;	}	LinkedList& Remove(const unsigned int& value_){		ListElem* curr_ = Find(value_);		if(curr_==0){			std::cout << "LinkedList Remove Err: Value not found" << std::endl;		}		else if (curr_==First_){ PopFront(); }		else if (curr_==Last_) { PopBack(); }		else {			curr_->Prev()->SetNext(curr_->Next());			curr_->Next()->SetPrev(curr_->Prev());			delete curr_;			--Length_;		}		return *this;	}	unsigned int RemoveAt(const unsigned int& index_){		unsigned int val_out = MAX_UINT;		if(index_>=Length_){			std::cout << "LinkedList RemoveAt Err: Index out of bounds or list empty" << std::endl;			return val_out;		}		else if (index_==0){			val_out = First_->Value();			PopFront();			return val_out;		}		else if (index_==(Length_-1)){			val_out = Last_->Value();			PopBack();			return val_out;		}		else{			ListElem* curr_ = First_;			for(unsigned int i = 0; i < index_; ++i){				curr_ = First_->Next();			}			curr_->Prev()->SetNext(curr_->Next());			curr_->Next()->SetPrev(curr_->Prev());			val_out = curr_->Value();			delete curr_;			--Length_;			return val_out;		}	}	LinkedList& PopFront(){		if (First_ == 0){			std::cout << "LinkedList.PopFront() ERROR: First element points to NULL" << std::endl;			return *this;		}		else{			if (First_ == Last_){				std::cout << "First==Last!!" << std::endl;				delete First_;				First_ = 0;				Last_ = 0;				Length_ = 0;			}			else{				First_ = First_->Next();				delete First_->Prev();				First_->SetPrev(0);				--Length_;			}			return *this;		}	}	LinkedList& PopBack(){		if (Length_ == 0){			std::cout << "LinkedList.PopBack() ERROR: Empty list" << std::endl;			return *this;		}		else{			if (First_ == Last_){				delete Last_;				First_ = 0;				Last_ = 0;					Length_ = 0;			}			else{				Last_ = Last_->Prev();				delete Last_->Next();				Last_->SetNext(0);				--Length_;			}			return *this;		}	}	ListElem* First(){ return First_; }	ListElem* InspFirst()const{ return First_; }	unsigned int FirstValue()const{ return First_->Value(); }	ListElem* Last(){ return Last_; }	ListElem* InspLast()const{ return Last_; }	ListElem* Find(const unsigned int& value_){		if ( Length_ == 0 ){			std::cout << "Find Err: empty list" << std::endl;			return 0;		}		ListElem* curr_ = First_;		if ( (Last_->Value() - value_) < (value_ - First_->Value()) ){			curr_ = Last_;			while ( (curr_ != First_) && (curr_->Value() != value_) ){				curr_ = curr_->Prev();			}			if (curr_->Value() == value_){				return curr_;			}			else{				std::cout << "Find Err: value_ not found" << std::endl;				return 0;			}		}		else{			while ( (curr_ != Last_) && (curr_->Value() != value_) ){				curr_ = curr_->Next();			}			if (curr_->Value() == value_){				return curr_;			}			else{				std::cout << "Find Err: value_ not found" << std::endl;				return 0;			}		}	}	unsigned int Size()const{return Length_;}	LinkedList& Clear(){		while(First_ != 0){ PopFront(); }		std::cout << "Done clearing.  Printme: " << std::endl;		PrintMe();		return *this;	}	void PrintMe()const{		ListElem* elem_ = First_;		std::cout << "LinkedList PrintMe Function: " << std::endl;		std::cout << "List: ";		for (unsigned int i = 0; i < Length_; elem_ = elem_->Next(), ++i){			std::cout << elem_->Value() << " ";		}		std::cout << "Length: " << Length_ << std::endl;		std::cout << "First Pointer: " << First_ << std::endl;		First_->PrintMe();		std::cout << "Last Pointer: " << Last_ << std::endl;		Last_->PrintMe();		std::cout << "LinkedList PrintMe End" << std::endl;		std::cout << std::endl;	}	LinkedList():Length_(0),First_(0),Last_(0){}	~LinkedList(){		std::cout << "List dtor PrintMe called: " << std:: endl;		PrintMe();		Clear();	}private:	unsigned int Length_;	ListElem* First_;	ListElem* Last_;};

SiCrane

11,840

October 12, 2010 09:23 AM

Do you ever copy your linked list objects? Your class doesn't seem to be rule of three compliant.

Liam M

223

October 12, 2010 09:55 AM

Your code is very difficult to read, consider using whitespace, discarding those frankly bizarre underscores (where'd you pick that habit up from?) and placing {}'s on their own line (Java and me disagree here, and elsewhere). Also, could you please provide a working piece of code with a main() method, that can reliably cause the error you describe? That would make answering your question much easier.

Also, consider that there may be a more elegant way to implement a linked list: all those if/else pairs aren't particularly user friendly.

alvaro

21,604

October 12, 2010 12:10 PM

Yes, please provide a contained minimal program that we can compile and run ourselves.

The style is killing me too. This:

	bool IsIsolated(){ 		if	((Next_!=0) && (Prev_!=0))	{			return false;		}		else return true;	}

is a convoluted way of saying this:

	bool IsIsolated() {		return Next_==0 || Prev_==0;	}

Then again, the name of the method is not very good. I would say something is isolated only if both next and prev were 0.

PrestoChung

334

Author

October 12, 2010 07:02 PM

Quote:Original post by SiCrane
Do you ever copy your linked list objects? Your class doesn't seem to be rule of three compliant.

I have one function in another class that returns a LinkedList:

	LinkedList NonPortalWalls(const unsigned int& this_room)const{		LinkedList out_;		out_.Insert(5).Insert(4).Insert(3).Insert(2).Insert(1).Insert(0);		if(Portals_.Size()==0){ 			return out_; }		else{			for (ListElem* curr_ = Portals_.InspFirst(); curr_!=Portals_.InspLast(); curr_ = curr_->Next()){				switch(GetWall(this_room, curr_->Value()))				{				case N_:					out_.Remove(0);					break;				case S_:					out_.Remove(1);					break;				case E_:					out_.Remove(2);					break;				case W_:					out_.Remove(3);					break;				case U_:					out_.Remove(4);					break;				case D_:					out_.Remove(5);					break;				default:					break;				}			}			return out_;		}	}

So when it is used, it is assigned to a local LinkedList:

LinkedList dirs_ = NonPortalWalls(this_index);

I thought shallow copy would be enough and would be done automatically by the compiler. I just added one for good measure and it didn't affect the result.

I commented out the bit of code that is calling this function and it might be what is causing the problem. I'm going to look at it some more. But for now I don't have any simple code to post that demonstrates the error.

Quote:Original post by Liam M
Your code is very difficult to read, consider using whitespace, discarding those frankly bizarre underscores (where'd you pick that habit up from?) and placing {}'s on their own line (Java and me disagree here, and elsewhere). Also, could you please provide a working piece of code with a main() method, that can reliably cause the error you describe? That would make answering your question much easier.

The underscores are to differentiate variables from type & function identifiers.

I used to have brackets on their own lines when I first started out but now I don't find it necessary to preserve readability (for me) and it helps to display more code in less space (which means less scrolling and paging).

Quote:Original post by Liam MI would say something is isolated only if both next and prev were 0.

You're right, I had it backwards. That little bit of code was never finished or used so I've taken it out now. Thanks.

SiCrane

11,840

October 12, 2010 07:52 PM

Quote:Original post by PrestoChung
I thought shallow copy would be enough and would be done automatically by the compiler.

No, a shallow copy leaves two instances of your linked list class holding pointers to the same nodes. When one of those instances gets destroyed it frees the nodes and your other instance is left pointing to garbage.

Steve132

433

October 12, 2010 08:02 PM

Is there a particular reason you are doing this? Is it for a class assignment? If not, there's really no reason you shouldn't be using std::list

Linked list explosion

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Linked list explosion

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines