Having trouble with my CircularList

Question

Right now I am trying to create a circular list, where when I use hasNext() from an Iterator it should always return true. However right now it is returning that it is not a circular list, and I am also having problems printing out the values (in this example Strings) of the ArrayList. Here is the CircularList class I created, which has a inner Node class for the objects that are put into the list:

public class CircularList<E> implements Iterable{
private Node<E> first = null;
private Node<E> last = null;
private Node<E> temp;
private int size = 0;

//inner node class
private static class Node<E>{ //In this case I am using String nodes
    private E data; //matching the example in the book, this is the data of the node
    private Node<E> next = null; //next value
    //Node constructors, also since in this case this is a circular linked list there should be no null values for previous and next    
    private Node(E data){
        this.data = data;
    }
}
//end of inner node class
public void addValue(E item){
    Node<E> n = new Node<E>(item);
    if(emptyList() == true){ //if the list is empty
        //only one value in the list
        first = n;
        last = n;
    }
    else{ //if the list has at least one value already
        //store the old first value
        temp = first;
        //the new first is the input value
        first = n;
        //next value after first is the old first value
        first.next = temp;
        //if after this there will be only two values in the list once it is done
        if(size == 1){
            last = temp;
        }
        //if the list is greater than one than the last value does not change, since any other values will be put before last in this case, and not replace it
        //creating the circular part of the list
        last.next = first;
    }
    size++;
}

public boolean emptyList(){
    boolean result = false;
    if(first == null && last == null){ //if there is no values at all
        result = true;
    }
    return result;
}

@Override
public Iterator<E> iterator() {
    // TODO Auto-generated method stub
    return new CircularIterator<E>(); //each time this method is called it will be creating a new instance of my Iterator
}
}

Here is the Iterator class I am making:

public class CircularIterator<E> implements Iterator<E> {

@Override
public boolean hasNext() {
    return false;
}

@Override
public E next() {
    // TODO Auto-generated method stub
    return null;
}

@Override
public void remove() {
    // TODO Auto-generated method stub

}

}

and finally the Test class:

public class Test {
static CircularList<String> c = new CircularList<String>(); //in this case it is a string list
static Iterator it = c.iterator();

public static void main(String[]args){
    c.addValue("Bob");
    c.addValue("Joe");
    c.addValue("Jaina");
    c.addValue("Hannah");
    c.addValue("Kelly");
    Iterate();

    for(String val : c){
        System.out.println(val);
    }
}

private static boolean Iterate(){
    boolean result = false;
    if(!it.hasNext()){
        System.out.println("Not a circular list!");
    }
    else{
        result = true;
    }
    return result;
}
}

Again I am trying to get it to always return true, I think the problem lies with my hasNext() method, but I am not completely sure.

Answer 1

You can simply use following for circular iteration. This Circular list behave as same as other java.util.Lists. But it's iteration is modified. You don't need to care about it's performance tuning additionally. Because it's super class (LinkedList) is already well tested and enough stronger to use.

`public class CircularList extends LinkedList {

@Override
public Iterator<E> iterator() {
    return createIterator();
}

//create new iterator for circular process
private Iterator<E> createIterator() {
    return new Iterator<E>() {
        private int index = 0;

        @Override
        public boolean hasNext() {
            //no elements when list is empty
            return isEmpty();
        }

        @Override
        public E next() {
            E node = get(index);

            //rotate index
            index++;
            if (index == size()) {
                index = 0;
            }

            return node;
        }
    };
}

}`

Answer 2

The main problem with your approach is you are using static inner classes - this is not necessary. Making the outer class generic is sufficient. The generic parameter is then inherited by the inner classes and all sorts of issues disappear.

Implementing an Iterator properly is subtle.

public static class CircularList<E> implements Iterable<E> {

    private Node first = null;
    private Node last = null;
    private int size = 0;

    private class Node {

        private E data;
        private Node next = null;

        private Node(E data) {
            this.data = data;
        }
    }

    public void addValue(E item) {
        Node n = new Node(item);
        if (emptyList()) {
            //only one value in the list
            first = n;
            last = n;
        } else { //if the list has at least one value already
            //store the old first value
            Node temp = first;
            //the new first is the input value
            first = n;
            //next value after first is the old first value
            first.next = temp;
            //if after this there will be only two values in the list once it is done
            if (size == 1) {
                last = temp;
            }
            //if the list is greater than one than the last value does not change, since any other values will be put before last in this case, and not replace it
            //creating the circular part of the list
            last.next = first;
        }
        size++;
    }

    public boolean emptyList() {
        boolean result = false;
        if (first == null && last == null) { //if there is no values at all
            result = true;
        }
        return result;
    }

    @Override
    public Iterator<E> iterator() {
        return new CircularIterator(); //each time this method is called it will be creating a new instance of my Iterator
    }

    private class CircularIterator implements Iterator<E> {

        // Start at first.
        Node next = first;

        public CircularIterator() {
        }

        @Override
        public boolean hasNext() {
            // Stop when back to first.
            return next != null;
        }

        @Override
        public E next() {
            if (hasNext()) {
                E n = next.data;
                next = next.next;
                if (next == first) {
                    // We're done.
                    next = null;
                }
                return n;
            } else {
                throw new NoSuchElementException("next called after end of iteration.");
            }
        }
    }
}

public void test() {
    CircularList<String> c = new CircularList<>();
    c.addValue("A");
    c.addValue("B");
    c.addValue("C");
    c.addValue("D");
    for (String s : c) {
        System.out.println(s);
    }
}

Your main code was essentially correct - all I did was remove the unnecessary generics parameters from the inner classes.

Note that the way you add node to the list means that the items come out backwards. You could adjust that in your addValue method quite easily.