Need help with Linked Lists

[iDontGetIt]

Hi all,

I am trying to program linked lists, this time without looking at the book. The program is throwing an unhandled exception, accessing memory violation... then it references a memory address.

Hopefully my code is not egregious and I'm starting to come around to something workable. I would love to get my head wrapped around linked lists so I can move on to bigger and better things. Any assistance offered is very appreciated.

The first class creates the list nodes:

#include <iostream>
using namespace std;

class ListNode
{
	friend class List;
	int data;
	ListNode *next;
public:
	ListNode();
	ListNode(int);
};

ListNode::ListNode()
{	data = 0;
}

ListNode::ListNode(int v): data(v){}

The second class is the list itself:

#include "ListNode.h"

class List
{
	ListNode *first;
	ListNode *last;
public:
	List();
	ListNode* getIt()const;
	int getData()const;
	void addNode(int);
};

List::List()
{
	ListNode * nuList = new ListNode();
	nuList->next = last = 0;
	nuList = first;
}

ListNode* List::getIt()const
{	return first;
}

void List::addNode(int v)
{
	ListNode *nuNode = new ListNode(v);
	ListNode *currentPtr = first;

	if(currentPtr->next == 0)
		first->next = nuNode;

	while(currentPtr->next != 0)
		currentPtr->next = currentPtr;

	currentPtr->next = nuNode;
	nuNode->next = 0;

	delete currentPtr;
}

And finally, here is my driver. Fancy, I know:

#include "List.h"


using namespace std;



int main()
{
	List a;
	a.addNode(5);


	system("PAUSE");
	return 0;
}

[kooth]

Well, you didn't say where you were getting the violation.

In your List constructor, it looks like you are setting nuList to whatever first is pointing to, which seems backwards to me.

I'm not understanding your addNode() function at all.

In your ListNode constructor, initialize all of your class variables -- that way you don't have to do it in the List constructor.

[iDontGetIt]

I see...

I initialized all ListNode variables like you said.

The debugger seems to be stopping at line 30. I tried to investigate further, but it's over my head, still.

In the list constructor, I was trying to create the head of the list, the starting point. I was thinking no ListNode exists yet.. so I created one and set it to first. Would it be better if I coded it this way:

List::List()
{
	ListNode * nuList = new ListNode();
	nuList->next = nuList;
}

Unfortunately, I don't understand my addNode function either. The problem is my book doesn't break it down well. It gives me one large program (templated) that spans almost 3 pages and just references it throughout the chapter. It's a little overwhelming.

[iDontGetIt]

Here is what I have now! It still doesn't compile, it melts down with the same symptom. Hopefully the addNode() function is at least a little bit deconfusified.

#include <iostream>
using namespace std;

class ListNode
{
	friend class List;
	int data;
	ListNode *next;
public:
	ListNode();
	ListNode(int);
};

ListNode::ListNode()
{	data = 0;
        next = 0;
}

ListNode::ListNode(int v): data(v), next(0){}

//--------------End of ListNode-------

class List
{
	ListNode *first;
	ListNode *last;
public:
	List();
	void addNode(int);
};

List::List()
{
	ListNode * nuList = new ListNode();
	nuList->next = 0;
}


void List::addNode(int v)
{
    ListNode *currentPtr = first;

    while(currentPtr->next != 0)
        currentPtr = currentPtr->next;

    currentPtr->next = new ListNode(v);
    currentPtr->next = currentPtr;
    currentPtr->next = 0;
}

//----------------End of List---------

int main()
{
	List a;
	a.addNode(5);


	return 0;
}

[doug4]

In your List constructor, you are dynamically allocating a node and pointing the node's next pointer to itself. Nothing is being stored in the list, and when the constructor returns, there is a memory leak (nothing points to the allocated node).

Instead, just set the values of first and last to NULL. This indicates that there are no elements in the list to start.

In addNode you need to be careful with a number of things.

1. Check to see whether the list is empty, and manage first and last appropriately.

2. If you are just adding to the end of the list, there is no need to iterate through the whole list (lines 43 and 44). Just start at last.

3. Be careful assigning next pointers. Right now you are pointing the next pointer of the last element to the new element (line 46) and then to itself (line 47), and then re-assigning it to NULL (line 48). Draw a picture of the elements of the list as well as the new element and figure out how and when to set each pointer value. This includes first (when necessary), last, last->next and newNode->next.

[clanmjc]

good advice doug4

This topic might help you with your add function look at the adding to the queue about halfway down. http://www.cplusplus.com/forum/beginner/68736/

[iDontGetIt]

Thanks so much for this help ! =)

I remember reading that thread that you linked above. I feel that guys pain.

It compiles just fine now, at least for adding one node at a time. I can't wait until I get off work so I can add more stuff to it.

Eventually I will be able to add a copy and operator= easily to the List class (which is what my homework assignment is).

Cheers.