java - 列表迭代器方法的正确实现

Question

为了更好地了解迭代器，我将自己编写它们以尝试获得它们的正确功能。我在从 ListIterator 之前的方法中获取正确行为时遇到问题。

例如，JavaDoc 指出:

Alternating calls to next and previous will return the same element repeatedly.

我的迭代器

class Node<Item> {
    public Item data;
    public Node<Item> next;
    public Node<Item> previous;

    public Node() {
        data = null;
        next = null;
        previous = null;
    }

    public Node(Item i, Node<Item> n, Node<Item> p) {
        data = i;
        next = n;
        previous = p;
    }
}

public ListIterator<Item> listIterator() {

    return new ListIterator<Item>() {

        private Node<Item> n = first;

        public boolean hasNext() {
            return n.next != last;
        }

        public Item next() {
            n = n.next;
            return n.data;
        }

        //TODO
        public void remove() {
        }

        public boolean hasPrevious() {
            return n.previous != first;
        }

        public Item previous() {
            n = n.previous;
            return n.data;
        }
    };
}

现在，当我对其进行测试时，我发现 previous() 方法的行为不正确。

测试

LinkedList<String> lst2 = new LinkedList<String>();

    for (int i = 0; i < 4; i++)
        lst2.add("" + "data".substring(i, i + 1));

    ListIterator<String> it2 = lst2.listIterator();
    System.out.println("\nTest the list iterator.\nThe test list is " + lst2 + "\n");

    while (it2.hasNext()) {
        System.out.println("next is " + it2.next());
        System.out.println("previous is " + it2.previous());
        if (removeImplemented) {
            it2.remove();
            System.out.println("After remove: " + lst2);
        }
        System.out.println("next is " + it2.next());
    }

    System.out.println("\nHere is how the built-in Java ArrayList class works\n");
    ArrayList<String> lst3 = new ArrayList<String>();

    for (int i = 0; i < 4; i++)
        lst3.add("" + "data".substring(i, i + 1));

    ListIterator<String> it3 = lst3.listIterator();
    System.out.println("Test list iterator.\nThe test list is " + lst3 + "\n");

    boolean remove = false;

    while (it3.hasNext()) {
        System.out.println("next is " + it3.next());
        System.out.println("previous is " + it3.previous());
        if (remove) {
            it3.remove();
            System.out.println("After remove: " + lst3);
        }
        System.out.println("next is " + it3.next());
    }

我的结果

The test list is [d, a, t, a]

next is d
previous is null //incorrect
next is d
next is a
previous is d //incorrect
next is a
next is t
previous is a //incorrect
next is t
next is a
previous is t //incorrect
next is a

正确结果

The test list is [d, a, t, a]

next is d
previous is d
next is d
next is a
previous is a
next is a
next is t
previous is t
next is t
next is a
previous is a
next is a

现在，据我了解，第二组结果是 ListIterator 的正确行为。那么，我该怎么做才能实现这种行为呢？根据我的阅读，它与之前将光标移动到元素有关，而不是与元素本身有关。我无法想出实现此目的的方法。

Answer 1

您已经正确实现了 next() 的行为，前进到下一个节点并返回新值。

但是，previous() 的行为需要在更改到上一个节点之前返回现有值。在更新 n 之前，您必须将 n.data 存储在临时变量中，然后返回存储的临时值。

例如:

public Item previous() {
    Item temp = n.data;
    n = n.previous;
    return temp;
}