List inserting error, see last post

Memory problem I can't figure out

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 3707 Views - Last Post: 27 March 2007 - 12:26 AM Rate Topic: -----

#1 bennyboy371  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 04-December 06

List inserting error, see last post

Posted 25 March 2007 - 07:40 PM

Okay, so I've been learning C++ and my class has a list assignment due. I've been working on this on and off for over a week and a half, and started over about a dozen times. In addition to needing a dummy head node and being circular, it must be a doubly linked list.

While I need help with all of these points, I'm mainly here because of my insert method. It tells me I have an unhandled exception and an access violation at the point that the code attempts to insert the new node into the list.

Any help would be appreciated, I know I'm not very good with this but I'd like to learn.

#include <iostream>
#include <iomanip>

using namespace std;


class List{
public:
	List();
	int getLength();
	void insert(int index, int newItem);
	//void remove(int index);
	void getItem(int index);
	void dispList();

private:

	struct Node{
		int item;
		Node *prev;
		Node *next;
		};
	int listSize;
	Node *head;
	Node *find(int index);
};


// Constructor
List::List(){
	listSize = 0;
	head = NULL;
};

// Returns length of list
int List::getLength(){
	return listSize;
};

// Traverses list for index
List::Node *List::find(int index){
	if ( (index < 1) || (index > getLength()) )
		return NULL;
	else{
		Node *cur = head;
		for (int incr = 1; incr < index; ++incr)
			cur = cur->next;
		return cur;
	}
};

// inserts a node into the list
void List::insert(int index, int newItem){
	if ( (index < 1) || (index > (listSize + 1)) ){
		cout << "Error: Index Out of Range." << endl;
	}
	else{
		++listSize;
		Node *cur = find(index);
		Node *newPtr = new Node;
		newPtr->item = newItem;

		newPtr->prev = cur->prev;
		newPtr->next = cur;
		cur->prev = newPtr;
		(newPtr->prev)->next = newPtr;
	}
};


// removes a node at index
/*
void List::remove(int index){
	if( (index < 1) || (index > listSize) ){
		cout << "Error: Index Out of Range.";
	}
	else{


	}
};
*/

// gets item of index
void List::getItem(int index){
	Node *cur = find(index);
	cout << cur->item;
};

// displays list
void List::dispList() {

	for(int i = 1; i <= listSize; i++){
		cout << "Item in index " << i << " is ";
		getItem(i);
		cout << ".\n";
	}
	cout << "Length is " << listSize << "." << endl;
	cout << endl;

};

int main(){
	List aList;

	aList.insert(1,5);
	aList.insert(1,8);
	aList.insert(1,2);
	aList.dispList();

	return 0;
}

This post has been edited by bennyboy371: 26 March 2007 - 09:10 PM


Is This A Good Question/Topic? 0
  • +

Replies To: List inserting error, see last post

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: List inserting error, see last post

Posted 25 March 2007 - 08:03 PM

Well you increase listSize before you have found the index... that means that find() is being lied to about how many nodes there are and I bet that is your access violation.
Was This Post Helpful? 0
  • +
  • -

#3 bennyboy371  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 04-December 06

Re: List inserting error, see last post

Posted 25 March 2007 - 08:07 PM

I'm not sure if it makes enough of a difference, but I just set it to increase the list size at the end of the insert method rather than at the beginning, and it still gives the same error.
Was This Post Helpful? 0
  • +
  • -

#4 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: List inserting error, see last post

Posted 25 March 2007 - 08:37 PM

well I lost my bet.

The problem is that you insert assumes that there is already something in the list.
	   Node *cur = find(index); // return null becuse there is nothing to find...
		Node *newPtr = new Node;
		newPtr->item = newItem;

		newPtr->prev = cur->prev; //exception as cur==NULL



here is what I did to fix it:
// inserts a node into the list
void List::insert(int index, int newItem){
	if ( (index < 1) || (index > (listSize + 1)) ){
		cout << "Error: Index Out of Range." << endl;
	}
	else{
		Node *cur = find(index);
		Node *newPtr = new Node;
		newPtr->item = newItem;
		//If find did not return a NULL pointer
		if (cur) 
		{
			newPtr->prev = cur->prev;
			newPtr->next = cur;
			cur->prev = newPtr;
			(newPtr->prev)->next = newPtr;
		} else //inserting the head of list...
		{ 
			\\Here we make a new head node...
			head = newPtr;
			\\Here we want to set up the pointers...
			head ->next=head;
			head ->prev=head;
		}
		++listSize;
	}
};

