Creating a node which stores the next node

[epheterson]

I'm having a mental block here. My task is to create a class, called node from hence forth, that has attributes such as strings and ints which define it. This node must also reference another node which is to be the next node "in line."

So here's my mental block, where do I create this new node in my class? I want it to always exist, and be accessible. When I place it before the constructor, I end up with an infinite loop kind of situation, rightfully so. As any node is created, it must create another. If I place it within any method, constructor or otherwise, it's stuck in this method.

Where do I define this so that it does not create an infinite loop, but does let me set it to either null or another node within methods.

My work in progress, which should be enough to convey what I'm trying to do:
class node
{
// Declare all variables to be used
String name;
int priority;

// Create the node which will store the next node
node nextNode = new node();

public node()
{
System.out.println("New node created");
}

public node(String name, int priority)
{
System.out.println("New node created and assigned "+name+priority);
this.name = name;
this.priority = priority;
}
public node(String name, int priority, node newNextNode)
{
this.name = name;
this.priority = priority;
this.setNextNode(newNextNode);
}

public String getName(){
return this.name; }

public int getPriority(){
return this.priority; }

public String setName(String name){
this.name = name; }

public int setPriority(int priority){
this.priority = priority; }

public node setNextNode(node newNextNode)
{
nextNode.setName(newNextNode.getName());
nextNode.setPriority(newNextNode.getPriority());
}

public node getNextNode()
{
return nextNode;
}


}

BTW, thanks for any and all help here. CodingForums has helped me out so much in the past and always does.

-Eric

[cs_student]

I am confused to as what you are having trouble with. Yes, if you were to create a new node in the constructor (which created a new node in the constructor ...) you would cause a stack overflow because it would go on until the program ran out of memory. However, I don't think the professor wants you to do anything of the such.

The class you provided seems to adequately fulfill the Node class which you described. You can add a node to the need of the node (using the setNextNode() method).

However, you could make setNextNode() a little cleaner and robust. You probably just want to have

public node setNextNode(node newNextNode)
{
// there is no tail node
if(nextNode == null) {
nextNode = newNextNode;
} else {
// tell tail node to make newNextNode it's tail node
nextNode.setNextNode(newNextNode);
}
}


If you aren't going to use newNextNode outside of the scope of the Node class it's safe to just set nextNode to the reference.

Also you can just recursively send the node to the very end of the list.

For more information check out the wikipedia page on nodes (http://en.wikipedia.org/wiki/Node_%28computer_science%29). It gives a explanation of what they are and how the can be applicable to certain structures in computer science.


Regards,


cs_student

[epheterson]

The problem with the code I posted is I get a stack overflow. I'm still very unclear where the nextNode will be stored.

Did you mean to send me something like:
public node setNextNode(node newNextNode)
{
// there is no tail node
if(nextNode == null) {
node nextNode = new node(newNextNode);
} else {
// tell tail node to make newNextNode it's tail node
nextNode.setNextNode(newNextNode);
}
}


where a new node is created? The problem with this is that we're referring to nextNode before its created. How can I create a new node in setNextNode and have it be visible to the rest of the node class?

I'm sorry, understanding this has turned out to be somewhat frustrating, thanks for working through it with me.

[Fou-Lu]

There is no reason to actually create a new node within the node.
I'm lazier than cs_student is, so I actually wouldn't recommend a chain passing technique (I'll get into why after). Instead, I'd have this style for node:

class Node<T>
{
private T data;
private int priority;
private Node next;
// I'll just throw some quickies together:
public Node()
{
this(null, 0);
}
public Node(T data, int priority)
{
this(data, priority);
}
public Node(T data, int priority, Node next)
{
this.data = data;
this.priority = priority;
this.next = next;
}
public void setNextNode(Node n)
{
// Here you need to decide if you're taking an object 'reference' or if you
// plan to clone. I'd take a reference myself.

Node current = this.next;

// Ok, you'll need to decide what you'll do if this isn't null. If the current
// exists as a Node, than you'll lose track of the remaining chain. If you
// plan to insert, than you can link the 'current' to the n.setNextNode.
// Another option is to perhaps return the 'lost' part of the chain. Or of
// course you can simply throw an exception if its not null. All up to you.

this.next = n;
// And simple as that.
}
}


Why I recommend this? As I mentioned, I'm lazy and would rather use the Node as an absolute base for any collection container really limiting the amount of work I need to do to write more classes. So, what we can do at this point is extend the node class to handle multi-direction nodes which can be used to handle doubly linked lists, trees etc. But if you recurse down the list to find the node it always has to be in the end. I leave it up to my lists to always track a start and end for my lists. This is where you make the choice, track it in you're collection, or pass it from you're node. Both work great.

Using a language like C is way easier to do this. You can use a single 'next' field to handle both directions if you use an XOR on you're 'previous' and 'next' memory addresses. Then when traversing it you can give it you're current location, XOR it to the 'next' value, and it will give you either the memory address for the 'next' or the 'previous' depending on the direction you're coming from. Thats super sweet.

[epheterson]

Aha! Thank you guys! To be honest, Fou-Lu, you were a little over my head there. I don't know exactly what you were implying, but there must be individual nodes as per the documentation. Also, I will have to insert and read nodes recursively.

Ready for this, my problem was that I was creating a new node not just declaring one.

ie. I was calling:
node nextNode = new node();

when I should have been calling:
private node nextNode;


Subtle, but makes all the difference. I realized this after seeing Fou-Lu's suggestion. The way java works is still not completely clear to me, so I'm running into these roadblocks.

Thanks for the help!