Java 迭代器中的单链表实现

Question

我正在 Java 中编写 Bag 的简单实现。我正在实施 Iterable 并编写自己的 LinkedList 迭代器。所以我绞尽脑汁；我正在尝试将元素添加到链表中。我有一个有效的实现（add() 函数中注释掉的代码）。但是，我不明白为什么以下代码不起作用：

current.item = item;
Node<T> nextNode = new Node<T>();
current.next = nextNode;
current = nextNode;

因此，鉴于列表为空并且当前头已初始化但没有项目或下一个：我将项目分配给当前项目，创建一个新节点，将其设置为当前的下一个并更改当前（ head) 到我刚刚创建的节点。将两项添加到列表中，我打印出对象供后代使用：

current: Bag$Node@4524411f next: Bag$Node@401e7803

current: Bag$Node@401e7803 next: Bag$Node@10dba097

current: Bag$Node@10dba097 next: Bag$Node@1786f9d5

current: Bag$Node@1786f9d5 next: Bag$Node@704d6e83

看起来很清楚，至少对我来说，下一个每次都设置一个新节点就好了。我将所有四个元素添加到包中，但该项目丢失并且每个索引的 returns 为空。 toArray() 函数显示 [null, null, null, null]

我敢肯定这是非常简单的事情。下面是整个实现。

import java.util.Iterator;

public class Bag<T> implements Iterable<T> {
    private Node current;
    //Node<T> head;
    private int numberofProducts;
    T[] myBag;
    int defaultCapacity;

    public Iterator<T> iterator() {
        return new ListIterator<T>(current);
    }

    public Bag(int defaultCapacity) {
        this.current = new Node<T>();
        this.numberofProducts = 0;
        this.defaultCapacity = defaultCapacity;
    }

    public void add(T item) {
        if(isFull()) {
            System.out.println("bags full, yo");
            return;
        }

        current.item = item;
        Node<T> nextNode = new Node<T>();
        current.next = nextNode;
        current = nextNode;

        numberofProducts++;

    //Node<T> nextNode = current;
    //current = new Node<T>();
    //current.item = item;
    //current.next = nextNode;
    //numberofProducts++;


    }

    public Object[] toArray() {
        Object[] array = new Object[size()];

        int i = 0;
        Node<T> node = current;
        //Node<T> node = head;
        while(node.next != null) {
            array[i] = node.item;
            node = node.next;
            i++;
        }

        return array;
    }

    public boolean isEmpty() {
        return this.numberofProducts <= 0;
    }

    public boolean isFull() {
        return this.numberofProducts >= defaultCapacity;
    }

    public int size() {
        return this.numberofProducts;
    }

    private class Node<T> {
        private T item;
        private Node<T> next;
    }


    private class ListIterator<T> implements Iterator<T> {

        private Node<T> current;

        public  ListIterator(Node<T> first) {
            current = first;
        }

        public boolean hasNext() {

            return current != null;
        }

        public T next() {
            if(hasNext()) {
                T item = current.item;
                current = current.next;
                return item;
            }
            return null;
        }

        public void remove() {

        }
    }
}

Answer 1

项目值没有丢失。问题是你忘记了链表的头部。您的 current 变量已经跟踪尾部，并且由于您的 toArray() 方法从 current 开始，因此 while 循环永远不会执行，因为尾部元素之后没有元素名单。

因此，您最终会得到一组默认初始化的 Object 值，即 null。

要解决这个问题，您需要另一个实例变量来跟踪列表的头部，这就是您将在 toArray() 方法中使用的内容。

Answer 2

据我所知，它不充当链接列表的原因是因为您没有保留对添加的第一个元素的引用。相反，您保留对添加的最后一个 (current) 元素的引用。

您可以通过在添加的第一个元素中添加一个 class 字段引用来解决此问题 T head

然后在您的 add() 方法中，将 head 设置为您创建的 Node。然后，当您构建 ListIterator 时，将 head 作为参数传递。

您可以将 add(T item) 更改为这样显示：

public void add(T item) {
    if (!isFull()) {
        Node<T> toAdd = new Node<>();
        toAdd.item = item;
        current.next = toAdd;
        current = toAdd;
        if (head == null) {
            head = toAdd;
        }
    }
}

然后将 class 字段 Node<T> head 添加到您的 Bag<T> class。

此外，我不确定为什么 Node 是静态的 class，还有一些我现在不会涉及的其他更改，但我猜 class目前不完整。

Answer 3

问题出在您在 add() 方法中编写的逻辑。每当将新数据添加到 Bag 时，您的根节点都会更改并指向 Bag 的最后一个节点。由于倒数第二个节点为空，这就是迭代器不返回任何内容的原因。具体解法请参考to this link。

Java 迭代器中的单链表实现

Singly Linked List implementation in Java Iterator

java

linked-list

iterator

singly-linked-list

iterable