How would you remove a given node from a linked list?

To remove a specific node from a linked list, we first need to locate that node and then update the pointers accordingly. Here’s a high-level algorithm for deleting a node from a linked list:

- If the head node is the one to be deleted,

- Change the head pointer to the next of the current head.

- Else,

- Initialize a ‘previousNode‘ to point to the head node.

- Traverse the linked list until the target node is found or the end of the list is reached.

- Update the ‘next‘ value of the ‘previousNode‘ to point to the ‘next‘ value of the target node.

Suppose we have a singly linked list and we want to remove a node ‘n‘:

class Node {
    public int data;
    public Node next;
}

public void deleteNode(Node node, Node n) {
    if(node == n) {
        if(node.next == null) {
            System.out.println("There is only one node. The list can't be made empty ");
            return;
        }

        node.data = node.next.data;
        node.next = node.next.next;

        System.gc();

        return;
    }

    Node prev = node;
    while(prev.next != null && prev.next != n) {
        prev = prev.next;
    }

    if(prev.next == null) {
        System.out.println("Given node is not present in Linked List");
        return;
    }

    prev.next = prev.next.next;

    System.gc();
    return;
}

Visualizing the process can better help show how node removal occurs in linked lists:

1- Linked List before removal:

---> [HEAD| ]---> [ | ]---> [TARGET| ]---> [ | ]---> NULL

2- Linked List after removing target:

---> [HEAD| ]---> [ | ] ----------------> [ | ]---> NULL

For doubly linked lists, the algorithm is slightly more complex because we have to update the ‘previous‘ pointer of the node after the target node, but the overall concept is the same.

The time complexity for this operation is O(n) as at worst case, we need to traverse all elements in the linked list.