Traversing Singly Linked List

[rklein]

Okay, so I am an electrical engineering major in my senior year. I have some experience with embedded C as a result but decided to take a C++ class in my school's computer science department to reinforce some of the C that I'd forgotten while I specialized into power systems.

I have an assignment to set up a singly linked list using two class', both separated into a .h file for setup and .cpp file for implementation and member functions. One class is the Node class for the the links of the list, another is the OrderedList class for member functions such as inserting and removing nodes. I also have another source.cpp file given by my instructor to drive and test these.

The issue I'm having is that my currentNodePtr, a pointer I've designated for helping manipulating and traversing the list, does not appear to shift from Node to Node at all. As a result the program never enters my while loops as the ASCII values being compared are always the same. My intention with the while loop is that it will iterate until the conditional sees that the ASCII value of the node's payload to be inserted is larger than currentNodeptr's. Which should mean it places it the payload into the correct alphabetical position.

My instructor suggested using the line which is commented out:
Node * freshNodePtr = new Node(n);
in class and I THINK this might be a fix but I'm pretty unclear on what it does. If anyone could clarify this, or what the issue might otherwise be, I would be very appreciative.

Also, do let me know if there is anything I might explain further or if more of my code might be helpful.

#include <iostream>
#include "OrderedList.h"
#include "Node.h"

void OrderedList::insert(Node n)
{
	//Node * freshNodePtr = new Node(n);	// My instructor recommended this line of code in class
	Node* currentNodeptr = firstNodePtr;

	if (firstNodePtr == nullptr) // If the list has no entries yet, sets the firstNodePtr to that entry
	{
		firstNodePtr = &n;
	}
	else
	{	
		//std::cout << static_cast<int>(n.getPayload()[0]) << "\t" << static_cast<int>(currentNodeptr->getPayload()[0]) << std::endl;
		//std::cout << (static_cast<int>(n.getPayload()[0]) < static_cast<int>(currentNodeptr->getPayload()[0])) << std::endl;
		
		// Converts payloads, which are single letter strings, of the nodes to ASCII ints for comparison
		while (	static_cast<int>(n.getPayload()[0]) > static_cast<int>(currentNodeptr->getPayload()[0])	) 
		{
			if(currentNodeptr->getnextNode() == nullptr)
			{
				break;
			}
			else 
			{
				currentNodeptr = currentNodeptr->getnextNode(); //Traverses the linked list until it's found 
			}
		}
		n.setnextNode(currentNodeptr->getnextNode());
		currentNodeptr->setnextNode(&n);
	}
}

Node OrderedList::remove(Node n){return n;}

Node OrderedList::removeFront(Node n){return n;}

void OrderedList::clear(void){}

void OrderedList::absorb(OrderedList ol){}

void OrderedList::printOrderedList(void){}

[jonnin]

//Node * freshNodePtr = new Node(n);	// My instructor recommended this line of code in class
	Node* currentNodeptr = firstNodePtr;

	if (firstNodePtr == nullptr) // If the list has no entries yet, sets the firstNodePtr to that entry
	{
		firstNodePtr = &n;
	}

Taking the address of n may be risky. if main has something like

Node n; 
for(everything the user types in)
{
    n.something = input;
    n.other = more input;
    list.insert(n);
}

then you will end up with a very messed up list.

if you get a new one each time in insert and copy the data from the incoming n into the new memory, your list may fare better.

what you did can work, but you have to make it work and its subtle how to do that.

See if getting fresh memory each insert helps with the issues you are seeing. I don't see anything else major, but I did not dig into it looking for trouble either.

if you recall your C well, new is akin to malloc, and delete is akin to free.

new gets a chunk of ram big enough to store the type.
so new node gives you a pointer to a new piece of memory big enough to hold a node object. every call to new must be matched to a delete later, but for now, you can let that slide until you have your insert working.

the idea is that you start with a null node pointer.
you get a node data chunk from user or file or something to put into the list.
so you ask for a new piece of memory, and that becomes the list head, and its next pointer is now null.
Then you get another piece of data, and you ask for more memory, and then you either say head -> next is the new item, or new item -> next is head, depending on which comes first (I see you call it ordered list so I assume you want to sort the data as you insert it). When you get the new piece of data, its next pointer should start out as null. So for a moment you have head, whos next is null, and temp, whos next is null. say head is to come first: head->next is assigned to temp. now your list is head, temp, null because temp's next is still set null, head's next is set temp. it begins to chain up that way and each iteration you do this. And if you insert in the middle of two nodes, say the above chain now you want to go head, third guy, second guy as your list, you have to break and assign the pointers in the right order so you don't lose any of them. If you ever have memory chunk with no variable holding that address, its gone. Does that make sense?
A picture may help, you can google animated linked lists to get a feel for what you are wanting to do visually.

[rklein]

Okay, I think I'm starting to understand a little better after this and a chat with my instructor. Thanks!

Will keep working and possibly post the end result in case anyone cares lol.

[dhayden]

Please post OrderedList.h and Node.h