Java Iterator для кругового связанного списка

Я создал класс CircularLinkedList вместо использования класса util LinkedList. Задача основана на задаче Иосифа, согласно которой для круга из 20 человек каждый 12-й человек должен быть убит, пока не будет определено, в какой позиции останется стоять выживший (используя итератор). Я не понимаю, как я могу использовать итератор с этой проблемой, поскольку я использую свой собственный класс вместо LinkedList, у которого уже есть метод iterator(), чтобы я мог объявить итератор следующим образом:

Iterator<E> iter = cll.iterator();

Я понятия не имею, как бы я написал свой собственный метод Iterator, и я чувствую, что должен перестать думать об этом. Любая помощь приветствуется! Я могу опубликовать свой код, если он прояснит что-то, что я забыл упомянуть.

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

Класс Itr (Итератор)

import java.util.Iterator;

public class Itr<E> extends CircularLinkedList<E> implements Iterator<E>
{

  /** the size of the list */
  private int size = 0;
  /** for the hasNext() method for Iterator */
  private int nextNode = 0;
  /** two Nodes used for next() method for Iterator */
  private Node<E> lastReturned = null;
  private Node<E> nextUp;

  /** part of the Iterator implementation */
  public boolean hasNext()
  {
    return nextNode < size;
  }

  /** part of the Iterator implementation */
  public E next()
  {
    lastReturned = nextUp;
    nextUp = nextUp.getNext();
    nextNode++;
    return lastReturned.data;
  }

  /** part of the Iterator implementation */
  public void remove()
  {
    Node<E> lastNext = lastReturned.getNext();
    if (lastReturned == null)
      nextUp = lastNext;
    else
      nextNode--;
    lastReturned = null;    
  }
}

класс Иосифа Флавия

public class Josephus<E>
{
  public static void main(String[] args)
  {
      CircularLinkedList cll = new CircularLinkedList();
      Itr iter = cll.iterator();

      int lastMan = 0;
      int n = 20;
      int passes = 12;
        while(n > 1)
        {
          iter.next();

          for(int i = 0; i < n; i += passes)
          {
          iter.hasNext();
          iter.remove();
          if(n == 1)
            lastMan = n;
          }
        }  
    System.out.println("Survior: " + lastMan);
  }
}

Класс CircularLinkedList

public class CircularLinkedList<E> 
{
  public class Node<E>
  {
    /* data value **/
    public E data;
    /* the link **/
    private Node<E> next = null;

    /** constructs a Node with given data and link
      * @param data the data value
      * @param next the link
      */
    public Node(E data, Node<E> next)
    {
      this.data = data;
      this.next = next;
    }

    /** construct a Node with given data value
      * @param data the data value
      */
    public Node(E data)
    {
      this.data = data;
    }

    /** return the data value of a Node
      * @return the data value
      */
    public E getData()
    {
      return data;
    } 

    /** set the next Node in a list
      * @param append the data value that the new Node will contain
      */
    public void setNext(Node append)
    {
      next = append;
    }

    /** return the next Node
      * @ return the next Node
      */
    public Node<E> getNext()
    {
      if(current.next == null)
      current.next = current;

      return next;
    }
  }

  /** a reference into the list */
  private Node<E> current = null;
  /** the size of the list */
  private int size = 0;

  /** helper methods */

  /** remove the first occurance of element item.
    * @param item the item to be removed
    * @return true if item is found and removed; otherwise, return false.
    */
  public void removeItem(E item)
  {
    Node<E> position = current;
    Node<E> nextPosition1,
            nextPosition2;

    while (position.next != null)
    {
      if(position.getNext().getData().equals(item))
      {
        nextPosition1 = position.getNext();
        nextPosition2 = nextPosition1.getNext();
        position.setNext(nextPosition2);
      } 
      else
      {
        position = position.getNext();  
      }
    }
  }

  /** set the first Node in a list
    * @param append the data value that the new Node will contain
    */
  public void addFirst(E append)
  {
    current = new Node<E>(append, current);
    size++;
  }

