2

I am trying to learn data structure, but I ran into the dreaded NullPointerException and I am not sure how to fix it.

My SinglyLinkedList<E> class implements an interface, LinkedList, where I redefined some methods like, add(), get(), contains(), and more.

The NullPointerException happens when I use the clear() method. It points at the method removeLast() under nodeBefore.setNext(null). It also points to the clear() method under remove(head.getElement()).

Also, if there is anything I can improve upon in my code please let me know.

public class SinglyLinkedList<E> implements LinkedList<E> {

    private class Node<E> {

        public Node<E> next;
        public E element;

        public Node(E element) {

            this.element = element;
        }

        public Node (E element, Node<E> next) {

            this.element = element;
            this.next = next;
        }

        public E getElement() {

            return element;
        }

        public Node<E> getNext() {

            return next;
        }

        public void setElement(E element) {

            this.element = element;
        }

        public void setNext(Node<E> next) {

            this.next = next;
        }

        public String toString() {

            return ("[" + element + "] ");
        }
    }

    public Node<E> head;
    public Node<E> tail;
    public int total;      

    public SinglyLinkedList() {

        this.head = null;
        this.tail = null; 
        this.total = 0;
    }

    public E get(int index) {

        if (index < 0 || index > size()) {
            return null;
        }

        if (index == 0) {
            return head.getElement();
        }

        Node<E> singly = head.getNext();

        for (int i = 1; i < index; i ++) {

            if (singly.getNext() == null) {
              return null;
            }       

            singly = singly.getNext();      
        }

        System.out.println("\n" + singly.getElement());

        return singly.getElement(); 
    }

    public void add(E element) {
        Node<E> singlyAdd = new Node<E>(element);

        if (tail == null) {
            head = singlyAdd;
            tail = singlyAdd;
        } else {
            tail.setNext(singlyAdd);
            tail = singlyAdd;
        }     

        total++;
    }             

    public void display() {
        if (head == null) {
            System.out.println("empty list");
        } else {
            Node<E> current = head;
            while (current != null) {
                System.out.print(current.toString());
                current = current.getNext();
            }
        }

    }

    public boolean contains(E data) {

        if (head == null) {
            return false;
        }

        if (head.getElement() == data) {
            System.out.println(head);
            return true;                                
        }

        while (head.getNext() != null) {
            head = head.getNext();

            if (head.getElement() == data) {
                System.out.println(head);                
                return true;                               
            }             

        } 

        return false;         
    }       

    private Node<E> removeFirst() {
        if (head == null) {
            System.out.println("We cant delete an empty list");
        }    

        Node<E> singly = head;            
        head = head.getNext();
        singly.setNext(null);
        total--;

        return singly;     
    } 

    private Node<E> removeLast() {

        Node<E> nodeBefore;
        Node<E> nodeToRemove;     

        if (size() == 0) {
            System.out.println("Empty list");
        }    

        nodeBefore = head;

        for (int i = 0; i < size() - 2; i++) {
          nodeBefore = nodeBefore.getNext();
        }    

        nodeToRemove = tail;    

        nodeBefore.setNext(null);
        tail = nodeBefore;
        total--;

        return nodeToRemove;
    }       

    public E remove(int index) {      

        E hold = get(index);     

        if (index < 0 || index >= size()) {
            return null;
        } else if (index == 0) { 

            removeFirst();    
            return hold;
        } else {

            Node<E> current = head;
            for (int i = 1; i < index; i++) {                
                current = current.getNext();
            }  

            current.setNext(current.getNext().getNext());
            total--; 
            return hold;
        }       
    }       

    public int size() {
        return getTotal();
    }

