Java Iterator for circular linked list

Question

I've created a CircularLinkedList class, instead of using the util LinkedList class. The problem is based off of the Josephus problem, stating that for a circle of 20 people, each 12th person is to be killed until it is determined which position the survivor will be left standing in (using an Iterator). I'm confused as to how I could use an Iterator with this problem, since I'm using my own class instead of LinkedList, which already has an iterator() method so that I could declare an Iterator like this:

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

I have no idea how I would write my own Iterator method, and I feel like I have to be over thinking this. Any help is appreciated! I can post my code if it would clear anything up that I forgot to mention

I'm still stuck on this, so I figured I'd post my code to see if anyone can help. It's a lot, so I apologize.

Itr class (Iterator)

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

Josephus class

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 class

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

I'm getting a NullPointerException from the next() method in the Itr class on the line

nextUp = nextUp.getNext();

Am I doing something wrong in the CircularLinkedList class for it to not actually be circular or is there a problem with my driver/Itr classes? I'm kind of lost at this point. Any help is appreciated.

Answer 1

Create a custom class which implements Iterator and return the custom Iterator from your CLL.iterator method.

See LinkedList#ListItr for inspiration - but only conside the Iterator methods (next, hasNext, remove) for this exercise. A true circular linked-list will simply follow the next node, always, and has no end - hasNext will always return true if there is at least one element. If your CLL implementation has an "end", then make sure to "move back to the start" when it is encountered.

In addition, the CLL class should conform to Iterable, which means it has an iterator method to obtain an Iterator.