doubly linked list remove first occurrence method

Question

Would anyone be able to help me write a removeFirstOccurrence method for this doubly linked list?

It removes the node having the first occurrence of the target data. The search starts at the head. If the target data is not in the list, then the list remains unchanged. The next field of the last node has value null. There is no tail reference.

public class DoublyLinkedList {

    protected Node head; // Note there is no tail reference.
    public void addToFront(String data) {
        head = new Node(data, head, null);
        if(head.next != null) {
            head.next.previous = head;
        }

    public void removeFirstOccurrence(String data) { 
    }

    protected class Node {
        protected String data;
        protected Node next;
        protected Node previous;
        private Node(String data, Node next, Node previous) {
            this.data = data;
            this.next = next;
            this.previous = previous;
        }
        private Node(String data) {
            this(data, null, null);
        }
    } // end of Node class 
} // end of DoublyLinkedList class

so far I wrote something like this but I am getting a null pointer exception when removing a string that isn't on the list. I have marked where the NPE occurs. if you can help figure out why or if you have a completely different method that works thats OK too just let me know, thanks!

public void removeFirstOccurance(String data) {
    if (data.equals(null)) {
        throw new java.lang.IllegalArgumentException("Data is null");
    }
    if (head == null) {
        throw new java.util.NoSuchElementException("List is empty");
    }

    Node current = head;
    if (current.data.equals(data)) {
        head = current.next;
    } else {
        boolean found = false; //keeps track if we found the element
        while (current != null && !found) {
            if (current.next.previous == null) { //NPE here
                current.next.previous = current;
            }
            current = current.next;
            if (current.data.equals(data)) {
                found = true;
                if (current.next == null) {
                    current.previous.next = null;
                } else {
                    current.previous.next = current.next;
                }
            }
        }
    }
}

Answer 1

You're not testing the current.next in your loop before accessing its values. So, when reaching the end of your list, the exception occurs.

while (current != null && !found) { // testing current
    if (current.next.previous == null) { // accessing current.next + testing current.next.previous
        current.next.previous = current;
    }
    // your loop
}

Note: It looks like work assignment so I will not post code.

Answer 2

Just some hints because I don't even have Java installed in this machine in order to check the code.

I'd suggest you to focus on what you have to do: find the first occurence. Then, once you have found it: update the pointers of the previous and following nodes.

E.g. it seems to me that you are forgetting to update the current.previous pointer of current.next when you check if the data is in the first node. In that way you won't actually delete the node..

So, my approach would be to have something like

while(!current.data.equals(data) && current.next != null){
    current = current.next; // looking through the list
}

Then, carefully checking that you haven't reached the end of the list, update the pointers so that

current.previous.next = current.next;
current.next.previous = current.previous;

Note also that if it's just for the sake of copying a value, you don't need to treat null as something special. I mean that in your last if:

if (current.data.equals(data)) {
                found = true;
                if (current.next == null) {
                    current.previous.next = null;
                } else {
                    current.previous.next = current.next;
                }
            }

you can simply assign current.previous.next = current.next;

Hope that helped.

Answer 3

This would be my reasoning in helping you find your bug. The null pointer exception is happening when evaluating current.next.previous. Your previous line ensures that current != null. Therefore it is likely that current.next is the null value. An easy way to test this is to add assert current.next != null before you use the value. If this theory is correct an assertion exception will be thrown at that point. You can then start examining your other code to find out why current.next might be null at that point.

As a programming tip, I recommend you use a lot of assert statements. They will save you a lot of pain in the long term. They are also good tips to others reading the code about what conditions you are assuming are true at each point.