java 迭代器中的自定义链表无法遍历整个列表

Question

我在java中创建了一个链表，问题是

    public void add(T data)

当我尝试在列表末尾添加一些内容时，"null" 被添加到列表末尾。我认为我的迭代器存在一些问题，无法找到最后一个节点。请帮助。

public class LinkedList<T> implements Iterable<T> {
    private Node<T> head;
    /**
     * Default constructor
     * 
     * @param head
     */
    public LinkedList() {
        super();
        this.head = new Node<T>(null);
    }
    /**
     * Inserts a new node at the beginning of this list.
     */
    public void addFirst(T data) {
        Node<T> newNode = new Node<T>(data, head);
        head = newNode;
    }
    public void add(T data) {
        Node<T> tempNpde = head;
        while (tempNpde.next != null) {
            tempNpde = tempNpde.next;
        }
        tempNpde.next = new Node<T>(data, null);
    }
    /**
     * 
     * @param head
     * @return
     */
    public T getNode() {
        return head.data;
    }
    @Override
    public Iterator<T> iterator() {
        return new ListIterator<T>();
    }
    public class ListIterator<T> implements Iterator<T> {
        private Node<T> currentNode;
        /**
         * @param currentNode
         */
        public ListIterator() {
            super();
            this.currentNode = (Node<T>) head;
        }
        @Override
        public boolean hasNext() {
            if (currentNode != null && currentNode.next != null)
                return true;
            else
                return false;
        }
        @Override
        public T next() {
            if (!hasNext())
                throw new NoSuchElementException();
            T node = currentNode.data;
            currentNode = currentNode.next;
            return node;
        }
        @Override
        public void remove() {
            // TODO Auto-generated method stub
        }
    }
    // Same as using struct in C
    private static class Node<T> {
        private T data;
        private Node<T> next;
        /**
         * @param data
         * @param next
         */
        public Node(T data, Node<T> next) {
            super();
            this.data = data;
            this.next = next;
        }
        /**
         * @param next
         */
        public Node(Node<T> next) {
            super();
            this.data = null;
            this.next = next;
        }
    }
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<String>();
        list.addFirst("aaaa");
        list.addFirst("bbbb");
        list.add("dddd");
        Iterator<String> itr = list.iterator();
        while (itr.hasNext()) {
            System.out.println(itr.next());
        }
    }

Answer 1

为什么不简单地将 Head 和 Tail 作为两个单独的字段进行跟踪，当您需要添加新节点时，将 Tail.next 设置为新节点，然后将 Tail 设置为新节点？每次要添加内容时都遍历整个列表是非常低效的。

另外，直接回答你的问题，你的迭代器坏了。看看你的 next() 方法在做什么。它实际上是返回下一个节点吗？

Answer 2

如前所述，最大的问题是您的 next() 没有按照您的想法行事...试试这个：

public class LinkedList<T> implements Iterable<T> {
    private Node<T> head;

    /**
     * Default constructor
     *
     * @param head
     */
    public LinkedList() {
        super();
        this.head = null;
    }

    /**
     * Inserts a new node at the beginning of this list.
     */
    public void addFirst(T data) {
        Node<T> newNode = new Node<T>(data, head);
        head = newNode;
    }

    public void add(T data) {

        if ( head == null )
        {
            head = new Node<T>(data, null);
            return;
        }

        Node<T> tempNode = head;
        while (tempNode.next != null) {
            tempNode = tempNode.next;
        }
        tempNode.next = new Node<T>(data, null);
    }

    /**
     * @param head
     * @return
     */
    public T getNode() {
        return head.data;
    }

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

    public class ListIterator<T> implements Iterator<T> {
        private Node<T> currentNode;
        private Node<T> previous;

        /**
         * @param currentNode
         */
        public ListIterator() {
            super();
            this.currentNode = (Node<T>) head;
            this.previous = null;
        }

        @Override
        public boolean hasNext() {
            if (currentNode != null && currentNode.next != null)
                return true;
            else
                return false;
        }

        @Override
        public T next() {
            if (!hasNext())
                throw new NoSuchElementException();
            if ( previous == null )
            {
                previous = currentNode;
                return previous.data;
            }
            T node = currentNode.data;
            currentNode = currentNode.next;
            return currentNode.data;
        }

        @Override
        public void remove() {
            // TODO Auto-generated method stub
        }
    }

    // Same as using struct in C
    private static class Node<T> {
        private T data;
        private Node<T> next;

        /**
         * @param data
         * @param next
         */
        public Node(T data, Node<T> next) {
            super();
            this.data = data;
            this.next = next;
        }

        /**
         * @param next
         */
        public Node(Node<T> next) {
            super();
            this.data = null;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<String>();
        list.add("aaaa");
        list.add("bbbb");
        list.addFirst("cccc");
        list.add("dddd");
        list.add("eeee");
        list.add("ffff");
        for ( String s : list ) // same thing as using an iterator
            System.out.println(s);
    }
}

_{这是class的全部内容。这应该为您修复功能，但如果您发现任何不满意的更改（例如，将 head 更改为最初 null 而不是具有空数据的节点），请告诉我...}

Answer 3

一个更简单的解决方案是将您的 ListIterator#hasNext() 实现修改为

@Override
public boolean hasNext() {
    if (currentNode != null)
        return true;
    else
        return false;
}

你的最后一个元素没有被你的 ListIterator 覆盖的原因是它总是 return false 对于 currentNode.next != null 因为它在最后。

删除此条件不会破坏您的迭代器实现。通过上述更改，当您的 ListIterator 位于最后一个元素时，现在 hasNext() returns true。随后的 next() 调用 return 的 currentNode.data 并将 ListIterator 指向 null，然后根据需要中断迭代循环。

基本上，您的 ListIterator#next() 实现很好。

java 迭代器中的自定义链表无法遍历整个列表

Custom linked list in java iterator not able to iterate over the entire list

java

iterator