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

Andreas Andreas · Accepted Answer · 2018-04-06T20:15:00

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;
    }
}

deleting from doubly linked list - java

1 Answers