java - 如何创建链表的迭代器？

Question

public class Java_Practice {

private static class LinkedListTest {

    private String data;
    private LinkedListTest next;

    public LinkedListTest(String data) {
        super();
        this.data = data;
    }

    public String getData() {
        return data;
    }

    public LinkedListTest getNext() {
        return next;
    }

    public void setNext(LinkedListTest next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "LinkedListTest [data=" + data + ", next=" + next + "]";
    }

}

// Do a deep copy
private static LinkedListTest copyLlt(LinkedListTest original) {

    LinkedListTest copy = new LinkedListTest(original.getData() + " copied");

    LinkedListTest nextCopy = original.getNext();
    LinkedListTest current = copy;

    while (nextCopy != null) {

        LinkedListTest newCopy = new LinkedListTest(nextCopy.getData() + " copied");
        newCopy.setNext(nextCopy.getNext());

        current.setNext(newCopy);

        current = newCopy;
        nextCopy = newCopy.getNext();
    }

    return copy;
}

我有一个类似这样的链表代码。我想创建一个具有 3 个私有(private)成员的迭代器:cur(当前节点)、itnext(下一个节点)和 list(我们正在迭代的整个列表)。我想知道如何获得列表值。有什么方法可以找出当前节点的前一个节点吗？抱歉，如果这是一个菜鸟问题。提前致谢

Answer 1

迭代器不需要下一个节点私有(private)成员，因为它可以从当前节点获取下一个节点。这个问题没有提到你想用迭代器实现什么方法。

figure out the previous node of the current node?

对于单个链表，没有简单的方法可以向后遍历列表。如果方法不涉及向后遍历列表，则迭代器可以是指向前一个节点的指针(引用)，这将需要使用虚拟节点作为列表的头节点，以便每个数据节点都有一个前一个节点节点。

使用指向前一个节点的迭代器，可以实现插入和删除方法(以及获取和设置数据)。

<小时/>

使用双链表，可以实现拼接方法(将列表中的节点移动或从一个列表移动到另一个列表)，以及向后遍历列表。

请注意，我认为 Java 的链表迭代器 native 实现是一个糟糕的实现，因为它派生自面向数组的类，这与 C++ 模板库不同，后者将链表实现为独立的双向链表容器。使用 C++ std::list 没有索引，但 std::next 可以扫描列表来模拟索引，尽管速度很慢。由于 Java 在其内部链表迭代器中保留索引，因此任何节点的插入或删除都会使该列表的所有其他迭代器无效，这就是我认为它是一个如此糟糕的实现的原因之一。我认为 Java 列表迭代器较差的另一个原因是 Java 迭代器无法复制(相反，您只是获得对同一迭代器对象的重复引用)。