linked list adding an element to the end of the list

Question

In a linked List when implementing a method to insert an item at the end of the list this was the code that I thought of,

public void insertEnd(Object item){

        SListNode current=head;
        while(current.next!=null){
            current=current.next;
        }
        current.next=new SListNode(item);

        size--;
    }

But since it did not work I checked from a book and realized that I had to add the line

current=current.next; 

just after the while loop again so that the code becomes

public void insertEnd(Object item){

        SListNode current=head;
        while(current.next!=null){
            current=current.next;
        }
        current.next=new SListNode(item);
        current=current.next;
        size--;
    }

Why is it necessary to add that line (line 7 in new code) because current.next points to the newly created node by the line current.next=new SListNode(item);

My second question is why do I have to consider a separate case when the list is empty?I get a null pointer exception error.

Can some one please explain it by a graph

Answer 1

Without line current=current.next; you will stuck forever in while loop, and creation of new Node would never happen, at first iteration(first inserting it would raise an exception)

public class Test2 {

SListNode head;

public void insertEnd(String item) {
    SListNode current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = new SListNode(item);
    // this line does not have any meaning, because it is out of while loop scope
    current = current.next;

}

public static void main(String[] args) {
    Test2 test2 = new Test2();
    test2.test();

}

private void test(){
    // keeping head reference
    head = new SListNode("1");
    insertEnd("2");
    insertEnd("3");
    insertEnd("4");

    System.out.println("HEAD "+head.item);
    SListNode init = head.next;
    while ( init != null ){
        System.out.println("ADDED "+init.item);
        init = init.next;
    }
  }

class SListNode {
    SListNode next;
    String item;
    public SListNode(String item) {
        this.item = item;
    }
}

}

Ok here is a reconstructed code(simplified). With that line or without program is working.

Answer 2

Your algorithm to add at the end looks fine at first glance so you should check that it isn't working right.

For the other problem though it's simple as if the list is empty then head is null.

That means SListNode current=head; sets current to null, which then fails as soon as you try and access current.

Answer 3

This piece of code uses your while loop to step through your list of potentially many nodes.

while(current.next!=null){
   current=current.next;
}

It stops at a list node where current.next ==null.

At this point you can add a new node calling

current.next = new SListNode(item);

The second current=current.next;, your book gets you to add, does nothing for your method. It moves your current pointer to the node you just created, but no work is done with (or required of) it.

The null pointer exception:-- When the list is empty, you do not have a head. Meaning any call of head.next is actually a call to null.next, which is a nonsense. Start your method with a check for the empty state:

if(head == null){
  head = new SlinkNode(item);
  size = 1;
  return;
}

Note that the head is just a standard node and it holds your first item. The size is set to 1 and you return from the method as there is no more work to do.

Also note that the size-- at the end of your code is decrementing the size, not incrementing it when you add new nodes. It should be size++.

Answer 4

It's a good Question. If there is no elements in the list then the head will be null value. while you try to access current.next it actually means null.next. Because of the null value you are getting the error. You can check for null and add directly.

public void insertEnd(Object item){
if(head!=null)
{
    SListNode current=head;
    while(current.next!=null)
    {
        current=current.next;
    }
    current.next=new SListNode(item);
    size++;
}
else
{
    current=new SListNode(item);
}
}