Linked List - Deletion (given a key)

Delete 3 in the linked list

1->2->3->5 to make it like 1->2->5

Solution:

1) Find the previous node and current node of the list to be deleted.

2) Make the next of the previous node to point to current->next.

Illustration:

Special cases:

i) If the head is null then return without any further operations.

ii) If the given key is in the head node itself then make the head to point to head->next.

iii) If we finished up to tail and the key is not present in the list then return.

Code:

void delete(int key){

    //case (i)

    if(head == null)

       return;

    //case (ii)

    if( head.data == key){

       head = head.next;

    }

    Node previous = head;

    Node current = head.next;

    while(current != null && current.data != key){

         prev = current;

         current = current.next; 

    }

    //case (iii)

    if(current == null) 

        return;

    

    prev.next = current.next;

       

}

Examples:

i) Delete 3 in  1->2->3->4

     Explanation:
    Initially previous points to head which is 1. Current points to head->next which is 2. While loop will continue since current->data which is 2 is not equal to 3. So previous will point to current which is 2 and current will point to current->next which is 3. The while loop will end here since current->data is 3 which is the terminating condition of while loop.Now the final step, 
previous->next will point to current->next which is 5.

ii) Delete 1 in 1->2->4


    Explanation:
     This is our case 2. Since head->data is key(1) we make head to point to head.next which is 2.

iii) Delete 4 in 2->4

     Initially previous points to 2 and current points to 3. While loop will be terminated since current->data is 3 which is equal to the key. So previous->next will point to current->next which is null.