Linked List in java

Question

I need to write a very simple 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 elements are equal (compared using equals() ), it removes duplicate nodes so that only one consecutive copy remains. Therefore, after the completion of the procedure, no two consecutive elements in this list are equal.

After squish() executed, the list may be shorter than when squish() run. No additional items are added to compensate for their removal.

For example, if the input list is [ 0 0 0 0 1 1 0 0 0 3 3 3 1 1 0 ] , then the result 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 basic task for executing 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 see that the method works fine ... only at the end of the list does it display a pointer to a null exception. Could 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 what recursion specialists like, and although most professionals don't use recursion, I set up the method this way.

Line 1 - init, you assign a pointer that will move through the list to the top of the linked list.

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

Line 2 is the base. If we have only one item in the list, you have nothing to do.

Line 3 is induction, if we point to a node, we examine the node in the neighborhood. If they are of equal importance, we can remove the node in the neighborhood.

Line 4 is another line 3, we looked at the node next door and saw that it is not equal. Therefore, we move the list.

This can be a useful exercise to go through the test data provided in the question manually, and then add a few System.out.println to my example to make sure you are right. I just had to do it today with some kind of complex 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 refers to 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 this, just change the condition:

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

Thus, the expression current.item.equals(current.next.item) will only be executed if current.next !=null true ( short circuit rating ), i.e. when it is safe for it.

Also, I think you can discard this first if . Take a look at @Pete's answer 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 , since current is the last item in the list and actually has no next item.

EDIT

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

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

Well, you just have to replace these two conditions with each other: the first check current.next not null and only then equates current and next :

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

By the way, you still get NPE in the line if(!current.item.equals(current.next.item)) when there is only one element in your list. To fix this, you can, for example, simply check to see if head.next == null . If so, do not start the while first.