Java delete node linked list not working

Question

I had a working method for deleting a node in a linked list given the key. That was when I had my Node class nested in my LinkedList class and I could access the members of the node class directly (for e.g. head.next and head.data). I refactored the code to have a separate Node class and set the accessor and mutator methods for the data and next members. (I'm preparing for an interview, so I am working on many linkedlist problems, so I thought having a separate class makes it so that I don't have to copy and paste a lot of code.

Here is my Node.java:

package linkedlistproblems;

public class Node {
    private int data;
    private Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

My method for deleting a node from LinkedList.java:

// delete node with key = data
public void deleteNode(int data) {
    System.out.println("Deleting node with key = " + data);
    if (head == null) {
        System.out.println("Linked list does not contain key = " + data);
        return;
    }
    else if (head.getData() == data) {
        Node temp = head;
        head = head.getNext();
        nElements--;
        temp = null;
    }
    else {
        Node n1 = head;
        Node n2 = head.getNext();
        while(n2 != null) {
            if (n2.getData() == data) {
                n1.getNext().setNext(n2.getNext());
                nElements--;
                break;
            }
            n1 = n1.getNext();
            Node temp = n2;
            n2 = n2.getNext();
            temp = null;
        }
        if (n2 == null)
            System.out.println("Linked list does not contain key = " + data);
    }
}

This method does not work. It gets in the if after checking for the data, but does not delete the node.

Here is the old method which worked:

// delete node with key = data
public void deleteNode(int data) {
    System.out.println("Deleting node with key = " + data);
    if (head == null) {
        System.out.println("Linked list does not contain key = " + data);
        return;
    }
    else if (head.data == data) {
        Node temp = head;
        head = head.next;
        nElements--;
        temp = null;
    }
    else {
        Node n1 = head;
        Node n2 = head.next;

        while (n2 != null) {
            if (n2.data == data) {
                n1.next = n2.next;
                nElements--;
                break;
            }
            n1 = n1.next;
            Node temp = n2;
            n2 = n2.next;
            temp = null;
        }

        if (n2 == null) 
            System.out.println("Linked list does not contain key = " + data);
    }
}

And here is the main method to test the code:

public static void main(String[] args) {
    LinkedList ll = new LinkedList();
    ll.add(70);
    ll.add(10);
    ll.add(55);
    ll.add(22);
    System.out.println("Original List: " + ll);
    ll.deleteNode(70);
    System.out.println(ll);
    ll.deleteNode(22);
}

I have overridden the toString method to pretty print the linked list (not shown here). I am not sure why the refactored method which makes use of the accesssor mutators is not working.

Output:

Original List: 70 ---> 10 ---> 55 ---> 22 ---> NULL
Deleting node with key = 70
10 ---> 55 ---> 22 ---> NULL
Deleting node with key = 22
10 ---> 55 ---> 22 ---> NULL
10 ---> 55 ---> 22 ---> NULL

Also, whenever I delete a node, I assign it to temp, remove it from the list and assign the temp to null. This I do to prevent loitering. Am I doing this right?

Thanks for your help!

Answer 1

The logic of the original line

n1.next = n2.next;

Does not match the new implementation

n1.getNext().setNext(n2.getNext());

It would be the equivalent of

n1.next.next = n2.next;

from the original implementation