Nullpointer.. am I losing a reference in this code?

[michael bradly]

I'm getting a null pointer and am wondering if I am losing a reference somewhere. I am trying to reverse the references in a list.
Assume the list had three items 1) milk 2) eggs 3)butter

public void reverseList()
{
   Node prev = null;
   Node temp = null;
   Node curr = head;
   while (curr.getNext() != null)
   {
      temp = curr;
      temp.setNext(prev);
      prev = curr;
      curr = curr.getNext();
   }
   head = prev;
}
 

Any suggestions would be appreciated,
Michael
[ March 15, 2003: Message edited by: michael bradly ]
[ March 15, 2003: Message edited by: michael bradly ]

[Barry Gaunt]

What's happening at the end of the list?
Have you stepped through this with a debugger?
Where's the Node class?
[ March 15, 2003: Message edited by: Barry Gaunt ]

[michael bradly]

Perhaps I'll try a debugger and see what happens. I've placed a ton of System.out lines, though....
I've checked the value of curr = curr.getNext(); in an if statement to see what curr is, and it is null.
This is what I've placed into the while loop and this is what I'm getting in return...

System.out.println("Entering reverseList method");
while (curr.getNext() != null)   
{      
   temp = curr;
   System.out.println("Temp is: " + (String)temp.getItem());      
   temp.setNext(prev);     
   prev = curr;
   System.out.println("Prev is: " + (String) prev.getItem());      
   curr = curr.getNext();
   if (curr == null)
   {
   System.out.println("Curr is getting a null value");
    }  
 } 

This is the output:
Entering the reverseList method
Temp is: milk
Prev is: milk
Curr is getting a null value
For some reason Curr is immediately getting a null value which is stumping me. I can print out all the items in the list without a problem.
Regards, Michael

Originally posted by Barry Gaunt:
What's happening at the end of the list?
Have you stepped through this with a debugger?
Where's the Node class?
[ March 15, 2003: Message edited by: Barry Gaunt ]

[John Smith]

Did you consider using standard API for this? Collections.reverse(list) will do the job. Why reinvent the wheel?
Eugene.

[Barry Gaunt]

Without seeing what Node.getNext() is doing, we can't tell what's getting returned into curr.
BTW. Have you checked that your input list is correctly linked?
Eugene: I'm guessing Michael's learning data structure concepts. It's one very good way to convince yourself to use Collection and Collections
[ March 15, 2003: Message edited by: Barry Gaunt ]

[michael bradly]

Yes, that would be simpler, however it isn't part of the instructions on my class assignment.

Originally posted by Eugene Kononov:
Did you consider using standard API for this? Collections.reverse(list) will do the job. Why reinvent the wheel?
Eugene.

[michael bradly]

Yes, good ol data structures..
Here is the Node class... Thus far the Node class has been doing what I've asked of it

public class Node 
{
  private Object item;
  private Node next;
  public Node(Object newItem) 
  {
    item = newItem;
    next = null;
  } // end constructor
  public Node(Object newItem, Node nextNode) 
  {
    item = newItem;
    next = nextNode;
  } // end constructor
  public void setItem(Object newItem) 
  {
    item = newItem;
  } // end setItem
  public Object getItem() 
  {
    return item;
  } // end getItem
  public void setNext(Node nextNode) 
  {
    next = nextNode;
  } // end setNext
  public Node getNext() 
  {
    return next;
  } // end getNext
} // end class Node

Originally posted by Barry Gaunt:
Without seeing what Node.getNext() is doing, we can't tell what's getting returned into curr.
BTW. Have you checked that your input list is correctly linked?
Eugene: I'm guessing Michael's learning data structure concepts. It's one very good way to convince yourself to use Collection and Collections
[ March 15, 2003: Message edited by: Barry Gaunt ]

[Barry Gaunt]

Looks like you have a situation like:
curr.next <- null; // because prev was null
// and temp is same as curr.
curr <- curr.next; // curr is now set to null
call getNext() through null pointer - Bang!
Cryptic I know, but you get the idea?
[ March 15, 2003: Message edited by: Barry Gaunt ]

