java链表迭代器错误，输出显示错误

Question

好吧，我是一名 Java 入门程序员，我们被分配了一个项目来创建一个功能性链表。我发布我的 DLinkedlist 文件来展示我如何创建链接列表。最后，我将展示正在使用的测试仪，以确保其正常运行。异常(exception)也没关系，这就是老师想要的。问题是“当有下一个”和“当有上一个”输出时。非常感谢!

package project5;

import java.util.NoSuchElementException;

public class DLinkedList {

private Node first;
private Node last;

public DLinkedList() {
    first = null;
    last = null;
}

/**
 * Adds an element to the head of the list
 * @param data - the object to store at the head of the list
 */
public void addFirst(Object data){
    Node newNode = new Node();
    newNode.data = data; // No setter necessary

    if (first != null){
        newNode.next = first;
    }else{
        last = newNode;
    }
    first = newNode;

}

/**
 * Gets what is stored at the beginning of the list
 * @return - the data stored at the head of the list
 */
public Object getFirst(){
    /*
    This is the syntax for getting the "data attribute" of the object called "first"
    We can do this because "data" is piublic and thus we do not need to call a getter method
     */
    if (first == null){
        throw new NoSuchElementException();
    }
    return first.data;
}

/**
 * Removes the head of the list
 * @return - returns data that was stored in the same node removed
 */
public Object removeFirst(){
    if (first == null){
        throw new NoSuchElementException();
    }
    Object temp = first.data;
    first = first.next;
    return temp;
}

/**
 * Adds an element to the tail of the list
 * @param data - the object to store at the tail of the list
 */
public void addLast(Object data){
    Node newNode = new Node();
    newNode.data = data;

    if(first == null){
        addFirst(data);
    }else{
        if (last != null){
            newNode.previous = last;
            last.next = newNode;
        }
        last = newNode;
    }
}

/**
 * Gets what is stored at the end of the list
 * @return - the data stored at the tail of the list
 */
public Object getLast(){
    /*
    Ths s
     */
    if (last == null){
        throw new NoSuchElementException();
    }
    return last.data;
}

/**
 * Removes the last item in the list
 * @return
 */
public Object removeLast(){
    if (last == null){
        throw new NoSuchElementException();
    }
    Object temp = last.data;
    last = last.previous;
    return temp;
}

/**
 * Checks if the Linked List contains an object
 * @param other
 * @return
 */
public boolean contains(Object other){
    Node temp = first;
    while (temp.next != null){
        if(temp.data == other){
            return true;
        }else{
            temp = temp.next;
        }
    }
    return false;
}







/**
 * Note: We return ListIterator because it is a PUBLIC interface that can be used outside fo the LinkedList class,
 * whereas LinkedListIterator only exists inside LinkedList
 * @return
 */
public ListIterator listIterator(){
    return new LinkedListIterator();
}

class LinkedListIterator implements ListIterator{
    private DLinkedList.Node position;
    private DLinkedList.Node previous;
    private DLinkedList.Node next;
    private boolean isAfterNext;
    private boolean isAfterPrevious;



    public LinkedListIterator(){
        position = null;
        previous = null;
        next = null;
        isAfterNext = false;
        isAfterPrevious = false;
    }

    @Override
    public Object next() {
        if (!hasNext()){
            throw new NoSuchElementException();
        }
        // Updating previous to be at the current pos
        previous = position;
        // Iterator is at the beginning of the lsit
        if (position == null){
            position = first;
        }
        else{
            position = position.next;
        }
        isAfterNext = true;
        return position.data;
    }

    @Override
    public boolean hasNext() {
        if (position == null){
            // Beginning of the list
            return first != null;
        }
        else{
            return position.next != null;
        }
    }

    @Override
    public void add(Object data) {
        if (!isAfterNext){
            throw new IllegalStateException();
        }
        if (position == first){
            addFirst(data);
        }
        else{
            Node newNode = new Node();
            newNode.data = data;
            newNode.next = position.next;
            newNode.previous = position;
            position.next = newNode;
            position = newNode;
        }
    }

    @Override
    public Object remove() {
        if (!isAfterNext){
            throw new IllegalStateException();
        }
        Object temp;
        if (position == first){
            temp = removeFirst();
        }
        else{
            temp = position.data;
            previous.next = position.next;
        }
        position = previous;
        isAfterNext = false;
        return temp;
    }

    @Override
    public Object previous() {
        boolean hasBeenCalled = false;
        if (!hasPrevious()){
            throw new NoSuchElementException();
        }
        // Updating next to be at the current pos
        next = position;
        // Iterator is at the end of the list
        if (position == null){
            position = last;
        }
        else{
            position = position.previous;
        }
        isAfterPrevious = true;
        return position.next.data;



    }

    @Override
    public boolean hasPrevious() {
        if (position == null){
            // End of the list
            return first != null;
        }
        else{
            return position.previous != null;
        }
    }

    @Override
    public void set(Object element) {
        position.data = element;
    }
}



/*
Node is an inner class, which means access to it is restruced to members of its outer class, i.e. LinkedList
 */
class Node{
    /*
   These variables don't need setters or getters because they are public, and thus can be accessed/modified by any
   member of the outer class, i.e. LinkedList
    */
    public Object data;
    public Node next;
    public Node previous;
 }
}

