实施通用单链表

Question

该网站的新功能。试图实现一个通用的SinglyLinkedList，即使存在节点并且delete方法返回false，当预期为true时，获取返回null。另外，当我决定以相反的顺序删除时，它的功能很好。寻找一组清新的眼睛，看看我缺少的东西。提前致谢。

public class SinglyLinkedList<T> { 

    private Node<T> h; // list header 

    public SinglyLinkedList() { 
     h = new <T> Node(); // dummy node 
     h.l = null; 
     h.next = null; 
    } 

    public boolean insert(T newNode) { 
     Node n = new Node(); 
     GenericNode node = (GenericNode) newNode; 
     if (node == null) // out of memory 
     { 
      return false; 
     } else { 
      n.next = h.next; 
      h.next = n; 
      n.l = (T) node.deepCopy(); 
      return true; 
     } 
    } 

    public GenericNode fetch(Object targetKey) { 
     Node p = h.next; 
     GenericNode node = (GenericNode) p.l; // this is where am I think there is a problem. Is this right? 
     while (p != null && !(node.compareTo(targetKey) == 0)) { 
      p = p.next; 
     } 
     if (p != null) { 
      return node.deepCopy(); 
     } else { 
      return null; 
     } 
    } 

    public boolean delete(Object targetKey) { 
     Node q = h; 
     Node p = h.next; 
     GenericNode node = (GenericNode)p.l;// I think is the problem 
     while (p != null && !(node.compareTo(targetKey) == 0)) { 
      q = p; 
      p = p.next; 
     } 
     if (p != null) { 
      q.next = p.next; 
      return true; 
     } else { 
      return false; 
     } 
    } 

    public boolean update(Object targetKey, T newNode) { 
     if (delete(targetKey) == false) { 
      return false; 
     } else if (insert(newNode) == false) { 
      return false; 
     } 
     return true; 
    } 

    public void showAll() { 
     Node p = h.next; 
     while (p != null) //continue to traverse the list 
     { 
      System.out.println(p.l.toString()); 
      p = p.next; 
     } 
    } 

    /** 
    * 
    * @param <T> 
    */ 
    public class Node <T> { 

     private T l; 
     private Node <T> next; 

     public <T> Node() { 
     } 
    }// end of inner class Node 
    } 
//end SinglyLinkedList outer class 

Answer 1

问题就出在这里（在fetch法）：

GenericNode node = (GenericNode) p.l; // this is where am I think there is a problem. Is this right? 
    while (p != null && !(node.compareTo(targetKey) == 0)) { 
     p = p.next; 
    } 

你也只是在进入循环之前assing node，只有改变环路内p值，所以node整个保持其初始值整个循环。您应该使用：

GenericNode node = null;  // define node before the loop in order to use it later 
    while (p != null) { 
     node = (GenericNode) p.l; // reset node value on each iteration 
     if (node.compareTo(targetKey) == 0) { 
      break; 
     } 
     p = p.next; 
    } 

正如你在delete，相同的修订将适用于具有相同的代码...