頭と尾の参照を使用した単一リンクリストの削除要素

Question

私は自分のプロジェクトに単独でリンクされたリストを実装する必要があり、removeメソッドを動作させるのに問題があります。私はここで答えを探しましたが、テールリファレンスを組み込んだものは見つかりませんでした。私のプロジェクトでは、リスト内に先頭と末尾の参照が必要で、必要に応じて更新する必要があります。これは私のクラスとremoveメソッドです：

public class BasicLinkedList<T> implements Iterable<T> { 
public int size; 

protected class Node { 
    protected T data; 
    protected Node next; 

    protected Node(T data) { 
     this.data = data; 
     next = null; 
    } 
} 

protected Node head; 
protected Node tail; 

public BasicLinkedList() { 
    head = tail = null; 
} 

public BasicLinkedList<T> addToEnd(T data) { 
    Node n = new Node(data); 
    Node curr = head; 
    //Check to see if the list is empty 
    if (head == null) { 
     head = n; 
     tail = head; 
    } else { 
     while (curr.next != null) { 
      curr = curr.next; 
     } 
     curr.next = n; 
     tail = n; 

    } 
    size++; 
    return this; 
} 

public BasicLinkedList<T> addToFront(T data) { 
    Node n = new Node(data); 
    if(head == null){ 
     head = n; 
     tail = n; 
    } 
    n.next = head; 
    head = n; 
    size++; 
    return this; 
} 

public T getFirst() { 
    if (head == null) { 
     return null; 
    } 
    return head.data; 
} 

public T getLast() { 
    if(tail == null){ 
     return null; 
    } 
    return tail.data; 
} 

public int getSize() { 
    return size; 
} 

public T retrieveFirstElement() { 
    // Check to see if the list is empty 
    if (head == null) { 
     return null; 
    } 
    Node firstElement = head; 
    Node curr = head.next; 
    head = curr; 
    size--; 
    return firstElement.data; 

} 

public T retrieveLastElement() { 
    Node curr = head; 
    Node prev = head; 
    // Check to see if the list is empty 
    if (head == null) { 
     return null; 
    } else { 
     // If there's only one element in the list 
     if (head.next == null) { 
      curr = head; 
      head = null; 
     } else { 
      while (curr.next != null) { 
       prev = curr; 
       curr = curr.next; 
      } 

      tail = prev; 
      tail.next = null; 
     } 
    } 
    size--; 
    return curr.data; 
} 

public void remove(T targetData, Comparator<T> comparator) { 
    Node prev = null, curr = head; 
    while (curr != null) { 
     if (comparator.compare(curr.data, targetData) == 0) { 
      //Check to see if we need to remove the very first element 
      if (curr == head) { 
       head = head.next; 
       curr = head; 
      } 
      //Check to see if we need to remove the last element, in which case update the tail 
      else if(curr == tail){ 
       curr = null; 
       tail = prev; 
       prev.next = null; 
      } 
      //If anywhere else in the list 
      else { 
       prev.next = curr.next; 
       curr = curr.next; 
      } 
      size--; 
     } else { 
      prev = curr; 
      curr = curr.next; 
     } 
    } 
} 

public Iterator<T> iterator() { 
    return new Iterator<T>() { 

     Node current = head; 

     @Override 
     public boolean hasNext() { 
      return current != null; 
     } 

     @Override 
     public T next() { 
      if(hasNext()){ 
       T data = current.data; 
       current = current.next; 
       return data; 
      } 
      return null; 
     } 

     @Override 
     public void remove(){ 
      throw new UnsupportedOperationException("Remove not implemented."); 
     } 

    }; 
} 

}

私はこの方法の多くの反復を経ていると私はヘッド基準、尾の参照を失うか、Iのいずれかたびは削除しないでください要素と私はそれを把握しようと困惑しています。ここで参考になるのは私がそれを実行しているテストです。私はテストにも失敗しない、それは単に失敗のトレースを言う。

public void testRemove(){ 
      BasicLinkedList<String> basicList = new BasicLinkedList<String>(); 
    basicList.addToEnd("Blue"); 
    basicList.addToEnd("Red"); 
    basicList.addToEnd("Magenta"); 
    //Blue -> Red -> Magenta -> null 
    basicList.remove("Red", String.CASE_INSENSITIVE_ORDER); 
    //Blue -> Magenta -> null 
    assertTrue(basicList.getFirst().equals("Blue")); 
    //getLast() returns the tail node 
    assertTrue(basicList.getLast().equals("Magenta")); 
    } 

編集：削除メソッドは、リストからターゲットデータのすべてのインスタンスを削除する必要があります。

Answer 1

1つのバグしか表示されません。あなたのリストは、最初に以下の方法を使用すると、次の自分自身を指し、一つのノードを持つループが発生します空の場合：

public BasicLinkedList<T> addToFront(T data) { 
    Node n = new Node(data); 
    // The list was empty so this if is true 
    if(head == null){ 
     head = n; 
     tail = n; 
    } 
    n.next = head; 
    // now head == n and n.next == head == n so you've got a circle 
    head = n; 
    size++; 
    return this; 
} 

あなたはそうのようにこの問題を解決することができます。

public BasicLinkedList<T> addToFront(T data) { 
    Node n = new Node(data); 
    if(head == null){ 
     tail = n; 
    } 
    n.next = head; 
    head = n; 
    size++; 
    return this; 
}