Удалить узлы с заданным ключом в связанном списке

Question

Мне сложно определить, что не так с моим кодом. Я должен удалить все узлы, содержащие конкретный элемент. В тестовом коде ниже моего кода мне требуется удалить все элементы «в» в предложении «быть или не быть», а затем вернуть голову, которая в этом случае «будет». Может ли кто-нибудь указать на проблему с моим кодом? Спасибо.

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 Часть кодекса < --Я извиниться, я не ставил эту часть кода. Спасибо тем, кто помог мне до сих пор.

/** 
* @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; 
    } 
} 

Тест Код:

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)); 
     } 
} 

Это ошибка, я получаю при запуске моего кода в Eclipse, с помощью теста JUnit. Это ошибка теста testRemoveNodes2. Для теста testRemoveNodes1 нет ошибки.

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

Answer 1

Единственный способ я вижу, ваша программа не будет работать, если в сравнение curr.data и item использованием == и != не работает, как ожидалось. Это вполне возможно, поскольку сравнение строк с использованием этих операторов не рекомендуется, а не обычная практика, и если вы действительно не знаете, что делаете (оптимизация), они не будут делать то, что вы ожидали.

Например, если в вашей реализации ListStackQueue.buildList вы создаете значения полей узлов data, используя new String(...). Если вы создадите значения таким образом, то s1 == s2 никогда не будет истинным для двух строк, даже если их значения одинаковы.

Bottomline есть, не сравнить строки с помощью == и !=, переписать реализацию использовать .equals вместо , а затем он должен работать. Конечно, когда вы это делаете, перед вызовом .equals на объект вам необходимо сначала убедиться, что он не является нулевым, иначе вы получите NullPointerException.

Предполагая, что нет узлов, где data поле является null, это должно работать:

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; 

Я также упал некоторые избыточные условия.

Если вы хотите, чтобы null значения Node.data, то !curr.data.equals(item) выше будет немного сложнее, заменить его:

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