    public boolean remove(E data) {      

        Node<E> nodeBefore, currentNode; 

        if (size() == 0) {
            System.out.println("Empty list");
        }            

        currentNode = head;

        if (currentNode.getElement() == data) {
            removeFirst();
        }

        currentNode = tail;
        if (currentNode.getElement() == data) {
            removeLast();
        }

        if (size() - 2 > 0) {
            nodeBefore = head;
            currentNode = head.getNext();
            for (int i = 0; i < size() - 2; i++) {
                if (currentNode.getElement() == data) {

                    nodeBefore.setNext(currentNode.getNext());
                    total--;
                    break;
                }

                nodeBefore = currentNode;
                currentNode = currentNode.getNext();
            } 
        } 

        return true;
    }

    public void clear() {

        while (head.getNext() != null) {    
            remove(head.getElement());    
        }

        remove(head.getElement());    
    }

    private int getTotal() {
        return total;
    } 
}
11
  • Is your code compiling? Commented Apr 18, 2015 at 7:14
  • The method remove(E) is undefined. Could you post its code as well? Commented Apr 18, 2015 at 7:14
  • @SMA is compiling fine. Everything works except the clear method. But it is compiling. Commented Apr 18, 2015 at 7:18
  • @Turing85 I left off a few methods so that it wont be too much to read. I can add the other methods if you want me to? Commented Apr 18, 2015 at 7:20
  • 2
    Is it not enough for clear() to release head and tail, set total to 0, and let the garbage collector take care of the rest? Like what your constructor does? Commented Apr 18, 2015 at 7:32

3 Answers 3

2

For your clear method, I don't see that you do any per element cleanup, and the return type is void, so all you want is an empty list. The easiest way is to simply clear everything, like in the constructor:

public void clear() {
    this.head = null;
    this.tail = null; 
    this.total = 0;
}

Another comment:

in contains, you do

while (head.getNext() != null) {
        head = head.getNext();

        if (head.getElement() == data) {
            System.out.println(head);                
            return true;                               
        }             
    } 

which may have two problems (where the first applies to the entire class),

  1. you compare with == data which compares references, where you probably want to compare values with .equals(data)

Edit: I.e. n.getElement().equals(data) instead of n.getElement() == data.

(Or, if n and data may be null, something like (data != null ? data.equals(n.getElement()) : data == n.getElement())

  1. you use the attribute head as the scan variable which modifies the state of the list. Do you really want that?
Sign up to request clarification or add additional context in comments.

3 Comments

Thank you very much! Can you elaborate on what I need to change on the contains method? Are you saying that I need to override the equals method?
@code check my answer for a link which elaborates the difference between == and equals.
@code no, simply use .equals instead of == if you want value comparison. Answer edited.
2

The problem arises when you delete the last element within clear: remove(head.getElement());. For some reason, you first remove the head and then the tail. But when calling removeLast, you use the head (which is already null). Within removeLast this is the line, which causes the NullPointerException: nodeBefore.setNext(null);. My advice would be to write the clear() method as @bali182 has suggested:

public void clear() {
    this.head = null;
    this.tail = head;
    this.total = 0;
}

One advice: if you are writing methods to search or delete entries, you should never use == when dealing with objects (or even better: don't use == at all when dealing with objects). You may want to read this thread.

Comments

0

From within clear method, you are calling remove(head.getElement()); meaning you are trying to call LinkedList's remove method. And since you are overriding each functionality and so is add, you don't maintain internal state of LinkedList and hence you get exception. Code in remove is:

    public boolean remove(Object o) {
    if (o==null) {
        for (Entry<E> e = header.next; e != header; e = e.next) {
            if (e.element==null) {

So here since you are not using functionality of LinkedList, header would be null and doing header.next would return NullPointerException.

6 Comments

OP is implementing a custum interface LinkedList. OP is not extending LinkedList. Therefore, OP does not have a method remove(E)
I don't think I understand? I already overridden my interface class method remove() and it works properly.
You implemented remove without any argument, but in reality you are calling it with one element remove(head.getElement());. So either you redefine remove method to accept one parameter or you change the call to remove without any argument.
@SMA remove(int) has an argument, but the wrong type. removeFirst() and removeLast() have no arguments. There is no method remove()
Your getElement returns a generic type element and not int public E getElement() { return element; }
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.