Delete node in Doubly Linked List

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Delete a node from doubly linked list given a pointer to it.

Algorithm

1node.prev.next = node.next (if prev exists). node.next.prev = node.prev (if next exists).
2Handle head/tail edge cases.

Common Pitfalls

•O(1) deletion if pointer given. Update both prev and next neighbor pointers.

Delete node in Doubly Linked List.java

Java

// Approach: Find the node with the given value, then update prev and next pointers to bypass it.
// Time: O(n) Space: O(1)
//Definition for doubly Link List Node
class Node {
    int data;
    Node next;
    Node prev;

    Node(int x) {
        data = x;
        next = null;
        prev = null;
    }
}

class Solution {
    public Node deleteNode(Node head, int x) {
        if (head == null)
            return null;

        if (x == 1)
            return head.next;

        Node curr = head;

        for (int i = 1; i < x; i++)
            curr = curr.next;

        if (curr.next == null) {
            curr = curr.prev;
            curr.next = null;
        } else
            curr.prev.next = curr.next;

        return head;
    }
}

Was this solution helpful?