Linked list in java

Question

i have to write a very easy method for a linked list class but i am having some problems. This method, called squish(), takes this list and, wherever two or more consecutive items are equal (compared using equals()), it removes duplicate nodes so that only one consecutive copy remains. Hence, no two consecutive items in this list are equal upon completion of the procedure.

After squish() executes, the list may well be shorter than when squish() began. No extra items are added to make up for those removed.

For example, if the input list is [ 0 0 0 0 1 1 0 0 0 3 3 3 1 1 0 ], the output list is [ 0 1 0 3 1 0 ].

This is my method:

public void squish() {
 SListNode current = head;
 boolean end =false;

  while(end == false )
    {


      if(!current.item.equals(current.next.item))
          current=current.next;
      else
      {
          while(current.item.equals(current.next.item) && current.next !=null)
              current.next=current.next.next;
          current=current.next;

      }
    if (current==null)
        end=true;
    }


      }

and this is a small main to execute the code.

public class main {
public static void main(String args[])
{



    int[] test6 = {6, 6, 6, 6, 6, 3, 6, 3, 6, 3, 3, 3, 3, 3, 3};
    SList list6 = new SList();
    for (int i = 0; i < test6.length; i++) {
      list6.insertEnd(new Integer(test6[i]));
    }
    System.out.println("squishing " + list6.toString() + ":");
    list6.squish();
    String result = list6.toString();
    System.out.println(result);


    int[] test5 = {3, 7, 7, 7, 4, 5, 5, 2, 0, 8, 8, 8, 8, 5};
    SList list5 = new SList();
    for (int i = 0; i < test5.length; i++) {
      list5.insertEnd(new Integer(test5[i]));
    }

    System.out.println("squishing " + list5.toString() + ":");
    list5.squish();
    result = list5.toString();
    System.out.println(result);

}

}

Debugging the code i can see that the method work fine..only at the end of the list he trhows a null exception pointer. Can you help me? thanks

Answer 1

I would do it like this:

public void squish() {
    SListNode current = head; //1

    if(current = null) return;  //1a

    while(current.next != null) { //2
       if(current.item.equals(currennt.next.item))
          current.next = current.next.next;  //3
       else 
          current = current.next;  //4
    }
}

This is the kind of thing that profs like to assign for recursion, and while most pros don't use recursion I have set up the method that way.

Line 1 is init, you assign the pointer that will traverse the list to the start of the linked list.

Line 1a if there are no elements in the list, then we return.

Line 2 is the base case. If we only have one element in the list then there is nothing to do.

Line 3 is the induction if we are pointing at a node, we examine the node next door. If they have an equal value, then we can remove the node next door.

Line 4 is the else of line 3, we have looked at the node next door, and sees that it is not equal. Therefore we traverse the list.

It might be a useful exercise to traverse the test data provided in the question by hand, then add some System.out.println's to my example to see if you are correct. I just had to do that today with some tricky code to figure out what was going on.

Answer 2

The problem is in this line:

while(current.item.equals(current.next.item) && current.next !=null)

Here, the first part of the condition accesses current.next.item, even if current.next is null, since the second part of the condition (current.next !=null) is checked after the first (and only if the first evaluates to true, see below). To fix it, just reverse the condition:

while(current.next !=null && current.item.equals(current.next.item))

This way, the expression current.item.equals(current.next.item) will only be executed if current.next !=null is true (short-circuit evaluation), i.e., when it's safe to do so.

Also, I think you can drop that first if statement. Take a look at @Pete's answer for how to simplify the method.

Answer 3

When the line if(!current.item.equals(current.next.item)) is executed in the last iteration, current.next points to null as current is the last item in the list and actually has no next item.

EDIT

In your comment now I see you get the NullPointerException in the line

while(current.item.equals(current.next.item) && current.next !=null)

Well, you should just replace those two conditions with each other: first validate current.next isn't null and only then equate current and next:

while(current.next !=null && current.item.equals(current.next.item))

BTW, you'd still get NPE in the line if(!current.item.equals(current.next.item)) when your list has only one element. To fix that you can, for instance, just check if head.next == null. If so, don't start the while loop in the first place.