23k 23k - 6 months ago 32
Java Question

Correct implementation of List Iterator methods

To better learn about Iterators, I am to write them myself to try and get the correct functionality of them. I'm having an issue getting the correct behavior out of the

ListIterator
previous method.

For example, the JavaDoc states that:


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


My Iterator

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 ListIterator300<Item> listIterator() {

return new ListIterator300<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;
}
};
}


Now, when I test it out, I'm having incorrect behavior with the
previous()
method.

TEST

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

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

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


My Results

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


Correct Results

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


Now, to my understanding, the second set of results is the correct behavior of the
ListIterator
. So, what can I do to achieve this behavior? From what I've read, it has something to do with the cursor being moved to the element before, and not the element itself. I'm having trouble thinking of a way to implement this.

Answer

You have properly implemented the behavior for next(), advancing to the next node and returning the new value.

However, the behaviour for previous() needs to return the existing value before you change to the previous node. You'll have to store n.data in a temporary variable before updating n, and then return the stored temporary value.

For example:

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