java - 如何正确实现 ListIterator 的中间模型？

Question

我正在尝试编写自己的 CustomLinkedList<E>快速通过我需要实现堆栈和队列的实验室。我可以在没有这门课的情况下通过实验(因为我根本不需要实现 iterable)，但我想掌握这个概念，因为我正在学习 java。

我现在已经运行并测试了大部分内容，但我还不能使迭代器正常工作。

第一种方法是“后增量”，例如:

E result = current.getValue();
current = current.getNext();
return result;

我发现它坏了，因为当我到达列表的末尾时，我将无法返回。我的hasNext()只是检查当前是否为 null ，因此失去了返回的能力。

第二种方法是添加虚拟 Node关于创作，以模特为开端。它有一个确定我是否在列表开头的问题，因为使用这种方法我不知道开头在哪里，直到为时已晚。

    Iterator(Node root)
    {
        current = new Node(null, null, root);
    }

    public E next()
    {
        //checks and stuff
        current = current.getNext();
        return current.getValue();
    }

因此，问题是:是否有可能实现ListIterator<>只知道当前元素？如果是，一些代码划痕会很棒。

编辑:

Node :

private class Node
{
    private Node prev;
    private T value;
    private Node next;

    Node(Node prev, T value, Node next) {
        this.setPrev(prev);
        this.setValue(value);
        this.setNext(next);
    }

    //getters and setters
}

CustomLinkedList<E> :

public class CustomLinkedList<T>  implements Iterable<T>{
    private class Node {/**/}

    private class Iterator implements java.util.ListIterator<T> {
        Node current;

        public Iterator(Node root) //from the first approach
        {
            current = root; 
        }

        //other methods
    }

    Node root;
    int size;

    //Object methods, and some basic Collection methods
}

Answer 1

我会做这样的事情:

public class CustomLinkedList<T>  implements Iterable<T>{
    private class Node {/**/}

    private class Iterator implements ListIterator<T> {
        Node next, previous;

        Iterator() {
            next = root;
            previous = null; 
        }

        public boolean hasNext() {
            return next != null;
        }

        public T next() {
            if ( ! hasNext()){
                throw new NoSuchElementException();
            }
            previous = next;
            next = next.getNext();
            return previous;
        }

        public boolean hasPrevious() {
            return previous != null;
        }

        public T previous() {
            if ( ! hasPrevious() ){
                throw new NoSuchElementException();
            }
            next = next.getPrevious();
            previous = next.getPrevious();
            return next;
        }
    }

    Node root;
    int size;

    //Object methods, and some basic Collection methods
}

这并没有实现 ListIterator 接口(interface)的其他方法，但您明白了。您需要将迭代器的光标视为在前一个元素和下一个元素之间，而不是在其中一个元素上。有关正确的实现，请参阅 Jorn Vernee's link .