Delete the node with value X of a Linked List

Problem Statement: Given a linked list, delete the node with value X of the linked list and print the updated linked list.

Examples

Example 1:
Input Format: 0->1->2, val = 1
Result: 0->2

Explanation: The value 1 can be found at the second position in the linked list, therefore we get this result after deleting that node.
Example 2:
Input Format: 12->5->8->7, val = 3
Result: 12->5->8->7
Explanation: The value 3 is not present in the list, therefore, the result is the same as the original linked list.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach:

The simple idea to solve this problem is to traverse the linked list and check if the data at the current node is equal to the value. If a match is found, delete this node and point the previous node to the next node. If the traversal has been completed, this means there is no node with data equal to value, therefore, the linked list remains the same.

Algorithm:

To start the problem, initialize a pointer temp to the head of the list and a pointer prev to null. The temp pointer will be used to traverse the list, and the prev pointer will keep track of the previous node that the temp pointer is pointing to.

Traverse the linked list until the data at the current node matches the value. There are 2 cases to consider:

If a match is found, point the previous node to the node after the current node, and free up the memory occupied by the current node, effectively deleting the node.
If the traversal is complete, this means no match was found, therefore, no changes are made in the linked list.
Note: In the case of languages like Java, Python, and Javascript, there is no need for the deletion of objects or nodes because these have an automatic garbage collection mechanism that automatically identifies and reclaims memory that is no longer in use.

Thus, the updated linked list looks like this:

Code:

C++ Code

// Definition of a Node in a linked list
class Node {
public:
    int data;
    Node* next;

    // Constructor with both data and next pointer
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data sets next to nullptr
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};

// Function to print the linked list
void printLL(Node* head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}

// Function to delete a node with a specific value in a linked list
Node* deleteVal(Node* head, int val) {
    // Check if the list is empty
    if (head == NULL)
        return head;

    // If the first node has the target value, delete it
    if (head->data == val) {
        Node* temp = head;
        head = head->next;
        delete (temp);
        return head;
    }

    // Traverse the list to find the node with the target value
    Node* temp = head;
    Node* prev = NULL;

    while (temp != NULL) {
        if (temp->data == val) {
            // Adjust the pointers to skip the node with the target value
            prev->next = temp->next;
            // Delete the node with the target value
            delete temp;
            break;
        }
        prev = temp;
        temp = temp->next;
    }

    return head;
}

int main() {
    // Create a linked list from a vector
    vector<int> arr = {0, 1, 2};
    int val = 1;
    Node* head = new Node(arr[0]);
    head->next = new Node(arr[1]);
    head->next->next = new Node(arr[2]);

    // Delete the node with the target value in the linked list
    head = deleteVal(head, val);

    // Print the modified linked list
    printLL(head);

    return 0;
}

Output: 0 2

Time Complexity: O(N) worst case, when the value is found at the tail and O(1) best case, when the value is found at the head.

Space Complexity: O(1), as we have not used any extra space.

Java Code

class Node {
    public int data;
    public Node next;

    // Constructor with both data and next pointer
    public Node(int data1, Node next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data, sets next to null
    public Node(int data1) {
        data = data1;
        next = null;
    }
}

public class LinkedListExample {
    // Function to print the linked list
    static void printLL(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }

    // Function to delete a node with a specific value in a linked list
    static Node deleteVal(Node head, int val) {
        // Check if the list is empty
        if (head == null)
            return head;

        // If the first node has the target value, delete it
        if (head.data == val) {
            Node temp = head;
            head = head.next;
            temp = null;
            return head;
        }

        // Traverse the list to find the node with the target value
        Node temp = head;
        Node prev = null;

        while (temp != null) {
            if (temp.data == val) {
                // Adjust the pointers to skip the node with the target value
                prev.next = temp.next;
                // Delete the node with the target value
                temp = null;
                break;
            }
            prev = temp;
            temp = temp.next;
        }

        return head;
    }

    public static void main(String[] args) {
        // Create a linked list
        int[] arr = {0, 1, 2};
        int val = 1;
        Node head = new Node(arr[0]);
        head.next = new Node(arr[1]);
        head.next.next = new Node(arr[2]);

        // Delete the node with the target value in the linked list
        head = deleteVal(head, val);

        // Print the modified linked list
        printLL(head);
    }
}

Output: 0 2

Time Complexity: O(N) worst case, when the value is found at the tail and O(1) best case, when the value is found at the head.

Space Complexity: O(1), as we have not used any extra space.

Python Code

class Node:
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node

# Function to print the linked list
def printLL(head):
    while head is not None:
        print(head.data, end=" ")
        head = head.next
    print()

# Function to delete a node with a specific value in a linked list
def deleteVal(head, val):
    # Check if the list is empty
    if head is None:
        return head

    # If the first node has the target value, delete it
    if head.data == val:
        temp = head
        head = head.next
        temp.next = None  # Disconnect the deleted node
        return head

    # Traverse the list to find the node with the target value
    temp = head
    prev = None

    while temp is not None:
        if temp.data == val:
            # Adjust the pointers to skip the node with the target value
            prev.next = temp.next
            # Delete the node with the target value
            temp.next = None  # Disconnect the deleted node
            break
        prev = temp
        temp = temp.next

    return head

# Create a linked list
arr = [0, 1, 2]
val = 1
head = Node(arr[0])
head.next = Node(arr[1])
head.next.next = Node(arr[2])

# Delete the node with the target value in the linked list
head = deleteVal(head, val)

# Print the modified linked list
printLL(head)

Output: 0 2

Time Complexity: O(N) worst case, when the value is found at the tail and O(1) best case, when the value is found at the head.

Space Complexity: O(1), as we have not used any extra space.

JavaScript Code

class Node {
    constructor(data, next) {
        this.data = data;
        this.next = next;
    }
}

// Function to print the linked list
function printLL(head) {
    while (head !== null) {
        console.log(head.data + " ");
        head = head.next;
    }
}

// Function to delete a node with a specific value in a linked list
function deleteVal(head, val) {
    // Check if the list is empty
    if (head === null)
        return head;

    // If the first node has the target value, delete it
    if (head.data == val) {
        let temp = head;
        head = head.next;
        temp.next = null;  // Disconnect the deleted node
        return head;
    }

    // Traverse the list to find the node with the target value
    let temp = head;
    let prev = null;

    while (temp !== null) {
        if (temp.data == val) {
            // Adjust the pointers to skip the node with the target value
            prev.next = temp.next;
            // Delete the node with the target value
            temp.next = null;  // Disconnect the deleted node
            break;
        }
        prev = temp;
        temp = temp.next;
    }

    return head;
}

// Create a linked list
let arr = [0, 1, 2];
let val = 1;
let head = new Node(arr[0]);
head.next = new Node(arr[1]);
head.next.next = new Node(arr[2]);

// Delete the node with the target value in the linked list
head = deleteVal(head, val);

Output: 0 2

Time Complexity: O(N) worst case, when the value is found at the tail and O(1) best case, when the value is found at the head.

Space Complexity: O(1), as we have not used any extra space.

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Neerav Sethi for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article