View Full Version : Java and ListNodes

03-05-2005, 05:24 PM
I have an assignment that I can't get. I've narrowed it down to one method that's causing the problem, so any guidance would be fantastic.

public void addLast(Object value)
if (first == null)
first = new ListNode(value, null);
last = first;
last = new ListNode(value, null);


It's suppose to take the value entered and add a new node at the end of my node list. I'm suppose to create a node list of numbers 1-20, but only the number 1 is added. The size of my node list is also only one so I know that it is not a printing out of the information issue.

I've attached the rest of my code.

This is for the JavaAB test so I'm basicly on my own to learn it, so I have a few another question about list nodes while I'm at it. Why are they useful? It seems that using an Array or arraylist would accomplish the same task.

03-05-2005, 09:18 PM
Look at your else clause.

last = new Node(blablabla);

Because the list is nonempty at this point, first points to the first node, and last points to the last node.

Now, that line *replaces* the last node, not appends it.

Assumably your ListNode class has a .next property.

What you really want is to assign something to last.next, and then make sure the variable last is pointing to where it needs to be.

03-06-2005, 06:19 AM
Thank you, it took me about 15 minutes to figure it out from what you said so I think I have a better understanding of them.

But I still don't see the advantage over array lists. From what I've read they are compare to arrays, but since sometimes you need array to "grow" linked lists are more suitable. Is this just another option available? Or are they better for sorting or something like that?

03-06-2005, 10:15 AM
Alright, now that you've figured out LinkedLists, here is why they are a *good thing*.

Say you want to represent a stack (careful word choice :)) of papers. You can use an array if you want, index 0 being immediately on top of your desk, index 5 being a little higher up, and so on.

Now, let's say you are like me, and let homework pile 3 feet high by the time it hits Wednesday, but the rest of the week the pile is nearly zero.

Now, 3 feet high is a lot of paper. Does it make sense to allocate several thousand memory addresses for something that is usually small, only because for one day of the week (maybe only 1 week of the year... finals time)? Of course not, that's just inefficient.

What we want is a datatype that can grow and shrink to arbitrary sizes, and only do that when requested to. If we use a Linked List (let's ignore the stack idea for now), then we simply do:

first = new Node("Complex Analysis, page 134", first.next);

And we've made the pile larger. 20 hours later when I finally figure out the proof of the maximum modulus principle, I happily say:

first = first.next;
(and let Java garbage collect)

And I've removed it from memory. Or I could do last.next = new Node("bla", null); last = last.next; If i wanted to insert at the end. (Removing from the end requires an O(n) operation though, if one-dimensional links)

And come finals week, I've made a stack of papers a mile high. I finally hit summer vacation, my computer is not still allocating that much memory, it's down to about 0 bytes of usage to represent my homework load.

Compare this to an array. I say Homework[] load = new Homework[10000000];

and always hold hostage that much memory. That's just silly.

I hope that makes a little sense. Use arrays when you amount of data you're dealing with is pretty much constant, use lists when the amount is highly variable.

03-06-2005, 10:40 AM
Also keep in mind that myarray[n] is an O(1) operation, but mylist.item(n) is an O(n) operation. Arrays are faster at accessing data if you are accessing it non-sequentially. If you're accessing it sequentially, however, does it really matter if you call myarray[i++] repeatedly or currentNode = currentNode.next? Not at all.

03-06-2005, 05:48 PM
Thanks jkd, the stack of homework is the perfect example for me! :thumbsup: