0

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!

0

1 Answer 1

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

Sign up to request clarification or add additional context in comments.

1 Comment

Thank you! I was sure it was something really simple but for the life of me couldn't figure it out.

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.