[michael bradly]

Yowza, let me get out my Captain Cosmic decoder on that one So I take it that I am losing a reference there?
I guess what is confusing me is that I don't see where I am breaking the link from curr to curr.getNext()
Perhaps I need to reasses what I'm doing. My thoughts were along the lines that I could create a back reference i.e.
head->milk->eggs|null to null|milk<-eggs<-head
by using a temp Node that processed backwards along the way. So the idea behind temp getting curr is that I could setNext to prev which is null, then continue down the list with temp getting the Node prev references.
Does this at least sound like I'm on the right path?
Thanks for all the help, Michael

Originally posted by Barry Gaunt:
Looks like you have a situation like:
curr.next <- null; // because prev was null
// and temp is same as curr.
curr <- curr.next; // curr is now set to null
call getNext() through null pointer - Bang!
Cryptic I know, but you get the idea?
[ March 15, 2003: Message edited by: Barry Gaunt ]

[Ilja Preuss]

Originally posted by michael bradly:
I'm getting a null pointer and am wondering if I am losing a reference somewhere. I am trying to reverse the references in a list.
Assume the list had three items 1) milk 2) eggs 3)butter

public void reverseList()
{
   Node prev = null;
   Node temp = null;
   Node curr = head;
   while (curr.getNext() != null)
   {
      temp = curr;
      temp.setNext(prev);
 

This is where you set curr.next to null, because prev == null and temp == curr!

[Barry Gaunt]

I would recommend that you do not use null in your algorithm. Use a reference to head instead. If the reference to next (or previous) is to head then you know you are at the end (or front) of the list. An empty list is just head referencing itself in both next and previous directions.
You should get yourself some empty matchboxes, some pins and some coloured thread. Build yourself a list and play with it until the algorithm becomes clear. Then write the code. I would also recommend using BlueJ for such experimentation.
-Barry
[ March 16, 2003: Message edited by: Barry Gaunt ]

[John Smith]

Here is a little cheat, -- an implementation of the reverse() method in the Collections class. But it is also a good educational example that demonstrates how elegant a solution could be (this class was written by our friend Josh Bloch):

    public static void reverse(List l) {
        ListIterator fwd = l.listIterator(), rev = l.listIterator(l.size());
        for (int i=0, n=l.size()/2; i<n; i++) {
            Object tmp = fwd.next();
            fwd.set(rev.previous());
            rev.set(tmp);
        }
    }

Isn't this beautiful?
Eugene.

[michael bradly]

Sounds like good advise. If there is one thing I have available, it's plenty of match books.
I realized just prior to falling asleep that my whole concept was flawed. trying to convert head->milk..etc|null to null|milk..etc<-head doesn't work if I'm setting temp.setNext to null. I just end up with milk|null as a Node.
Well, I have plenty of work still to do, then.
Thanks for everyone's assistance. I think I have enough tools to wrap this up.
Regards, Michael

Originally posted by Barry Gaunt:
I would recommend that you do not use null in your algorithm. Use a reference to head instead. If the reference to next (or previous) is to head then you know you are at the end (or front) of the list. An empty list is just head referencing itself in both next and previous directions.
You should get yourself some empty matchboxes, some pins and some coloured thread. Build yourself a list and play with it until the algorithm becomes clear. Then write the code. I would also recommend using BlueJ for such experimentation.
-Barry
[ March 16, 2003: Message edited by: Barry Gaunt ]

[ March 16, 2003: Message edited by: michael bradly ]

[Barry Gaunt]

Originally posted by Eugene Kononov:

    public static void reverse(List l) {
        ListIterator fwd = l.listIterator(), rev = l.listIterator(l.size());
        for (int i=0, n=l.size()/2; i<n; i++) {
            Object tmp = fwd.next();
            fwd.set(rev.previous());
            rev.set(tmp);
        }
    }

Isn't this beautiful?
Eugene.[/QB]

Wouldn't get through CattleDrive !