Implementing Doubly Linked List from scratch, error in remove() method

Question

I was trying to learn to implement Doubly Linked List in java just as an exercise. but I am stuck at remove() method.

The contents of the list are,

1 2 3 4

When I try to remove the element which is not present.It shows the NullPointerException at line no. 21 instead of printing not found.

The other codes that I saw was a little complicated and different from what I am doing. The method is,

 void remove(int data){
    Node n = head;
    if(head==null)
        System.out.println("Not Found");
    else if(head.d==data){
        if(head==tail){
            head=null;
            tail=null;
        }
        else{
            head=head.next;
            head.prev=null;
        }
    }
    else{
        while(n!=null && n.d==data){
            n=n.next;
        }
        if(n==tail){
            tail=tail.prev;
            tail.next=null;
        }
        else if(n!=null){
            n.prev.next=n.next;
            n.next.prev=n.prev;
        }
        if(n==null)
            System.out.println("Not Found");
    }
}

So my Question is, Am I doing it completely wrong? OR what is the problem? Pardon me if it's just too foolish.

Does it give the NullPointerException for every input or just for some inputs? What is the content of the list and what is the input when it gives you the exception? — RealSkeptic
– RealSkeptic, Commented Jan 1, 2016 at 14:09
Can you please post exact stacktrace to help us reach to conclusion bit faster? — Aaditya Gavandalkar
– Aaditya Gavandalkar, Commented Jan 1, 2016 at 14:16

4 revs, 2 users 78% · Accepted Answer · 2016-01-02 18:43:54Z

2

The problem is with search logic. In the while loop condition "n.d == data" is incorrect. It should be "n.d != data" i.e.

while(n!=null && n.d==data){
n=n.next;
}

Should be:

...

    while(n!=null && n.d != data){
        n=n.next;
    }

Here is a much cleaner implementation :

public void remove(int data) { // Head is not required in param, should be field variable
    Node ptr = head;

    while(ptr!=null && ptr.data != data) // search for the node
    {
        ptr = ptr.next;
    }

    if(ptr == null) {
        System.out.println("Not Found");
        return;
    }

    if(ptr.prev == null) {// match found with first node
        head = ptr.next;
    }
    else{
        ptr.prev.next = ptr.next;
    }
    if(ptr.next == null){// match found with last node
        tail = ptr.prev;
    }
    else{
        ptr.next.prev = ptr.prev;
    }       
}

edited Jan 2, 2016 at 18:43

community wiki

4 revs, 2 users 78%
raj kumar

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

3 Comments

itishrishikesh Over a year ago

If the Node to be remove is last then it will be the tail node and if block above else if mentioned in the answer I think does that. I am not sure if I am stating it correct or I am just misunderstanding your statements.

raj kumar Over a year ago

Probably my bad. Modified the answer. Check if it helps. BTW, you modified the question i guess. Earlier there was a parameter 'Node head' (which you should not do otherwise you can not change the head reference) (Y)

itishrishikesh Over a year ago

won't the method you suggested, cause unnecessary loop cycles

lucky · Accepted Answer · 2016-01-01 14:12:24Z

0

void remove(Node head, int value) {
    if (head == null) {
        System.out.println("Not Found");
    } else if (value == head.d) {
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
    } else {
        Node n = head.next;
        while (n != null && value != n.d) {
            n = n.next;
        }
        if (n == tail) {
            tail.next = null;
            tail = tail.prev;
        } else if (n != null) {
            n.prev.next = n.next;
            n.next.prev = n.prev;
        }
    }
}

answered Jan 1, 2016 at 14:12

lucky

1641 silver badge5 bronze badges

1 Comment

itishrishikesh Over a year ago

I am enable to figure out, What has happened? By just interchanging line no. 21 and line no. 22. And even after not showing NullPointerException. It does not tell when the element is not present, Unless the list is empty.

Collectives™ on Stack Overflow

Implementing Doubly Linked List from scratch, error in remove() method

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related