LinkedSet Java Implementación
-
25-09-2019 - |
Pregunta
Se nos ha pedido poner en práctica un conjunto vinculado en Java. A continuación es mi intento, tiene todos los métodos que les pide que escriban, pero el método remove llama a una excepción de puntero nulo y sin fallar. Mucho que lo intentaba no puedo parecer a la figura hacia fuera, cualquier ayuda muy apreciada.
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));
}
}
Solución
El punto obvio es que el primer elemento en la lista no tiene un elemento anterior. (Algunas implementaciones lista enlazada añadirán un enlace ficticio para manejar esto de forma más limpia.)
Otros consejos
Mira esta parte del código:
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;
}
Si equals(t, head.item)
, entonces pPrev == null
cuando salga del bucle while y obtendrá una excepción de puntero nulo después.
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow