LinkedSet implementazione Java
-
25-09-2019 - |
Domanda
è 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));
}
}
Soluzione
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.)
Altri suggerimenti
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.
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow