我的 CircularList 有问题

Question

现在我正在尝试创建一个循环列表，当我从 Iterator 使用 hasNext() 时，它应该总是 return true。但是现在 returning 它不是循环列表，而且我在打印 ArrayList 的值（在本例中为字符串）时也遇到了问题。这是我创建的 CircularList class，它有一个内部节点 class 用于放入列表的对象：

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

这是我正在制作的迭代器class：

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

}

}

最后是测试 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;
}
}

我再次尝试让它始终 return 正确，我认为问题在于我的 hasNext() 方法，但我不完全确定。

Answer 1

您的方法的主要问题是您使用的是 static 内部 classes - 这不是必需的。使外部 class 通用就足够了。然后通用参数被内部 classes 继承，所有问题都消失了。

正确实施 Iterator 很微妙。

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

您的主要代码基本上是正确的 - 我所做的只是从内部 classes 中删除不必要的泛型参数。

请注意，您将节点添加到列表的方式意味着项目向后出现。您可以很容易地在 addValue 方法中对其进行调整。

Answer 2

你可以简单地使用following进行循环迭代。此循环列表的行为与其他 java.util.Lists 相同。但是它的迭代被修改了。您不需要另外关心它的性能调整。因为它的超级 class (LinkedList) 已经经过很好的测试并且足够强大可以使用。

`public class CircularList 扩展了 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;
        }
    };
}

}`

我的 CircularList 有问题

Having trouble with my CircularList

java

list

iterator

iterable

circular-reference