java链接集实现

Question

我们被要求在 java 中实现一个链接集。下面是我的尝试，它具有我们要求编写的所有方法，但是方法remove调用空指针异常不会失败。尽我所能，我似乎无法弄清楚，非常感谢任何帮助。

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

明显的一点是列表中的第一个元素没有前一个元素。 （一些链表实现会添加一个虚拟链接来更干净地处理这个问题。）

Answer 2

看一下这部分代码：

  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循环时，你会得到一个null稍后指针异常。