Как удалить элемент из связанного списка

Question

У меня есть класс сумки был дан мне, как выглядит следующим образом:

import java.util.Iterator; 
import java.util.NoSuchElementException; 

public class Bag<Item> implements Iterable<Item> { 

private int N;    // number of elements in bag 
private Node<Item> first; // beginning of bag 

// helper linked list class 
private class Node<Item> { 
    private Item item; 
    private Node<Item> next; 
} 

/** 
* Initializes an empty bag. 
*/ 
public Bag() { 
    first = null; 
    N = 0; 
} 

/** 
* Is this bag empty? 
* @return true if this bag is empty; false otherwise 
*/ 
public boolean isEmpty() { 
    return first == null; 
} 

/** 
* Returns the number of items in this bag. 
* @return the number of items in this bag 
*/ 
public int size() { 
    return N; 
} 

/** 
* Adds the item to this bag. 
* @param item the item to add to this bag 
*/ 
public void add(Item item) { 
    Node<Item> oldfirst = first; 
    first = new Node<Item>(); 
    first.item = item; 
    first.next = oldfirst; 
    N++; 
} 

public void remove(Item item){ 
    // currentNode is the reference to the first node in the list and to the Item 
    Node<Item> currentNode = first; 
    // if items equals the first node in the list, then first = currentNode.next which will make the first item 
    Node<Item> temp = currentNode; 
    while(temp.next != null){ 
     temp = currentNode; 
     if(item.equals(currentNode.item)){ 
      currentNode = currentNode.next; 
      temp.next = currentNode; 
      break; 
     }else{ 
      currentNode = currentNode.next; 
     } 
    } 
    N--; 
} 

/** 
* Returns an iterator that iterates over the items in the bag in arbitrary order. 
* @return an iterator that iterates over the items in the bag in arbitrary order 
*/ 
public ListIterator<Item> iterator() { 
    return new ListIterator<Item>(first); 
} 

// an iterator, doesn't implement remove() since it's optional 
private class ListIterator<Item> implements Iterator<Item> { 
    private Node<Item> current; 

    public ListIterator(Node<Item> first) { 
     current = first; 
    } 

    public boolean hasNext() { return current != null;      } 
    public void remove()  { throw new UnsupportedOperationException(); } 

    public Item next() { 
     if (!hasNext()) throw new NoSuchElementException(); 
     Item item = current.item; 
     current = current.next; 
     return item; 
    } 
} 

Мне нужно реализовать метод удалить и код, написанный для него моего. Это не работает, и мне было интересно, может ли кто-нибудь сказать мне, почему и как его исправить?

Answer 1

Пара проблем с вашим методом удаления.

• Вы должны только уменьшить N, если вы на самом деле удалить узел
• Если мешок содержит повторяющиеся элементы, если удалить() метод удалить все дубликаты этого товара? Я бы так и ожидал.
• Вам необходимо обработать случай, когда вы удаляете первый узел и обновляете свою первую ссылку.
• Если вы не удаляете первый узел, вам необходимо обновить предыдущий узел, чтобы указать на следующий узел после удаляемого узла.

Принесите все это вместе:

public void remove(Item item){ 
    Node<Item> currentNode = first; 
    Node<Item> previousNode = null; 
    while(currentNode != null){ 
     if(item.equals(currentNode.item)){ 
      if(previousNode == null) { 
       first = currentNode.next; 
      } 
      else { 
       previousNode.next = currentNode.next; 
      } 
      N--; 
     } 
     else { 
      previousNode = currentNode; 
     } 
     currentNode = currentNode.next; 
    } 
}