TAGS :Viewed: 8 - Published at: a few seconds ago

[ Exception in thread "main" java.lang.NullPointerException error - Eclipse Java linked lists ]

I'm creating a Stack Data Structure and am implementing it using a Linked List. I am using 3 java files - stack.java, stacktest.java and linkedList.java. The linked list works fine when I test it but the stack test is giving me the following errors

Is Empty?: true
Is Empty?: false
Exception in thread "main" java.lang.NullPointerException
    at Stack.Peek(Stack.java:56)
    at StackTest.main(StackTest.java:12)

Here is my stack.java file

 import java.util.EmptyStackException;

public class Stack{

    linkedList list;
    int count;

    public Stack()
    {
        list = new linkedList();
        count = 0;
    }

    /**
     * Adds a node to the head of the list
     * @param c character to add
     */
    public void Push(char c)
    {
        if(list.isEmpty())
        {// If the list is empty
            list.addFirst(c); // Add first
            count++;
        }
        else
        {
            list.addAtEnd(c); // To the end (tail acts as head)
            count++;
        }
    }

    /**
     * Removes a node from the head of the list
     * @return char removed node
     */
    public char Pop() throws EmptyStackException 
    {
        if (!isEmpty())
        {
            return list.removeLast();
        }
        else
        {
            throw new EmptyStackException();
        }
    }

    /** 
     * Returns the char from the head of the list
     * @return char from top of the list
     */
    public char Peek() throws EmptyStackException 
    {
        if (!isEmpty())
        {
            return list.getTail().ch;
        }
        else
        {
            throw new EmptyStackException();
        }
    }

    /**
     * Is the list empty?
     * @return true=yes false=no
     */
    public boolean isEmpty()
    {
        return list.isEmpty();
    }

    /**
     * Counts number of nodes within the list
     * @return int # nodes in list
     */
    public int getCount()
    {
        int counter = 0;
        Node temp = list.getHead(); // Get head pointer.
        while(temp.next != null) // Iterate until tail is reached.
            counter++; // Increment counter on each node
        return counter;
    }

    public void printStack()
    {
        list.printList();
    }
}

My stacktest.java

   import java.io.IOException;

public class StackTest {

    public static void main(String args[]) throws IOException
    {
    Stack stackList = new Stack();
    System.out.println("Is Empty?: " + stackList.isEmpty());
    stackList.Push('A');
    System.out.println("Is Empty?: " + stackList.isEmpty());
    stackList.Pop();
    stackList.Peek();
    stackList.isEmpty();
    stackList.getCount();
    stackList.printStack();

    }

}

And my linkedList.java

    class Node
{
    protected char ch;
    protected Node next;
    protected Node previous;

    /**
   * Construct a node with the given character value 
   * @param c - The character 
    */
    public Node (char c)
    {
        this.ch = c;
        this.next = null;
        this.previous = null;
    }
}   

public class linkedList
{  /** A reference to the head of the list */
    protected Node head;
    protected Node tail;
    /**
   * Construct a new empty list 
    */
    public linkedList()
    {
        head=null;
        tail=null;
    }

    public Node getHead()
    {
        return head;
    }

    public Node getTail()
    {
        return tail;
    }

/**
 *Set c as first node in the list
 *@param c The character to be inserted
 */
    public void addFirst(char c)
    {
        Node newNode = new Node(c);
        head=newNode; // Adding new element.
        tail=newNode; // Head and tail will be the same.
    }

    /**
 *Add a character to the end of the list 
 *@param c The character to be inserted
 */
    public void addAtEnd(char c)
    {
        Node nod = new Node(c);
        Node temp = head;
        while (temp.next != null) // cycle until at end of list.
            temp = temp.next;
        temp.next=nod; // last element is new node.
        nod.previous=temp; // linking last node with rest of list.
        tail=nod; // new node is the tail.
    }

    /**
     *Add a character in alphabetical order into the list 
     *@param c The character to be inserted
    */
    public void addInOrder(char c)
    {

        Node n= new Node(c);

        if(isEmpty())
        {
            addFirst(c);
        }
        else
        {
        Node pre=head;
        Node succ= head.next;
        if (n.ch < pre.ch)
            {
                n.next =head;// join node n to the list at the head.
                head = n;// head is reading from n.
            }
        else
        {

        while(succ!=null && n.ch > succ.ch)
        {   // find the position to insert the node
            pre = succ;
            succ = pre.next;

        }   //rearrange pointers    
       n.next = succ;
       pre.next = n;
        }
        }
    }
    /**
     *Test to see if this list is empty 
     *@returns true or false
    */  
    public boolean isEmpty()
    {
        return (head == null && tail == null);
    }


    /**
     *removes a node from the head of the list 
     *@returns c The character from the removed node
    */
    public char removeFirst() 
    {
        if(!isEmpty())
        {
    // a temporary pointer to enable return of the char being removed
            Node temp = head;
            head = head.next;   //  move head pointer along the list
            return temp.ch;
        }
        else 
        {
            System.out.println("List is empty");
            return '?'; //to indicate that the list is empty
        }
    }

    /**
     * removes a node from the tail of the list 
     * @return c The character from the removed node
     */
    public char removeLast()
    {
        Node t = getTail(); // Retrieve tail
        tail = t.previous; // Set tail to previous node
        return t.ch; // return character
    }

    /**
     *prints the characters in the list
    */
    public void printList()
    {
        Node temp=head;
        while(temp!=tail.next)
        {
            System.out.print(temp.ch + " ");
            temp=temp.next;
        }
        System.out.println(); // After print, goes to new line.
    }

}

I understand that I am using a variable which is null but can someone explain to me where I am going wrong

Answer 1


When you call addFirst(), it sets both the head and the tail to the new node. However, when you removeLast(), it only changes tail to null and leaves head set to the node you popped.

Then, when you call isEmpty(), since head is not null, it doesn't recognize that the list is empty and returns false.

You need to modify removeLast() to check whether you're removing the only element in the list, and update the head accordingly.

Answer 2


Once you have popped out your only element of the stack, the inner list is empty. Therefore list.getTail() will return null, and you cannot peek into your stack anymore.

Answer 3


In StackTest.java you are inserting one element into the stack, then popping it and then trying to peek into the stack. Your pop function is using removeLast method of linkedList.java. While you are correctly pointing the tail to tail.previous, you need to also check if the result of this leads to tail becoming null (which means you have removed the last element in your linked list). You should check for this in removeLast and make head = tail if this is the case:

public char removeLast()
{
    Node t = getTail(); // Retrieve tail
    tail = t.previous; // Set tail to previous node
    if(tail == null){
        head = tail;
    }
    return t.ch; // return character
}

This way isEmpty() method will always return true if you have popped out the last element in the list. You will have to make a similar change to removeFirst() as follows:

public char removeFirst() 
{
    if(!isEmpty())
    {
// a temporary pointer to enable return of the char being removed
        Node temp = head;
        head = head.next;   //  move head pointer along the list
        if(head == null){
            tail = head;
        }
        return temp.ch;
    }
    else 
    {
        System.out.println("List is empty");
        return '?'; //to indicate that the list is empty
    }
}

After this change your peek() method will now throw an EmptyStackException (which is desirable) instead of a NPE when you try to peek into an empty stack. Might I also suggest that you don't need to traverse the whole list to add at the end of the list (on addAtEnd()). Since you already have the tail you can just append to the end of the tail pointer.