Please check the logic...
Was This Post Helpful? 0
  • +
  • -

#5 bennyboy371  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 04-December 06

Re: List inserting error, see last post

Posted 25 March 2007 - 08:49 PM

Well it compiles fine, so thank you very, very much. Though, I'm not sure I entirely understand why. I'd thought I already had a list head node? This is all rather confusing as I'm still learning.

Since I'm supposed to have a circular list with a dummy head node... was this line in the class
Node *head;

merely a pointer to the head of the list, making the list entirely empty?

As far as I could tell, once it was circular my original code should've worked, had there been a dummy header there, but I'm not entirely sure I understand that concept.

This post has been edited by bennyboy371: 25 March 2007 - 08:49 PM

Was This Post Helpful? 0
  • +
  • -

#6 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: List inserting error, see last post

Posted 25 March 2007 - 10:28 PM

Well actually I think you misunderstand the idea of a double-liked list with a dummy head node.

normally (as I understand it) the dummy node would always be the head, and it would not have a stored value. So you would have a constuctor something like:

// Constructor
List::List(){
	listSize = 0;
	head = new Node;
	head->item = -1 //This value is NEVER used...
	head->next = head;
	head->prev = head;
};


Now the head always points to this "dummy" node. It is called a "dummy" because it does not hold a value it is just ued for the pointers.

Make sure you look over your text book/course material to ensure that you understand what this ADT looks like.

The below graphic comes from this power point slide

Attached image(s)

  • Attached Image

Was This Post Helpful? 0
  • +
  • -

#7 bennyboy371  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 04-December 06

Re: List inserting error, see last post

Posted 25 March 2007 - 10:33 PM

The graphic also comes from my textbook. :-P

I was also confused by it as there is an external pointer directed to the dummy node as well. Hmm, well, you've helped quite a bit, thank you very much. I'll be speaking with my instructor tomorrow about this as well.
Was This Post Helpful? 0
  • +
  • -

#8 bennyboy371  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 04-December 06

Re: List inserting error, see last post

Posted 26 March 2007 - 08:33 PM

I'm back. I got a lot of my problems hammered out, its circular now, but I can't seem to get my insert working. I think it has something to do with how I'm handling the head node, but I honestly can't see why.

As far as I can tell, its creating a new node after head, then attempting to alter the pointers in the head. I get an access violation error while its setting the first pointers, however.

My problems seem to be wholly in the insert method and the List constructor. Could anyone point me in the right direction again?

#include <iostream>
#include <iomanip>

using namespace std;

class List{
public:
	List();
	int getLength();
	void insert(int index, int newItem);
	void remove(int index);
	void getItem(int index);
	void dispList();

private:

	struct Node{
		int item;
		Node *prev;
		Node *next;
	};

	int listSize;
	Node *head;
	Node *find(int index);
};

// Constructor
List::List(){
	listSize = 0;
	head = new Node;
	head->item = -1;
	head->prev = head;
		head->next = head;
};

// Returns length of list
int List::getLength(){
	return listSize;
};

// Traverses list for index
List::Node *List::find(int index){
	if ( (index < 1) || (index > getLength()) )
		return NULL;
	else{
		Node *cur = head;
		for (int incr = 1; incr < index; ++incr)
			cur = cur->next;
		return cur;
	}
};

// inserts a node into the list
void List::insert(int index, int newItem){
	if ( (index < 1) || (index > (listSize + 1)) ){
		cout << "Error: Index Out of Range." << endl;
	}
	else{
		Node *cur = find(index);
		Node *newPtr = new Node;
		newPtr->item = newItem;
		// setting pointers
		newPtr->prev = cur;
	cur->next = newPtr;
	newPtr->next = cur->next;
		// closing the circle, so to speak
	if(newPtr->next == head){
		head->prev = newPtr;
	}

	++listSize;
	}
};

// removes a node at index
void List::remove(int index){
	if( (index < 1) || (index > listSize) ){
		cout << "Error: Index Out of Range.";
	}
	else{

	}
};

// displays item of index
void List::getItem(int index){
	Node *cur = find(index);
	cout << cur->item;
};

// displays list
void List::dispList() {

	for(int i = 1; i <= listSize; i++){
		cout << "Item in index " << i << " is ";
		getItem(i);
		cout << ".\n";
	}
	cout << "Length is " << listSize << "." << endl;
	cout << endl;

};

int main(){
	List aList;

	aList.insert(1,5);
	aList.insert(1,8);
	aList.insert(1,2);
	aList.dispList();

	return 0;
}

This post has been edited by bennyboy371: 26 March 2007 - 09:01 PM

