列表迭代器方法的正确实现
Correct implementation of List Iterator methods
为了更好地了解迭代器,我将自己编写它们以尝试获得它们的正确功能。我在从 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
的正确行为。那么,我该怎么做才能实现这种行为呢?从我读过的内容来看,它与之前将光标移动到元素有关,而不是元素本身。我在想办法实现它时遇到了麻烦。
您已正确实施 next()
的行为,前进到下一个节点并 return 获取新值。
但是,previous()
的行为需要 return 现有值才能更改为上一个节点。在更新 n
之前,您必须将 n.data
存储在临时变量中,然后 return 存储的临时值。
例如:
public Item previous() {
Item temp = n.data;
n = n.previous;
return temp;
}
为了更好地了解迭代器,我将自己编写它们以尝试获得它们的正确功能。我在从 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
的正确行为。那么,我该怎么做才能实现这种行为呢?从我读过的内容来看,它与之前将光标移动到元素有关,而不是元素本身。我在想办法实现它时遇到了麻烦。
您已正确实施 next()
的行为,前进到下一个节点并 return 获取新值。
但是,previous()
的行为需要 return 现有值才能更改为上一个节点。在更新 n
之前,您必须将 n.data
存储在临时变量中,然后 return 存储的临时值。
例如:
public Item previous() {
Item temp = n.data;
n = n.previous;
return temp;
}