deleting from doubly linked list - java

Question

I'm trying to better undserstand my teachers notes on how to delete a node from a doubly linked list, what she had on the boards is

 public void deleteNode(Node D){
 Node current = head;
 while(current.data != D.data && current.next != null){
  current = current.next;
   }
  d.prev.next = d.next;
  d.next.prev = current.prev.
 }

I can't help but feel like this isn't enough to remove a node. I was thinking maybe she meant

current.prev.next = d.next and
current.next.prev = d.prev

Once I figure out how to understand this better would it make sense if I wanted to delete a node from the middle by doing

public void deleteMiddle(){
    Node current = head;
    int i = 0;
    while(i < size/2){
        current = current.next;
        i++;
    }
    deleteNode(current);
}

The deletion of node from a doubly-linked list can be done in O(1). There is no need to iterate at all. This is one of the huge advantages of a doubly-linked list over a singly linked list. — MFisherKDX
– MFisherKDX, Commented Apr 6, 2018 at 20:13

Andreas · Accepted Answer · 2018-04-06 20:15:00Z

3

The correct way would be to either pass in the value, i.e. the data, or to make the method private, to protect against misuse.

Or do both:

public void deleteNode(int data) {
    Node current = head;
    while (current != null && current.data != data) {
        current = current.next;
    }
    deleteNode(current);
    // Note: We silently do nothing if 'data' not found
}
private void deleteNode(Node node) {
    if (node != null) {
        // Here we can rely on 'node' actually being in our list
        if (node.prev != null)
            node.prev.next = node.next;
        else
            head = node.next;
        if (node.next != null)
            node.next.prev = node.prev;
        else
            tail = node.prev;
    }
}

answered Apr 6, 2018 at 20:15

Andreas

160k13 gold badges164 silver badges262 bronze badges

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

6 Comments

MFisherKDX Over a year ago

I want to point out for the OP that Andreas's first function takes a value iterates through the list to find the node, and deletes the node. The second function takes a node and simply deletes it without iterating. Thus the complexity of the first function is O(N) and the complexity of the second is O(1).

MFisherKDX Over a year ago

However, I do not necessarily agree with his assertion that the "correct" way is to make the function private. I would say it depends on use case.

alwaysquestioning Over a year ago

Awesome thanks you! I don't know why I have a hard time visualizing the Linked list structures, it seems like the only data structure I struggle with but this cleared it up thank you

alwaysquestioning Over a year ago

@Andreas but so to target my last question, if I wanted to just delete the middle node( got this question wrong on my test haven't had time to see her since) would I do something similar to what I did in the original posting?

alwaysquestioning Over a year ago

@MFisherKDX so you're saying it would me more concise to use the second function if I knew EXACTLY which node i wanted to delete, and the first function is more for if I only knew the value of the node?

|

Collectives™ on Stack Overflow

deleting from doubly linked list - java

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related