7.10: Linked List Node Delete

Delete Node 

We have looked at creating a linked list, and we have worked through inserting a new node into a linked list. Now we will work through deleting a node from the list.

To delete a node from linked list, we need to do following steps.
1) Find previous node of the node to be deleted.
2) Change the next of previous node.
3) Free memory for the node to be deleted.

In this instance we remove the node where C is the Data. This simply means we reset the B node Next value to point the the D node. Remember: the Next value is a memory pointer that points the the place in memory where the various structures exist. Then we release the memory, using the free() function,  location where the C node was.

The following code uses a struct instead of a Class, this allows you to see a slightly different way to implement linked lists. This is a fully implemented linked list using structures. Pay attention to the printList() function. Again, this is an example of walking across the list. Taking the head, which is the argument passed into this function, and seeing if it points to NULL. As long as it points to a valid address we print the Data member, and reset the node pointer to the current Next, then go back to the while statement.

// A complete working C program to demonstrate deletion in singly 
// linked list 
#include <iostream>
using namespace std; 

// A linked list node 
struct Node 
{ 
    char data; 
    struct Node *next; 
}; 

/* Given a reference (pointer to pointer) to the head of a list 
and a char, inserts a new node on the front of the list. */
void push(struct Node** head_ref, char new_data) 
{ 
    struct Node* new_node = new Node; 
    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 

/* Given a reference (pointer to pointer) to the head of a list 
and a key, deletes the first occurrence of key in linked list */
void deleteNode(struct Node **head_ref, char key) 
{ 
    // Store head node 
    struct Node* temp = *head_ref, *prev; 
    // If head node itself holds the key to be deleted 
    if (temp != NULL && temp->data == key) 
    { 
        *head_ref = temp->next; // Changed head 
        delete(temp);             // free old head memory
        return; 
    } 
    
    // Search for the key to be deleted, keep track of the 
    // previous node as we need to change 'prev->next' 
    while (temp != NULL && temp->data != key) 
    { 
        prev = temp; 
        temp = temp->next; 
    }
    
    // If key was not present in linked list 
    if (temp == NULL) 
       return; 
     // Unlink the node from linked list 
     prev->next = temp->next; 
     delete(temp); // Free memory 
} 

// This function prints contents of linked list starting from 
// the given node 
void printList(struct Node *node) 
{ 
    while (node != NULL) 
    { 
        cout << node->data; 
        node = node->next; 
    } 
    cout << endl;
} 

/* Main to test above functions*/
int main() 
{ 
    /* Start with the empty list */
    struct Node* head = NULL; 
    
    push(&head, 'A'); 
    push(&head, 'B'); 
    push(&head, 'C'); 
    push(&head, 'D'); 
    
    cout << "Created Linked List: " << endl; 
    printList(head); 
    deleteNode(&head, 'B'); 
    cout << "Linked List after Deletion of 'C': " << endl; 
    printList(head); 
    return 0; 
}

Output:

Created Linked List: 
DCBA
Linked List after Deletion of 'C': 
DCA 

Adapted from:
"Linked List | Set 3 (Deleting a node)" by mlv, Geeks for Geeks is licensed under CC BY-SA 4.0