delete node after specified node in doubly linked list. (recursively)

Question

I have this recursive function that is supposed to delete the node that comes after the specified one in a doubly linked list. However My method Isn't deleting anything. I am having trouble with rearranging the values in the list. Any ideas?

private void deleteAfterThis(T data, Node headAux) {
    if(headAux == null) {
        return;
    }

    Node deleteAfter = new Node(data);
    Node target = deleteAfter.next;
    if(target == null) {
        return;
    }

    if(deleteAfter.prev == null){
        if(target != tail && target==headAux) {
            deleteAfter.next = target.next;
            target.next.prev = deleteAfter;
            size--;
            deleteAfterThis(data, headAux.next);
        }

        else if(target == tail && target == headAux) {
            deleteAfter.next = null;
            deleteAfter = tail;
            size--;
            return;
        }
    }

    else if(deleteAfter.prev != null) {
        if(target != tail && target == headAux) {
            deleteAfter.next = target.next;
            target.next.prev = deleteAfter;
            size--;
            deleteAfterThis(data, headAux.next);
        }
        else if( target == tail && target == headAux) {
            deleteAfter.next = null;
            deleteAfter = tail;
            size--;
            return;
        }
    }

    deleteAfterThis(data, headAux.next);

}

wLui155 · Accepted Answer · 2020-12-17 19:56:46Z

1

One mistake I see right off the bat is that you should not be creating a completely new node for deleteAfter. Intuitively, does it make sense to have to create a new node when attempting to delete one? I'll assume that, even knowing what the constructor for Node actually looks like, it sets the next and prev pointers to nodes to null. As a result, you'll keep recursively updating headAux until it's null without ever deleting anything. It seems what you want deleteAfter to be is headAux.next.

Another bug I see is that you've copy and pasted your checking logic twice - I recommend stepping through both cases and verifying if the logic should be identical within each block of the if and else-if blocks (it probably shouldn't).

Stepping into the logic, you should realize that the prev node of the current (headAux in your code) would be null only if headAux is the head of the list. Thus, it would be a bit more clear to rewrite the headAux.prev check as verifying if headAux is equal to the head of the linked list.

Looking at the actual deletion logic, it seems to make sense in the general case to me (assuming the fact that deleteAfter is the next node of headAux as stated above). You're making the prev of the node to be deleted to point to the deleted node's prev node and the next of the previous node (after having set the pointer, which I'm not too big of a fan of but it works) point to deleteAfter.

Lastly, when you do actually locate the node you'd like to delete, you probably shouldn't be calling the recursive function again. You already handle the setting of pointers correctly, so there shouldn't be a need to do so.

I would highly recommend you (re-)draw a sample use-case of your circular linked list and perform deletion on a sheet of paper before jumping to coding the edgecases (which aren't all handled here). The edge cases you should probably be aware of are the following: empty list, deleting head, deleting tail, single-node list. In your code, it seems that you did try to handle the deletion of the head (you'd have to remember to set the head afterwards). After getting that to work, making deletion work on other cases should be a breeze.

edited Dec 17, 2020 at 19:56

answered Dec 17, 2020 at 19:36

wLui155

7325 silver badges11 bronze badges

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

4 Comments

user14846068 Over a year ago

Thanks for your suggestions! I also think that I need to clarify that I'm supposed to be removing the node that comes after the one with the specified data element. That's why I thought I had to keep track of the node that contains that data via a new node. But now I'm not sure how to check if the node with the specified data is even in the list

wLui155 Over a year ago

Oh, thanks for clarifying! Your logic seems to make a bit more sense then. What you should do in that case is check if the existing next node contains the specified data instead of creating a new node. If the next node does not contain it, then you'd call your recursive function to continue onwards. You're handling the base case correctly, and if the current node headAux is null, you terminate without having done anything.

user14846068 Over a year ago

Ok so I've updated my method. I thought it would make more sense to just go down the list and see if the parameter node 's data is equal to the specified data and then delete. private void deleteAfterThis(T data, Node headAux) { if(headAux == null) { return; } if(headAux.data == data){ if(headAux.next != null) { headAux.next = headAux.next.next; size--; deleteAfterThis(data, headAux.next); } } deleteAfterThis(data, headAux.next); }

wLui155 Over a year ago

Hmm... it's kinda hard to read the code without formatting but it's almost correct. Since you're working with a double linked list, you need to make sure that the node after the deleted one has a prev pointer back to headAux. I suppose that your intention is to perform this 'node after' deletion for any node containing data, so what you must can do is remove the call deleteAfterThis after deleting, as you're calling the recursive function too many times. Other than that, you just need to add in special logic for the edge cases (deleting the tail for example).

Collectives™ on Stack Overflow

delete node after specified node in doubly linked list. (recursively)

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related