测试仪显示预期输出与实际输出!

package project5;

import project5.DLinkedList;
import project5.ListIterator;

public class DLinkedListTester {

public static void main(String[] args) {

    DLinkedList ages = new DLinkedList();
    for(int i = 1; i <= 15; i++) {
        ages.addFirst(i);
    }

    for(int i = 16; i <= 30; i++) {
        ages.addLast(i);
    }
    System.out.println("Remove First Expected: 15");
    System.out.println("Output: "+ages.removeFirst() + "\n");

    System.out.println("Remove Last Expected: 30");
    System.out.println("Output: "+ages.removeLast() + "\n");

    System.out.println("Get First Expected: 14");
    System.out.println("Output: "+ages.getFirst() + "\n");

    System.out.println("Get Last Expected: 29");
    System.out.println("Output: "+ages.getLast() + "\n");

    System.out.println("Contains 10 Expected: true");
    System.out.println("Output: " + ages.contains(10) + "\n");

    System.out.println("Contains 100 Expected: false");
    System.out.println("Output: " + ages.contains("100") + "\n");

    ListIterator iter = ages.listIterator();

    System.out.print("While has next Expected: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16 17 18 19 20 21 22 23 24 25 26 27 28 29 \nOutput: ");
    while(iter.hasNext()) {
        System.out.print(iter.next() + " ");
    }

    System.out.println("\n");

    System.out.print("While has previous Expected: 29 28 27 26 25 24 23 22 21 20 19 18 17 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 \nOutput: ");
    while(iter.hasPrevious()) {
        System.out.print(iter.previous() + " ");
    }

    iter = ages.listIterator();
    iter.next(); //14 | 13 12 11 10 ...
    iter.next(); //14 13 | 12 11 10 ...
    iter.add("12.5"); //14 13 12.5 | 12 11 10 ...
    iter.next(); //14 13 12.5 12 | 11 10 ...
    System.out.println("\n\nRemove Expected: 12");
    System.out.println("Output: " + iter.remove() + "\n");

    iter.previous(); //14 13 | 12.5 11 10 ... 
    iter.previous(); //14 | 13 12.5 11 10 ...
    iter.remove(); //14 | 12.5 11 10 ...
    while(iter.hasNext()) {
        iter.next();
    }
    iter.previous();
    iter.set("100");
    System.out.print("\nWhile has next Expected: 14 12.5 11 10 9 8 7 6 5 4 3 2 1 16 17 18 19 20 21 22 23 24 25 26 27 28 100 \nOutput: ");
    iter = ages.listIterator();
    while(iter.hasNext()) {
        System.out.print(iter.next() + " ");
    }
 }

}

控制台输出!

Remove First Expected: 15
Output: 15

Remove Last Expected: 30
Output: 30

Get First Expected: 14
Output: 14

Get Last Expected: 29
Output: 29

Contains 10 Expected: true
Output: true

Contains 100 Expected: false
Output: false

While has next Expected: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16 17 18 19 20 21 
22 23 24 25 26 27 28 29 

Output: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16 17 18 19 20 21 22 23 24 25 26 27 
28 29 30 

While has previous Expected: 29 28 27 26 25 24 23 22 21 20 19 18 17 16 1 2 3 
4 5 6 7 8 9 10 11 12 13 14 

Output: 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 

Remove Expected: 12
Output: 12

Exception in thread "main" java.util.NoSuchElementException
 at project5.DLinkedList$LinkedListIterator.previous(DLinkedList.java:224)
 at project5.DLinkedListTester.main(DLinkedListTester.java:59)

Answer 1

如果您仔细查看代码以及链接列表的填充方式，您会注意到(填充后)从 15 (第一个元素)到 1 的元素 是单链接的，而从 16 到 30 的下一个元素是双向链接的(1 和 1 之间有一个双链接)也是16)。

关于“while has next”:
每当删除最后一个元素时，只需将 last 指针更新为前一个元素，但最后一个元素仍然保留在链表中，因此在末尾得到 30值列表。迭代器的循环在值 prev=29 和 position=30

处停止

关于“while has previous”:
因为之前的指针从元素 1 开始一直到 first 都是 null，所以您更新 position通过 position =position.previous; 因此它开始指向 29，然后输出 position.next 即 30 >，然后逐一向上遍历，自然停在 position=1 处，然后输出 position.next 即 16 并停止，因为1 的前一个指针未指向 2

所以，
1.您必须修改addFirst()，使第一个节点的previous指针指向新节点:

public void addFirst(Object data){
    Node newNode = new Node();
    newNode.data = data; // No setter necessary

    if (first != null){
        newNode.next = first;  
        first.previous = newNode; //<---added
    }else{
        last = newNode;
    }
    first = newNode;

}

2.您必须修改removeLast()，使删除的元素不再保留在列表中:

public Object removeLast(){
    if (last == null){
        throw new NoSuchElementException();
    }
    Node temp = last;
    last = last.previous;
    last.next = null;
    temp.previous = null;
    return temp.data;
}