java - java数据结构异常

Question

我正在编写一个通用数据结构，可以从第一个或最后一个节点添加和删除我测试了我的代码，但是在某些特定的输入方式中出现了异常。

现在，如果我添加最后一个，然后添加第一个，然后删除最后一个，我会遇到异常

当我多次添加第一个而不添加最后一个然后尝试通过removelast()函数删除它们时，我得到了异常但是当我添加last很多次而没有首先添加然后通过removefirst()删除它们时它会起作用

我试图避免 while 循环，这是代码

 import java.util.Iterator;
 public class Deque <Item> implements Iterable <Item> {

private Node first,last;

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

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

public boolean IsEmpty()
{
    return first == null;
}

public void addFirst(Item item)
{
    Node oldfirst = first;
    first = new Node();
    first.item = item;
    first.next = oldfirst;
    first.prev = null;
    if (last == null)
    {
        last = first;

    }

}

public void addlast(Item item)
{
    Node oldlast = last;
    last = new Node();
    last.item = item;
    last.next = null;
    if (first == null)
    {
        first = last;
    }
    else
    {
        last.prev = oldlast;
        oldlast.next = last;
    }
}

public Item removeFirst()
{
    Item x = first.item;
    first = first.next;
    if (IsEmpty())
        last = null;
    return x;
}

public Item removeLast()
{
    if (first == last)
        return removeFirst();
    Item x = last.item;
    last = last.prev;
    last.next = null;
    if (IsEmpty())
        first = null;
    return x;
}

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

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

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

    public void remove()
    {
        //NOt Supported
    }

    public Item next()
    {
        Item x = current.item;
        current = current.next;
        return x;
    } 

}}

我相信removelast()中的last.prev有问题，因为它已经为空，然后在remove()中引用了last = last.perv但我想不出一种方法将最后一个节点链接到第一个节点的最后一个节点

谁能帮我解决这个问题

如果你想尝试的话，这是主要内容...

public class Main {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Deque<Integer> o = new Deque<Integer>();
    int num = 0;
    while (true)
    {
        StdOut.println("enter 1 to addfirst, 2 addlast, 3 removefirst, 4 removelast, " +
                "5 to exit");
        num = StdIn.readInt();
        if (num == 5)
            break;
        switch (num)
        {
        case 1:
            StdOut.println("enter number to add first");
            int x = StdIn.readInt();
            o.addFirst(x);
            break;
        case 2:
            StdOut.println("enter number to add last");
            int y = StdIn.readInt();
            o.addlast(y);
            break;
        case 3:
            int w=o.removeFirst();
            StdOut.print("the deleted number is: ");
            StdOut.print(w);
            StdOut.println();
            break;
        case 4:
            int z=o.removeLast();
            StdOut.print("the deleted number is: ");
            StdOut.print(z);
            StdOut.println();
            break;
        default:
            StdOut.println("Stick with the range!");
            break;
        }

        for (Iterator<Integer> i=o.iterator(); i.hasNext();)
        {
            StdOut.print(i.next());
            StdOut.print("  ");
        }
        StdOut.println();
    }

}

}

Answer 1

您错过了几次操作。在 addFirst 中，您没有设置 oldFirst.prev = first;，因此，如果您用它添加节点，则不会有任何 prev定义的引用文献。这就是 removeLast 失败的原因。它尝试清理对 last.prev 的遍历，但由于所有内容都是使用 addFirst 添加的，因此 last.prev 为 null。

此外，在 removeFirst 中，您也遇到了类似的问题，即您没有删除到前一个 prev 节点的链接，例如 first.prev = null; 如果不这样做，如果您使用 prev 引用进行遍历，则在调用 removeFirst 之后，您将能够超越第一个节点。

addLast 和 addFirst 本质上应该做完全相同的事情，只是在列表的不同末端。在您的实现中，addFirst 看起来更简单，这意味着您错过了 addFirst 中的某些内容，或者 addLast 过于复杂。在这种情况下，您错过了 addFirst 中的某些内容。与删除方法相同。