Remove nodes with given key in linked list

Question

I'm having a hard time figuring out what is wrong with my code. I'm suppose to remove all nodes containing the specific item. In the test code below my code, it requires me to remove all the items "to" in the sentence "to be or not to be" and then return the head, which in this case is "be". Can someone please point out the problem with my code? Thank you.

package edu.csc130.assignment;
import java.util.LinkedList;

public class ListStackQueue {
/**
 * @param head the head of the input linked list
 * @param item the given value
 * @return the head of the linked list with nodes contains the given value removed
 * Assume for any node in the  linked list, node.item cannot be null
 */
  public static Node<String> removeNodes(Node<String> head, String item) {
    Node<String> curr = head;
    Node<String> prev = null;

    if (head == null) {
        System.out.println("list is empty");
    } else {
        while (curr != null) {
            if (curr.data != item) {
                prev = curr; 
                curr = curr.next; 
            } else if (curr == head && curr.data == item) {
                head = head.next; 
                curr = curr.next; 
            } else if (curr != head && curr.next != null && curr.data == item) {
                prev.next = curr.next; 
                curr = curr.next; 
            } else {
                curr.next = null; 
            }
        }   
    }

    return head;
  }
}

BuildList Part of Code <--I apologize, I did not put up this part of the code. Thanks to those who have helped me so far.

/**
 * @param items input array
 * @return the first node of the linked list build from the input array
 */
public static <E> Node<E>  buildList(E[] items) {
    Node<E> head = null;
    if (items!=null && items.length>0) {
        head = new Node<E> (items[0], null);
        Node<E> tail = head;
        for (int i=1; i<items.length; i++) {
            tail.next = new Node<E>(items[i], null);
            tail = tail.next;
        }
    }
    return head;
}

/**
 * @param head the first node of the linked list
 * @return the length of the linked list
 */
public static <E> int getLength(Node<E> head) {
    int length = 0;
    Node<E> node = head;
    while (node!=null) {
        length++;
        node = node.next;
    }
    return length;
}

public static <E> E get(Node<E> head, int index) {
    E item = null;
    Node<E> node = head;
    for (int i=0; i<index; i++) {
        if (node != null) {
            node = node.next;
        } else {
            break;
        }
    }
    if (node!=null) {
        item = node.item;
    }
    return item;
}

public static class Node<E> {
    public Object data;

    public String data();
    E item;
    Node<E> next;

    public Node(E item) {
        this.item = item;
        this.next = null;
    }

    public Node(E item, Node<E> next) {
        this.item = item;
        this.next = next;
    }
}

The test code:

package edu.csc130.assignment;
import org.junit.Assert;
import org.junit.Test;

import edu.csc130.assignment.ListStackQueue.Node;

public class ListStackQueueTest {

  @Test
  public void testRemoveNodes1() {
    Node<String> head = ListStackQueue.buildList(null);
    ListStackQueue.removeNodes(head, "to");
    Assert.assertNull(head);
  }

  @Test
  public void testRemoveNodes2() {
    String[] sentence = {"to", "be", "or", "not", "to", "be"};
    Node<String> head = ListStackQueue.buildList(sentence);
    head = ListStackQueue.removeNodes(head, "to");
    Assert.assertEquals(4, ListStackQueue.getLength(head));
    Assert.assertEquals("be", ListStackQueue.get(head, 0));
    Assert.assertEquals("or", ListStackQueue.get(head, 1));
    Assert.assertEquals("not", ListStackQueue.get(head, 2));
    Assert.assertEquals("be", ListStackQueue.get(head, 3));
  } 

  @Test
  public void testRemoveNodes3() {
    String[] sentence = {"to", "be", "or", "not", "to", "be"};
    Node<String> head = ListStackQueue.buildList(sentence);
    head = ListStackQueue.removeNodes(head, "be");
    Assert.assertEquals(4, ListStackQueue.getLength(head));
    Assert.assertEquals("to", ListStackQueue.get(head, 0));
    Assert.assertEquals("or", ListStackQueue.get(head, 1));
    Assert.assertEquals("not", ListStackQueue.get(head, 2));
    Assert.assertEquals("to", ListStackQueue.get(head, 3));
  }     

  @Test
  public void testRemoveNodes4() {
        String[] sentence = {"to", "be", "or", "not", "to", "be"};
        Node<String> head = ListStackQueue.buildList(sentence);
        head = ListStackQueue.removeNodes(head, "or");
        Assert.assertEquals(5, ListStackQueue.getLength(head));
        Assert.assertEquals("to", ListStackQueue.get(head, 0));
        Assert.assertEquals("be", ListStackQueue.get(head, 1));
        Assert.assertEquals("not", ListStackQueue.get(head, 2));
        Assert.assertEquals("to", ListStackQueue.get(head, 3));
        Assert.assertEquals("be", ListStackQueue.get(head, 4));
      }
}

This is the error I'm getting when running my code in Eclipse with JUnit test. This is the error for the testRemoveNodes2 test. There is no error for testRemoveNodes1 test.

java.lang.AssertionError: expected:<4> but was:<6>

Answer 1

The only way I see your program wouldn't work is if the comparisons of curr.data and item using == and != are not working as expected. Which is entirely possible, as comparing strings using these operators is not recommended, not a common practice, and unless you really know what you're doing (optimization), they will not do what you expected.

For example, if in your implementation of ListStackQueue.buildList you create the values of the data field of nodes using new String(...). If you create the values that way, then s1 == s2 will never be true for two strings, even if their values are the same.

The bottomline is, don't compare strings using == and !=, rewrite your implementation to use .equals instead, and then it should work. Of course, when you do that, before calling .equals on an object, you need to first verify that it's not null, otherwise you'll get a NullPointerException.

Assuming that there are no nodes where the data field is null, this should work:

if (head == null) {
    System.out.println("list is empty");
} else {
    while (curr != null) {
        if (!curr.data.equals(item)) {
            prev = curr; 
            curr = curr.next; 
        } else if (curr == head) {
            head = head.next; 
            curr = curr.next; 
        } else if (curr != head && curr.next != null) {
            prev.next = curr.next; 
            curr = curr.next; 
        } else {
            curr.next = null; 
        }
    }   
}

return head;

I also dropped some redundant conditions.

If you want to allow null values for Node.data, then the !curr.data.equals(item) above will be a bit more complicated, replace it with:

        if (curr.data == null && item != null || curr.data != null && !curr.data.equals(item)) {