LinkedSet implementazione Java

Question

è stato chiesto di implementare un insieme collegato in Java. Qui di seguito è il mio tentativo, ha tutti i metodi che sono invitati a scrivere, ma il metodo remove chiama un'eccezione di puntatore nullo a colpo sicuro. Per quanto mi sforzassi non riesco a capirlo, tutto l'aiuto molto apprezzato.

import java.util.*;

class LinkedSet<T> {

 private static class Node<T> {

  private T item;
  private Node<T> next;

  Node(T item, Node<T> next) {

   this.item = item;
   this.next = next;
  }

 }


 private Node<T> head = null;
 private int numItems = 0;

 int size() {

  return (numItems);

 }

 public boolean add(T t) {

  if(contains(t)) return false;

  Node<T> newNode = new Node(t, null); //new node to be added

  if(numItems==0) {

   head = newNode;
   numItems++;
   return true;
  }

  Node<T> temp = head;

  while(temp.next != null) temp = temp.next;
  temp.next = newNode;
  numItems++;
  return true;

 }


 public boolean remove(T t) {

  if(numItems == 0) return false; //check for empty set
  //was tempted to use contains here but would have made it N^2 I think

  Node<T> p = head; //t if present
  Node<T> pPrev = null; //previous node to p

  while(p!=null && !equals(t, p.item)) {

   pPrev = p;
   p = p.next;

  }

  //t is present if node p!= null , node p != null ==> t in node p

  if(p==null) return false;
  else {

   pPrev.next = p.next; //null pointer
   numItems--;
   return true;
  }


 }

 public boolean contains(T t) {


  Node<T> temp = head;

  for(int i = 0; i < numItems; i++) {

   if(equals(temp.item, t)) return true;
   temp = temp.next;
  }

  return false;

 }

 private boolean equals(T t1, T t2) { //t1, t2 may be null

  if(t1!=null) return t1.equals(t2); //learn this
  else return t2 == null; //learn this

 }

 public static void main(String[] args) {

  LinkedSet<Integer> test = new LinkedSet<Integer>();

  test.add(1);
  test.add(2);
  test.add(3);

  for(int i = 0; i < 10; i ++) {

   System.out.println("Testing i = " + i + " - " + test.contains(i));
  }

  System.out.println(); System.out.println(); System.out.println();

  System.out.println(test.remove(1));


 }



}

Answer 1

Il punto evidente è che il primo elemento della lista non ha un elemento precedente. (Qualche lista implementazioni legate aggiungerà un collegamento fittizio per gestire questa situazione in modo più pulito.)

Answer 2

Guardate questa porzione di codice:

  Node<T> p = head; //t if present
  Node<T> pPrev = null; //previous node to p

  while(p!=null && !equals(t, p.item)) {

   pPrev = p;
   p = p.next;

  }

Se equals(t, head.item), allora pPrev == null quando si lascia il ciclo while e si otterrà un'eccezione di puntatore nullo in seguito.