双向链表实现的Deque调用addLast后输出null不符合预期问题排查

1. 构造函数逻辑错误：空Deque初始化时创建了一个无有效数据的空节点，该节点item属性为null，会被插入到前插元素和后插元素中间，遍历过程中会被输出导致出现null行。
2. 迭代器逻辑错误：hasNext方法判断条件为current.next != null，既会漏掉链表最后一个有效元素，也不符合常规迭代器的判断逻辑，应该直接判断当前待返回节点是否存在。
3. 边界情况处理缺失：现有addFirst/addLast/removeFirst/removeLast方法均未处理Deque为空、仅剩一个元素的边界场景，调整构造逻辑后会触发空指针异常。

以下是所有需要修改的代码片段：

1. 修改构造函数 #

移除多余的空节点初始化，空队列状态下first和last均为null：

// 构造空的双端队列
public Deque()
{
    first = null;
    last = null;
    size = 0;
}

2. 修改addFirst方法，新增空队列分支处理 #

// 向队首添加元素
public void addFirst(Item item)
{
    if (item == null) throw new IllegalArgumentException();
    Node n = new Node();
    n.item = item;
    if (isEmpty()) {
        first = n;
        last = n;
    } else {
        Node oldFirst = first;
        n.next = oldFirst;
        oldFirst.previous = n;
        first = n;
    }
    size++;
}

3. 修改addLast方法，新增空队列分支处理 #

// 向队尾添加元素
public void addLast(Item item)
{
    if (item == null) throw new IllegalArgumentException();
    Node n = new Node();
    n.item = item;
    if (isEmpty()) {
        first = n;
        last = n;
    } else {
        last.next = n;
        n.previous = last;
        last = n;
    }
    size++;
}

4. 修改迭代器逻辑 #

调整hasNext判断条件，符合常规迭代器逻辑：

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

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

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

5. 修改removeFirst方法，处理仅剩一个元素的边界场景 #

// 移除并返回队首元素
public Item removeFirst()
{
    if (isEmpty()) throw new NoSuchElementException();
    Node oldFirst = first;
    Item item = oldFirst.item;
    if (size == 1) {
        first = null;
        last = null;
    } else {
        first = first.next;
        first.previous = null;
        oldFirst.next = null;
    }
    size--;
    return item;
}

6. 修改removeLast方法，处理仅剩一个元素的边界场景 #

// 移除并返回队尾元素
public Item removeLast()
{
    if (isEmpty()) throw new NoSuchElementException();
    Node oldLast = last;
    Item item = oldLast.item;
    if (size == 1) {
        first = null;
        last = null;
    } else {
        last = last.previous;
        last.next = null;
        oldLast.previous = null;
    }
    size--;
    return item;
}

修改完成后运行测试用例即可得到预期输出。

内容的提问来源于stack exchange，提问作者DaWise_Weirdo