Add at end of LinkedList

[LinkedList]

Okay I'm trying to add elements at the end of a LinkedList and so far I have the following code in my add() method (located in my LinkedList class):

public void add(Person newPerson)
{
Node node;
Node finalNode;

node = new Node(newPerson, null);
if (firstNode == null)
{
firstNode = node;
}
else
{
finalNode = firstNode;
while(finalNode.getNextNode() != null)
{
finalNode = finalNode.getNextNode();
}
finalNode.setNextNode(node);
}
}

and the following is from my node class:

public Node getNextNode()
{
return nextNode;
}

public void setNextNode(Node nextNode)
{
this.nextNode = nextNode;
}

But when I try to run it, the program never completes (i.e. It seems as though the while loop never terminates). Can anyone help me with this?

[Old Pedant]

How about just showing us the entire class???

You know, this would be trivial if you kept track of both the firstNode *AND* lastNode at the class level. So you'd never need to use a while loop in the first place.


class Node
{
public Object obj;
public Node nextNode;
}
class LinkedList
{
private Node firstNode = null;
private Node lastNode = null;
public void add(Student s)
{
Node newNode = new Node(s, lastNode);
if ( lastNode != null ) lastNode.nextNode = newNode;
if ( firstNode == null ) firstNode = lastNode;
}
}

No?

[LinkedList]

Well this is a sample program I copied straight from my textbook because I wanted to see how it performed, but it's not working and I can't understand why. I even checked more than 10 times to see if I copied it out right and I did.

However, I tried placing
System.out.println(lastNode);
right after
lastNode = lastNode.getNextNode();
in the while loop and it seems to print out the first person constantly without actually getting the next person, so it seems like there's something wrong with my getNextNode() method or maybe my Node class in general, but I can't figure it out. Any ideas?

[LinkedList]

Well, I looked into it a little bit more and apparently it's not just repeating the same person over and over but it's repeating the first two (of four in total) over and over.

[Old Pedant]

Well, I'd still like to see the complete classes. I honestly don't see it with the code you showed.

[LinkedList]

This is the program:

public class persons
{
public static void main(String[] parms)
{
LinkedList people;

people = createList();
print(people);

System.out.println("\nProgram completed");
}

public static LinkedList createList()
{
LinkedList people;

people = new LinkedList();

people.add(new Person("Alex"));
people.add(new Person("Jeff"));
people.add(new Person("Mary"));
people.add(new Person("Patrick"));
return people;
}

public static void print(LinkedList list)
{
int count;

System.out.println("\n");
for (count=0; count<list.size(); count++)
{
System.out.println(list.get(count));
}
}
}

class LinkedList
{
private Node firstNode;

public LinkedList()
{
firstNode = null;
}

public void add(Person person)
{
Node node;
Node finalNode;

node = new Node(person, firstNode);
if(firstNode == null)
{
firstNode = node;
System.out.println(firstNode);
}
else
{
finalNode = firstNode;
while(finalNode.getNextNode() != null)
{
finalNode = finalNode.getNextNode();
System.out.println(finalNode);
}
finalNode.setNextNode(node);
}
}

public Person get(int position)
{
Node currentNode;
Person currentPerson;
int current;

currentPerson = null;
current = 0;
currentNode = firstNode;
while ((currentNode!=null) && (current<=position))
{
currentPerson = currentNode.getPerson();
currentNode = currentNode.getNextNode();
current++;
}
return currentPerson;
}

public int size()
{
Node currentNode;
int size;

size = 0;
currentNode = firstNode;
while (currentNode!=null)
{
currentNode = currentNode.getNextNode();
size++;
}
return size;
}
}

class Node
{
private Person person;
private Node nextNode;

public Node(Person person, Node nextNode)
{
this.person = person;
this.nextNode = nextNode;
}

public Person getPerson()
{
return person;
}

public Node getNextNode()
{
return nextNode;
}

public void setNextNode(Node node)
{
nextNode = node;
}

public String toString()
{
return person.toString();
}
}

class Person
{
private String personName;

public Person(String personName)
{
this.personName = personName;
}

public String toString()
{
return personName;
}
}

[cs_student]

Next time please format your code properly. I'm not going to bother reading it if it's not formatted properly.

I think the problem lies within your add method. I don't thin you will ever have more than one node in your list since while(finalNode.getNextNode() != null)
would initially result in a false conditional thus inhibiting a next node from ever being added. Besides that it looks like your add method wouldn't work anyways.

Why not try something like


public void add(T obj)
{
// make the new node the head node, and link it to the last head node
firstNode = new Node(obj, firstNode);
}



It seems much simpler and easier to comprehend to me.
Also, I would suggest that you keep track of the size of your list that way you don't have to iterate through the entire thing every time you call the size() method.


cs_student

[LinkedList]

Oh, sorry about that, I wasn't sure of how to get the properly formatted code pasted in a post. I fixed it now.

Also, your example of adding an object to the linked list is only adding it to the "beggining" which makes my output


Patrick
Mary
Jeff
Alex

Program completed


when I want it to be


Alex
Jeff
Patrick
Mary

Program completed


So what the program is supposed to do is add it so that it is in the order that is shown with Alex first. The textbook called it inserting at the end of a LinkedList because what it's trying to do is add the next object at the end of the LinkedList (i.e. Alex is already in the LinkedList so Jeff gets added after).

[Old Pedant]

Well, CS, that's much the same as I told him in my first post.

I assumed that the homework requirement was indeed to put the new elements on the *end* of the list, so your code using firstnode wouldn't do the job.

As I said, then, if he kept track of both the first and last node then adding to the end of the list is much easier.

So...pretty much in agreement.

