Creating a getLast method for Linked Lists

Question

I'm trying to hand code a getLast method in Java. I know what I have to do, I'm just having trouble coding it. What I need to do is traverse the linked list until p.link points to null, then I can add to the end of the list. Here's what I have so far:

class MyLinkedList 
{
   private class Node           
   {
      private Node link;
      private int x;
   }
   //----------------------------------
   private Node first = null;    
   //----------------------------------
   public void addFirst(int d)
   {
      Node newNode = new Node(); 
      newNode.x = d;            
      newNode.link = first;      
      first = newNode;           
   } 

   public void addLast(int q)
   {
      Node newNode = new Node();
      newNode.x = q;
      newNode.link = null;  //points to null because nothing should follow it
   //----------------------------------
   public void traverse()
   {
      Node p = first;
      while (p != null)            
      {
         System.out.println(p.x);  
         p = p.link;               
      }
   }
}
//==============================================
class C15h1  
{
   public static void main(String[] args)
   {
      MyLinkedList list = new MyLinkedList();
      list.addLast(4);
      list.addLast(5);
     list.addLast(6);
      list.addFirst(1);
      list.addFirst(2);
      list.addFirst(3);
      System.out.println("Numbers on list");
      list.traverse();
   }
}

Answer 1

I would keep track of the last node:

class MyLinkedList 
{
   private class Node           
   {
        private Node link;
        private int x;
   }
    //----------------------------------
    private Node first = null;    
    private Node last = null;    
    //----------------------------------

    public void addFirst(int d)
    {
        Node newNode = new Node(); 
        newNode.x = d;            
        newNode.link = first;      
        first = newNode;
        if(last == null)
            last = newNode;           
    } 

    public void addLast(int q)
    {
        Node newNode = new Node();
        newNode.x = q;
        newNode.link = null;  //points to null because nothing should follow it
        if(last != null)
            last.link = newNode;
        last = newNode;
        if(first == null) // This is the first node
            first = newNode;
    }

    //----------------------------------
    public void traverse()
    {
        Node p = first;
        while (p != null)            
        {
            System.out.println(p.x);  
            p = p.link;               
        }
    }

    public int getLast()
    {
        if(last != null)
            return last.q;
        return -1;
    }
}

Answer 2

this may be what you wanted?

public Node getLast()
{
    Node lastNode = first;
    Node next = first.link;

    while (next != null)
    { 
         lastNode = next;
         next = next.link; 
    }

    return lastNode;
}

Answer 3

The problem in your current code is in the traverse() method. It loops until p == null which means that you stop when p "fell" out of the list. What you want is to stop one step before that such p is pointing at the very last item of the list. To do that you simply need to change the condition from while (p != null) to while (p.link != null).

Here's how addLast() should look like:

public void addLast(int q)
{
   Node newNode = new Node();
   newNode.x = q;
   newNode.link = null;  //points to null because nothing should follow it

   Node p = first;
   while (p.link != null) {
      p = p.link;               
   }
   p.link = newNode;
}

Answer 4

iterate till you get last node using while loop and once foinds last node return it..

 public Node getLast(){
    Node p = first;
          while (p.link != null)            
          { 
             p = p.link;               
          }
    return p;
    }

Answer 5

You need to loop through your list till the end. (Just like as you mentioned. 'until p.link points to null,')

You could do something like this:

public void addLast(int q) {
    Node newNode = new Node();
    newNode.x = q;
    newNode.link = null;
    if (first == null) {
        first = newNode;
    } else {
        Node lastNode = first;
        while (lastNode != null && lastNode.link != null) {
            lastNode = lastNode.link;
        }
        lastNode.link = newNode;
    }
}