Interfejs Iteratora

Question

Mam przypisanie Uniwersytetu, który wymaga mnie do wdrożenia wewnętrznej klasy, która implementuje interfejs Iterator. Iterator działa na superklasie listy pojedynczego łącza.

Obecnie mój wewnętrzny klasy wygląda następująco:

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(); 
     } 

    } 

} 

Teraz moim problemem jest to, że metoda hasNext() zwraca wartość true, nawet gdy lista jest rzeczywiście pusty. Wszystko inne wydaje się działać. Prawdopodobnie przeoczyłem błąd logiczny, ale nie mogę go znaleźć.

Answer 1

Zmieniono implementację tak, aby odzwierciedlała to, czego potrzebuje umowa Iterator. Musisz pamiętać, że musisz mieć możliwość iteracji nad wszystkimi elementami kolekcji, tzn. next() powinien rozpoczynać się od pierwszego elementu i po każdym wywołaniu musi zmienić bieżący następny element na następny element na liście lub rzucić wyjątek jeśli nie ma.

Dobrze jest przeczytać Iterator interface doc, aby znaleźć sposób, w jaki trzeba go wdrożyć i zacząć od tego.

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

Musisz śledzić, gdzie jesteś na liście, zaimplementować cursor, lub jeśli twoje węzły z połączonej listy są świadome swoich next, zapytaj ich, czy mają następny element. Gdy kursor jest większy niż długość/Twój węzeł nie ma wartości next, zwracasz wartość false w hasNext().

Wykonaj wszystkie te czynności w swojej metodzie hasNext(). Pamiętaj, że w porządku, aby next() rzucił wyjątek, jeśli hasNext() byłby fałszywy - musisz więc upewnić się, że to jedyny moment, w którym wygeneruje wyjątek.

Ponieważ nie znam podstawowej struktury danych na liście, nie mogę powiedzieć, która z nich będzie lepsza.

Answer 3

hasNext zwraca wartość true, jeśli bieżący węzeł (temp) nie jest null.

Jeśli implementacja listy powiązanej używa węzła nagłówka, to konstruktor zawsze otrzymuje fo!=null, a hasNext zwraca true, mimo że lista jest pusta. Powinieneś rozważyć ten fakt w swojej implementacji.

oparciu o kodzie, wydaje się, że

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

może załatwić sprawę (jeśli header.getNext()==null dla pustej listy).

Answer 4

Aby zmniejszyć trochę kodu i uczynić go trochę bardziej czytelny

• przemianować temp do next, notacja skrót
• używanie,
• prawdopodobnie powinien mieć jakąś koncepcję węzła current,

co powoduje, że aktualizacja wygląda następująco:

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; 
} 

usunięcie może ustawić aktualny na null. Nie potrzebujemy flagi (zakładając, że nic nam nie doleci, jeśli ktoś usunie przed wywołaniem pierwszego numeru getNext(). Heck, jeśli naprawdę chcemy zdobyć złoto, prześlijmy IllegalStateException, jeśli current == null.