Was This Post Helpful? 0
  • +
  • -

#9 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: List inserting error, see last post

Posted 26 March 2007 - 09:45 PM

		// setting pointers
		newPtr->prev = cur;
	cur->next = newPtr;
	newPtr->next = cur->next;


So lets think about this... netPtr->prev = cur, ok... cur->next=newPtr, ok
now: newPtr->next = cur->next (=newPtr from last statemant)... problem
newPtr->next now == newPtr... not very helpful.
	   newPtr->prev = cur;
	newPtr->next = cur->next;
	cur->next = newPtr;

Might work better...
Was This Post Helpful? 0
  • +
  • -

#10 bennyboy371  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 04-December 06

Re: List inserting error, see last post

Posted 26 March 2007 - 09:50 PM

Okay, I figured out that I was asking it to insert at the wrong area, and reworked the pointer coding, but it still gives the same error at the first pointer.


EDIT: I just figured out that the first pointer in this code will set the new pointer as head if the list is empty, I must figure out how to rework the code for this.
void List::insert(int index, int newItem){
	if ( (index < 1) || (index > (listSize + 1)) ){
		cout << "Error: Index Out of Range." << endl;
	}
	else{
		++index; // to not count head node
		Node *cur = find(index-1); // to make sure that insert is at right index
		Node *newPtr = new Node;
		newPtr->item = newItem;
		
		(cur->next)->prev = newPtr; // accommodation for next node
		newPtr->next = cur->next;
		newPtr->prev = cur;
		cur->next = newPtr;

		if(newPtr->next == head){
			head->prev = newPtr;
		}

		++listSize;
	}
};

This post has been edited by bennyboy371: 26 March 2007 - 09:55 PM

Was This Post Helpful? 0
  • +
  • -

#11 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: List inserting error, see last post

Posted 26 March 2007 - 10:03 PM

...sorry I should read more carefully before I post...

What error is it giving you?

The only funny thing I see is:

		if(newPtr->next == head){
			head->prev = newPtr;
		}

which does not seem nessisary to me...

This post has been edited by NickDMax: 26 March 2007 - 10:08 PM

Was This Post Helpful? 0
  • +
  • -

#12 bennyboy371  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 04-December 06

Re: List inserting error, see last post

Posted 26 March 2007 - 10:12 PM

Its telling me: Unhandled exception at 0x0041174c in Assignment1.exe: 0xC0000005: Access violation reading location 0x00000008.

This is at the point of the pointers definition. The setting of the head->prev to the new pointer is to make it circular, handling the tail node well.
Was This Post Helpful? 0
  • +
  • -

#13 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: List inserting error, see last post

Posted 26 March 2007 - 10:30 PM

Can you post you code as it stands.

As for the bit about being circular, my point is that the code above this should take care of that. This seems redundant.

		(cur->next)->prev = newPtr; //***This Line***
		newPtr->next = cur->next; //***Combined With This Line ***
		newPtr->prev = cur;
		cur->next = newPtr;

		if(newPtr->next == head){
			head->prev = newPtr;   //***Same Thing as This Line***
		}

Was This Post Helpful? 0
  • +
  • -

#14 bennyboy371  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 04-December 06

Re: List inserting error, see last post

Posted 26 March 2007 - 10:37 PM

Unfortunately I haven't made any progress. Ah, I see what you mean, its made redundant by the second line.

As I see it, my biggest problem at the moment is the first line. It should work for every node but the last, but as current is head, its effectively setting head = newPtr, which is a big problem.

EDIT: I think I can make things simpler for me if I set the code up to have the current pointer after the node to be inserted rather than before it.

Here is what I have now:

strangely enough, its exactly as I started with last night, except pointing to the wrong node as current. O.o

void List::insert(int index, int newItem){
	if ( (index < 1) || (index > (listSize + 1)) ){
		cout << "Error: Index Out of Range." << endl;
	}
	else{
		Node *cur = find(index+1); // sets current to node after that to be inserted
		Node *newPtr = new Node;
		newPtr->item = newItem;
				
		newPtr->next = cur;
		newPtr->prev = cur->prev;
		cur->prev = newPtr;
		newPtr->prev->next = newPtr;

		++listSize;
	}
};

This post has been edited by bennyboy371: 26 March 2007 - 10:52 PM

Was This Post Helpful? 0
  • +
  • -

#15 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: List inserting error, see last post

Posted 26 March 2007 - 10:51 PM

what I meant was can I see the whole tamali so I can load it in my debugger and watch it roll... not only that it helps to see what is going on in the whole program.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2