But I don't see your point about the while loop. Let me format it and see if we can make sense of it:
public void add(Person person)
{
Node node;
Node finalNode;
node = new Node(person, firstNode);
if(firstNode == null)
{
firstNode = node;
System.out.println(firstNode);
}
else
{
finalNode = firstNode;
while(finalNode.getNextNode() != null)
{
finalNode = finalNode.getNextNode();
System.out.println(finalNode);
}
finalNode.setNextNode(node);
}
}

Okay, so let's pretend to be the computer.

We add the first Person. "Adam".

That creates a new Node for "Adam" where the nextNode property of that new node is null (because firstNode was null when the constructor was invoked). And then the class-scope variable firstNode is set to reference that newly created Node.

We add the second Person. "Bob".

That creates a new Node for "Bob" where the nextNode property of that new node references the "Adam" node (because firstNode referenced the "Adam" node when the constructor was invoked). And then we proceed to the "else" code:
-- finalNode copies firstNode, so it references the "Adam" node.
-- we enter the "while"
-- finalNode.getNextNode() indeed returns a null (see the description of the creation of the "Adam" node, above) so the loop never actually executes
-- we change the nextNode property of the "Adam" node (referred to by the finalNode variable) to reference the new "Bob" node.
-- Done.

We add the *THIRD* Person. "Carl".

That creates a new Node for "Carl" where the nextNode property of that new node references the "Bob" node (because firstNode referenced the "Bob" node when the constructor was invoked). And then we proceed to the "else" code:
-- finalNode copies firstNode, so it references the "Adam" node.
-- we enter the "while"
-- finalNode.getNextNode() returns the reference to "Bob" that is in the "Adam" node.
-- so finalNode is set to reference the "Bob" node.
-- finalNode.getNextNode() returns the reference to "Adam" that is in the "Bob" node (see the text in Magenta, above).
-- so finalNode is set to reference the "Adam" node.
-- finalNode.getNextNode() returns the reference to "Bob" that is in the "Adam" node.
-- so finalNode is set to reference the "Bob" node.
-- finalNode.getNextNode() returns the reference to "Adam" that is in the "Bob" node (see the text in Magenta, above).
-- so finalNode is set to reference the "Adam" node.
-- finalNode.getNextNode() returns the reference to "Bob" that is in the "Adam" node.
-- so finalNode is set to reference the "Bob" node.
-- finalNode.getNextNode() returns the reference to "Adam" that is in the "Bob" node (see the text in Magenta, above).
-- so finalNode is set to reference the "Adam" node.
-- finalNode.getNextNode() returns the reference to "Bob" that is in the "Adam" node.
-- so finalNode is set to reference the "Bob" node.
-- finalNode.getNextNode() returns the reference to "Adam" that is in the "Bob" node (see the text in Magenta, above).
-- so finalNode is set to reference the "Adam" node.
... ad infinitum ...

So *NOW* do you see the root of the problem? It's dirt simple.

[Old Pedant]

public void add(Person person)
{
Node node;
Node finalNode;
node = new Node(person, null); // THE FIX IS IN!
if(firstNode == null)
{
firstNode = node;
System.out.println(firstNode);
}
else
{
finalNode = firstNode;
while(finalNode.getNextNode() != null)
{
finalNode = finalNode.getNextNode();
System.out.println(finalNode);
}
finalNode.setNextNode(node);
}
}


Except now that code agress with what you made in your first post. So now I'm even more confused. Why didn't it work back then???

[cs_student]

I figured that it would become a circularly linked list, but I didn't feel like going through it.

I drew up a simple singly linked list class real quick.

I haven't tested it and am sure it has some bugs, but it should help you get an idea of how to create a singly linked list.


public class SList<T>
{
Node<T> firstNode = null;
Node<T> tailNode = null;
public SList(T obj)
{
firstNode = new Node<T>(obj);
tailNode = firstNode;
}
public SList() {}

public void insertInFront(T obj)
{
firstNode = new Node<T>(obj, firstNode);
}

public void insertInBack(T obj)
{
tailNode = firstNode.sendBack(obj);
}
public T get(int pos)
{
get(pos, firstNode);
}


private T get(int pos, Node<T> node)
{
if(node == null)
return null;
else if(pos >= 1)
return node.data();
else
return get(pos--, node.next());
}

public class Node<T>
{
T data = null;
Node<T> nextNode = null;
public Node<T>(T data)
{
this.data = data;
}
public Node<T>(T data, Node<T> nextNode)
{
this.nextNode = nextNode;
}

public T data()
{
return data;
}

public Node<T> next()
{
return nextNode;
}
public Node<T> sendBack(T obj)
{
if(nextNode == null)
return nextNode = new Node<T>(obj);
else
return nextNode.sendBack(obj);
}
}
}



I used recursion to make things simpler as well as generics so that SList can use any data container.


cs_student

[LinkedList]

Wow, I replaced:

node = new Node(person, firstNode);


with:

node = new Node(person, null);

in the add() method like you had mentioned, Old Pedant, and it seemed to have worked. Can't believe it was that simple, yet it makes so much sense. Also, thanks for the added details on LinkedList (both of you) that actually really helps. I'm not the brightest when it comes to LinkedLists.

[Old Pedant]

Like I said, I don't understand why the code didn't work at the time of your first post, where you were using null in the call.

But presumably there was something else wrong at that time.

Anyway... Don't be afraid to do as I did: Become the computer and actually try to execute the code. When you do so, be careful not to make any assumptions! Try very very hard to behave exactly according to the code with no outside influences.

And, of course, find and learn to use a debugger.

[cs_student]

And, of course, find and learn to use a debugger.


These are words of wisdom. Debuggers have a bit of a learning curve, but will help you greatly in the long run.

[LinkedList]

Cool, I'll look into it. Thanks again, guys!