LinkedSet的Java实现
-
25-09-2019 - |
题
我们一直要求实现一组链接在Java中。下面是我的尝试,它拥有所有我们被要求写的方法,但该方法删除通话,而不能空指针异常。我尝试过,我可能似乎无法弄清楚,任何帮助非常感谢。
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));
}
}
解决方案
在明显的一点是,在列表中的第一个元素不具有前一个元素。 (一些链表实现将添加一个虚设链接到更清洁处理这一点。)
其他提示
看代码的这一部分:
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;
}
如果equals(t, head.item)
,然后pPrev == null
当你离开while循环,以后你会得到一个空指针异常。
不隶属于 StackOverflow