exception with java data structure

Question

I am writing a generic data structure that can add and delete from the first or last nodes I tested my code however I got exceptions in some certain way of input.

now if I addlast then addfirst then removelast i got exception

and when I addfirst many time without adding last then try to remove them by removelast() function i got exception but when I addlast many time without adding first then remove them by removefirst() it works

I am trying to avoid while loops here is the code

 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;
    }

} }

I believe I have something wrong with last.prev in removelast() since it is already null and then referred last = last.perv in remove() but i couldnt think of a way to link last to last node of first

can anyone help me with this

here is the main if you want to try...

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();
    }

}

}

"i got exception" --> Which exception (and also stacktrace)? "I am trying to avoid while loops" --> Why ? — jlordo

femtoRgon femtoRgon · Accepted Answer · 2013-02-26T18:51:20

You have missed a couple of operations. In addFirst you don't set oldFirst.prev = first;, so if you add nodes with it, you won't have any prev references defined. That is why removeLast fails. It attempts to clean traverse to last.prev, but since everything was added with addFirst, last.prev is null.

Also, in removeFirst, you have a similar issue, that you don't remove the link to the former prev node, such as first.prev = null; Without doing that, if you were traversing using prev references, you would be able to move beyond the first node, after having called removeFirst.

addLast and addFirst should do, in essence, exactly the same things, just at different ends of the list. addFirst looks simpler, in your implementation, which means either you missed something in addFirst, or addLast is overly complex. In this case, you missed something in addFirst. Same with the remove methods.

exception with java data structure

1 Answers