为什么这个双端队列没有为 addLast 产生预期的结果

Question

我正在为双端队列（作为双向链表实现）编写代码，当我运行测试客户端（主要方法）时，结果并不像我预期的那样。任何人都可以解释为什么会发生这种情况，并可能解释如何修复此错误？我认为它要么与 addLast

有关

预期结果：

Task: Begin Elementary Sorts
Task: Finish Implementing RandomizedQueue
Task: Finish Implementing Deque
Task: Testing
Task: Testing
Task: Testing
Task: Testing

获得的结果：

Task: Begin Elementary Sorts
Task: Finish Implementing RandomizedQueue
Task: Finish Implementing Deque
Task: null
Task: Testing
Task: Testing
Task: Testing

代码

// Implemented via a Doubly Linked-List.
public class Deque<Item> implements Iterable<Item> { 
    private int size;
    private Node first, last;

    private class Node
    {
        Item item;
        Node next;
        Node previous;
    }

    private class DequeIterator implements Iterator<Item>
    {
        private Node current = first;

        public boolean hasNext()
        {
            return current.next != null;
        }

        public Item next()
        {
            if (hasNext() == false) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    // construct an empty deque
    public Deque()
    {
        Node n = new Node();
        first = n;
        last = first;
    }

    // is the deque empty?
    public boolean isEmpty(){ return size == 0; }

    // return the number of items on the deque
    public int size() { return size; }

    // add the item to the front
    public void addFirst(Item item)
    {
        if (item == null) throw new IllegalArgumentException();
        Node n = new Node();
        Node oldFirst = first;
        n.item = item;
        n.next = oldFirst;
        first = n;
        oldFirst.previous = n;
        size++;
        return;
    }

    // add the item to the back
    public void addLast(Item item)
    {
        if (item == null) throw new IllegalArgumentException();
        Node n = new Node();
        last.next = n;
        n.previous = last;
        n.item = item;
        last = n;
        size++;
        return;
    }

    // remove and return the item from the front
    public Item removeFirst()
    {
        if (size == 0) throw new NoSuchElementException();

        Node oldFirst = first;
        first = first.next;
        oldFirst.next = null;
        first.previous = null;
        size--;
        return oldFirst.item;
    }

    // remove and return the item from the back
    public Item removeLast()
    {
        if (size == 0) throw new NoSuchElementException();
        Node oldLast = last;
        last = last.previous;
        last.next = null;
        oldLast.previous = null;
        size--;
        return oldLast.item;
    }

    // return an iterator over items in order from front to back
    public Iterator<Item> iterator(){ return new DequeIterator(); }

    // unit testing (required)
    public static void main(String[] args)
    {
        Deque<String> todo = new Deque<String>();
        todo.addFirst("Finish Implementing Deque");
        todo.addFirst("Finish Implementing RandomizedQueue");
        todo.addFirst("Begin Elementary Sorts");
        todo.addLast("Testing");
        todo.addLast("Testing");
        todo.addLast("Testing");
        todo.addLast("Testing");

        // Iterator<String> tasks = todo.iterator();

        // while (tasks.hasNext())
        // {
        //     String task = tasks.next();
        //     StdOut.println(task);
        // }

        // System.out.println(todo.removeFirst());
        // System.out.println(todo.removeLast());
        // System.out.println("After Removal:");
        // if (!todo.isEmpty() && todo.size() != 0)
            for (String task: todo)
                System.out.println("Task: " + task);
    }
}

Answer 1

您的 addLast 函数实现需要处理 last.item 为空的情况。

要达到目标输出，您应该检查 last.item == null，然后将该值放入 last。

这是我的实现：

// add the item to the back
public void addLast(Item item)
{
    if (item == null) throw new IllegalArgumentException();
    Node n = new Node();

    if (last.item == null) {
        last.item = item;
    }
    else {
        last.next = n;
        n.previous = last;
        n.item = item;
        last = n;
    }
    size++;
}

输出：

Task: Begin Elementary Sorts
Task: Finish Implementing RandomizedQueue
Task: Finish Implementing Deque
Task: Testing
Task: Testing
Task: Testing

为什么这个双端队列没有为 addLast 产生预期的结果

Why does this deque not produce the expected result for addLast

java

iterator

deque

nodes