  /** add a new Node as the last in the List
    * @param data value of the new Node
    */
  public void addNext(E value)
  {
    // location for new value
    Node<E> temp = new Node<E>(value,null);
    if (current != null)
    {
      // pointer to possible tail
      Node<E> finger = current;
      while (finger.next != null)
      {
        finger = finger.next;
      }
      finger.setNext(temp);
    } else current = temp;
    size++;
  }

  /** return the data value of the fourth Node in the list
    * @return the data value
    */
  public E printFourth()
  {
    current.next.next.next = current;
    return current.next.next.next.getData();
  }

  /** return the size of the LinkedList
    * @return the size
    */
  public int size()
  {
    return size;
  }

  public E get(int index)
  {    
    Node<E> temp = null;
    for(int i = 0; i < index; i++)
    {
      temp = current.next;
      System.out.print(temp.getData() + " ");

    }
    return temp.getData();
  } 

  public Itr<E> iterator()
  {
    return new Itr<E>();
  }

  @Override
  public String toString()
  {
    StringBuilder sb = new StringBuilder();
    sb.append("[");
    Node<E> aux = this.current;
    boolean isFirst = true;
    while(aux != null)
    {
      if(!isFirst)
      {
        sb.append(", ");
      }
      isFirst = false;
      sb.append(aux.data.toString());
      aux=aux.next;
    }
  return sb.append("]").toString();
  }
}

Я получаю исключение NullPointerException из метода next() в классе Itr в строке

nextUp = nextUp.getNext();

Я делаю что-то неправильно в классе CircularLinkedList, чтобы он на самом деле не был циклическим, или есть проблема с моими классами драйверов/Itr? Я немного потерян в этот момент. Любая помощь приветствуется.


person smitty werbenjagermanjensen    schedule 05.03.2014    source источник
comment
Публикация кода — хорошая идея. Чтобы создать собственный метод iterator, вам необходимо создать класс, предоставляющий несколько методов: docs.oracle.com/javase/7/docs/api/java/util/Iterator.html. Они выберут следующий из вашей структуры данных.   -  person spikeheap    schedule 06.03.2014
comment
Чрезвычайно актуальная запись: stackoverflow.com/questions/5849154/   -  person Brian English    schedule 06.03.2014


Ответы (1)


Создайте собственный класс, реализующий Итератор, и верните пользовательский итератор из вашего метода CLL.iterator.

См. LinkedList#ListItr для вдохновения - но только рассмотрите методы Iterator (next, hasNext, remove) для этого упражнения. Настоящий круговой связанный список всегда будет следовать за следующим узлом и не будет иметь конца — hasNext всегда будет возвращать true, если есть хотя бы один элемент. Если ваша реализация CLL имеет «конец», обязательно «вернитесь к началу», когда она встретится.

Кроме того, класс CLL должен соответствовать Iterable, что означает, что у него есть метод iterator для получения Iterator.

person user2864740    schedule 05.03.2014
comment
Спасибо за совет, с тех пор я реализовал Iterator в пользовательском классе, но у меня все еще есть некоторые проблемы, которые я отредактировал в своем исходном сообщении. Любые идеи о том, что я могу делать неправильно? - person smitty werbenjagermanjensen; 06.03.2014
comment
@smittywerbenjagermanjensen Вы никогда не устанавливаете nextUp значение до того, как оно будет впервые использовано. Или, если да, то это было null. Тогда это просто вопрос отладки вашего кода — вы знаете, что nextUp равно null, так что выясните почему и исправьте это. - person user2864740; 06.03.2014
comment
Если я сделаю nextUp = null, у меня все еще будет та же проблема. Если я не должен назначать другое значение, которое я не понимаю (я некоторое время работал над этим и теряю фокус). - person smitty werbenjagermanjensen; 06.03.2014
comment
(null).getNext() является причиной возникновения исключения; и nextUp является нулевым в строке nextUp.getNext(), о чем свидетельствует исключение. Это явно недопустимо и должно быть исправлено. Я подозреваю, что nextUp изначально не назначен действительный (т.е. первый) узел; если это не так, то в какой-то момент nextUp.getNext() само дает нуль, так что nextUp становится нулевым после nextUp = nextUp.getNext(). - person user2864740; 06.03.2014