Interfaccia Iterator

Question

Ho un incarico universitario che richiede l'implementazione di una classe interna che implementa l'interfaccia Iterator. L'iteratore funziona su una superclasse di elenco single-linked.

Attualmente la mia classe interna si presenta così:

private class ListIterator implements Iterator<V>{ 

    Node temp; 
    boolean nextCalled = false; 

    ListIterator(Node fo){ 
     this.temp = fo; 
    } 

    @Override 
    public boolean hasNext() { 
     if(temp != null){ 
      return true; 
     } 
     return false; 
    } 

    @Override 
    public V next() { 
     nextCalled = true; 
     return temp.getReprValue(); 
    } 

    @Override 
    public void remove() { 
     if(nextCalled && hasNext()){ 
      nextCalled = false; 
      removeElement(temp.getReprKey()); 
      temp = temp.getNext(); 
     } 

    } 

} 

Ora il mio problema è che il metodo hasNext() restituisce vero anche quando la lista è in realtà vuota. Tutto il resto sembra funzionare. Probabilmente ho trascurato un difetto logico da qualche parte, ma non riesco a trovarlo da solo.

Answer 1

Modificata l'implementazione in modo da riflettere ciò di cui ha bisogno il contratto Iterator. È necessario ricordare che è necessario essere in grado di scorrere tutti gli elementi della raccolta, ovvero, next() dovrebbe iniziare dal primo elemento e dopo ogni chiamata deve cambiare l'elemento successivo corrente nell'elemento successivo nell'elenco o generare un'eccezione se non ce n'è.

È utile leggere lo Iterator interface doc per capire come è necessario implementarlo e iniziare da lì.

private class ListIterator implements Iterator<V> { 
    private Node next; 
    private boolean alreadyDeleted = false; 

    ListIterator(Node node){ 
     this.next = node; 
    } 

    @Override 
    public boolean hasNext() { 
     // because next is the current element. We need to iterate over all the elements 
     // from the collection. 
     return next != null; 
    } 

    @Override 
    public V next() { 
     if (next == null) { 
      throw new NoSuchElementException(); 
     } 

     Node current = next; 

     this.next = current.getNext(); 
     this.alreadyDeleted = false; // it's better to try to elimate this state variable. You can try to do in another way, if yours removeElement returns something 

     return current; 
    } 

    @Override 
    public void remove() { 
     if (alreadyDeleted || next == null) { 
      throw new IllegalStateException(); 
     } 
     removeElement(next.getReprKey()); 
     this.alreadyRemoved = true; 
    } 

} 

Answer 2

È necessario tenere traccia di dove si trova nell'elenco, implementare un cursor o se i nodi nell'elenco collegato sono a conoscenza del proprio next, basta chiedere loro se hanno un elemento successivo. Quando il cursore è più grande, la lunghezza/il nodo non ha next si restituisce falso in hasNext().

Fai tutto questo nel tuo metodo hasNext(). Ricorda, è possibile che next() generi un'eccezione se hasNext() sarebbe stato falso - quindi è necessario assicurarsi che sia l'unica volta in cui genererà un'eccezione.

Poiché non conosco la struttura dati sottostante del tuo elenco, non posso dirti quale di questi sarà migliore.

Answer 3

hasNext restituisce true se il nodo corrente (temp) non è null.

Se l'implementazione dell'elenco collegato utilizza un nodo di intestazione, il costruttore riceve sempre fo!=null e hasNext restituirà true anche se l'elenco è vuoto. Dovresti considerare questo fatto nella tua implementazione.

Sulla base di codice, sembra che

ListIterator(Node fo){ 
    this.temp = fo.getNext(); 
} 

può fare il trucco (se header.getNext()==null per una lista vuota).

Answer 4

Per ridurre po 'di codice, e ne fanno un tocco più leggibile

• rinominare temp a next,
• uso notazione scorciatoia,
• probabilmente dovrebbe avere qualche concetto del nodo current,

che rende l'aggiornamento simile a:

private Node next; 
private Node current; //track deletion 

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

public Node getNext() { 
    if (hasNext()) { 
    current = next; 
    next = next.getNextNode(); 
    } 
    return current; 
} 

l'eliminazione potrebbe impostare corrente su null. Non abbiamo bisogno di una bandiera (supponendo che non stiamo facendo nulla se una persona cancella prima di chiamare il primo getNext(). Diamine, se davvero vogliamo andare per l'oro, avere remove() gettare un IllegalStateException se current == null.