Deletion in a Linked List

Deletion in a Linked List | Deleting a node from Linked List Data Structure.

Deletion in a Linked List | Deleting a Node from Linked List Data Structure

In this section, we'll explore how to delete a node from a linked list. Unlike arrays, where deleting an element requires shifting other elements, linked lists allow us to simply adjust pointers, making deletions more efficient.

Inserting in a linked list:

Consider the following Linked List:

Deletion in a linked list can be divided into the following categories:

Case 1: Deleting the First Node
In this case, we simply update the head pointer to point to the second node in the list. The original head node will be freed to release its allocated memory.

Case 2: Deleting a Node at a Specific Index
To delete a node at a particular index, we need to traverse the list to find the node just before the target node. We then adjust the pointers to skip the target node and free its memory.

Case 3: Deleting the Last Node
For this case, we traverse the list until we reach the second last node. We then set its next pointer to NULL and free the memory of the last node.

Case 4: Deleting a Node with a Given Value
To delete a node containing a specific value, we traverse the list to find the target node. We then adjust the pointers to bypass this node and free its allocated memory.

General Steps for Deletion

For each of the above cases, the general process involves:

Locating the Node: Navigate through the list to find the appropriate node to delete.
Adjusting Pointers: Update the pointers of the surrounding nodes to exclude the target node from the list.
Freeing Memory: Use the free() function to deallocate the memory associated with the deleted node.

By following these steps, we can efficiently manage the nodes in a linked list, ensuring that memory is appropriately allocated and deallocated as needed.

Syntax for freeing a node:

free(ptr);

The above syntax will free this node, that is, remove its reserved location in the heap.

Now, let's begin with each of these cases of insertion.

Case 1: Insert at the beginning:

In order to delete the node at the beginning, we would need to have the head pointer pointing to the node second to the head node, that is, head-> next. And we would simply free the node that’s left.

Case 2: Deleting at some index in between:

Assuming index starts from 0, we can delete an element from index i>0 as follows:

To delete the last node in the linked list, you will need a temporary pointer p that points to the node just before the last node.
Move the pointer p through the list until it reaches the second-to-last node (the one before the last node).
Once p is positioned correctly, you will set p->next to NULL, effectively removing the link to the last node.
Finally, free the memory associated with the last node to release the allocated space.

Case 3: Deleting at the end:

In order to delete an element at the end of the linked list, we bring a temporary pointer ptr to the last element. And a pointer p to the second last. We make the second last element to point at NULL. And we free the pointer ptr.

Case 4: Delete the first node with a given value:

Similar to the other cases, ptr can be deleted for a given value as well by following few steps:

p->next = givenVal-> next;
free(givenVal);

Since, the value 8 comes twice in the list, this function will be made to delete only the first occurrence.

Learning about the time complexity while deleting these nodes, we found that deleting the element at the beginning completes in a constant time, i.e O(1). Deleting at any index in between is no big deal either, it just needs the pointer ptr to reach the node to be deleted, causing it to follow O(n). And the same goes with case 3 and case 4. We have to traverse through the list to reach that desired position.

C Code For Deletion From Beginning, End, Specified Position & Key

Now that we have a thorough understanding of all the cases that we will encounter when deleting an existing node from a linked list, we can code each one in C language.

Before we code, let’s recall all the cases:

Deleting the first node -> Time complexity: O(1)
Deleting a node in between -> Time complexity: O(n)
Deleting the last node -> Time complexity: O(n)
Deleting the element with a given value from the linked list -> Time complexity: O(n)

Now, let's move on to the coding part. I have attached the snippet below. Refer to it while understanding the steps.

Understanding the snippet below:

You should have a good understanding of how to declare struct Nodes and traverse linked lists by now.
So, the first thing would be to create a struct Node and create the linkedlistTraversal function.
Do include the header file <stdlib.h>, since we’ll use malloc to reserve memory locations.
Similar to what we did in the insertion video, create four nodes. Request the memory location for each of these nodes from the heap via malloc. Link these nodes using the arrow operator.
This is how we create a linked list of size 4. Let’s see the cases of deletion.

Deleting the First Node:

Create a struct Node* function deleteFirst which will return the pointer to the new head after deleting the current head.
We’ll pass the current head pointer into the function.
Create a new struct Node* pointer ptr, and make it point to the current head.
Assign head to the next member of the list, by head = head->next, because this is going to be the new head of the linked list.
Free the pointer ptr. And return the head.

// Case 1: Deleting the first element from the linked list
struct Node * deleteFirst(struct Node * head){
    struct Node * ptr = head;
    head = head->next;
    free(ptr);
    return head;
}

Code Snippet 1: Deleting the first node

Deleting a Node in Between

Create a struct Node* function deleteAtIndex which will return the pointer to the head.
In the function, we'll pass the current head pointer and the index where the node is to be deleted.
Create a new struct Node* pointer p pointing to head.
Create a new struct Node* pointer q pointing to head->next, and run a loop until this pointer reaches the index from where we are deleting the node.
Assign q->next to the next member of the p structure using p->next = q->next.
Free the pointer q, because it has zero connections with the list now.
Return head.

// Case 2: Deleting the element at a given index from the linked list
struct Node * deleteAtIndex(struct Node * head, int index){
    struct Node *p = head;
    struct Node *q = head->next;
    for (int i = 0; i < index-1; i++)
    {
        p = p->next;
        q = q->next;
    }
    
    p->next = q->next;
    free(q);
    return head;
}

Code Snippet 2: Deleting a node in between

Deleting the Last Node

Deleting the last node is quite similar to deleting from any other index. The difference holds in the limit of the while loop. Here, we run a loop until the pointer reaches the end and points to NULL.
Assign NULL to the next member of the p structure using p->next = NULL.
Break the connection between q and NULL by freeing the pointer q.
Return head.

// Case 3: Deleting the last element
struct Node * deleteAtLast(struct Node * head){
    struct Node *p = head;
    struct Node *q = head->next;
    while(q->next !=NULL)
    {
        p = p->next;
        q = q->next;
    }
    
    p->next = NULL;
    free(q);
    return head;
}

Code Snippet 3: Deleting the last node

Deleting the Element with a Given Value from the Linked List

Here, we already have a value that needs to be deleted from the list. The main thing is that we’ll delete only the first occurrence.
Create a struct Node* function deleteByValue which will return the pointer to the head.
Pass into this function the head node and the value which needs to be deleted.
Create a new struct Node* pointer p pointing to the head.
Create another struct Node* pointer q pointing to the next of head.
Run a while loop until the pointer q encounters the given value or the list finishes.
If it encounters the value, delete that node by making p point to the next node, skipping the node q. Then, free q from memory.
If the list finishes without finding the value, continue without doing anything.
Return head.

// Case 4: Deleting the element with a given value from the linked list
struct Node * deleteByValue(struct Node * head, int value){
    struct Node *p = head;
    struct Node *q = head->next;
    while(q->data!=value && q->next!= NULL)
    {
        p = p->next;
        q = q->next;
    }
    
    if(q->data == value){
        p->next = q->next;
        free(q);
    }
    return head;
}

So, this was all about deletion in the linked list data structure.Here is the whole source code:

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;
    struct Node *next;
};

void linkedListTraversal(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

// Case 1: Deleting the first element from the linked list
struct Node * deleteFirst(struct Node * head){
    struct Node * ptr = head;
    head = head->next;
    free(ptr);
    return head;
}

// Case 2: Deleting the element at a given index from the linked list
struct Node * deleteAtIndex(struct Node * head, int index){
    struct Node *p = head;
    struct Node *q = head->next;
    for (int i = 0; i < index-1; i++)
    {
        p = p->next;
        q = q->next;
    }
    
    p->next = q->next;
    free(q);
    return head;
}

// Case 3: Deleting the last element
struct Node * deleteAtLast(struct Node * head){
    struct Node *p = head;
    struct Node *q = head->next;
    while(q->next !=NULL)
    {
        p = p->next;
        q = q->next;
    }
    
    p->next = NULL;
    free(q);
    return head;
}


// Case 4: Deleting the element with a given value from the linked list
struct Node * deleteAtIndex(struct Node * head, int value){
    struct Node *p = head;
    struct Node *q = head->next;
    while(q->data!=value && q->next!= NULL)
    {
        p = p->next;
        q = q->next;
    }
    
    if(q->data == value){
        p->next = q->next;
        free(q);
    }
    return head;
}
int main()
{
    struct Node *head;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;

    // Allocate memory for nodes in the linked list in Heap
    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    // Link first and second nodes
    head->data = 4;
    head->next = second;

    // Link second and third nodes
    second->data = 3;
    second->next = third;

    // Link third and fourth nodes
    third->data = 8;
    third->next = fourth;

    // Terminate the list at the third node
    fourth->data = 1;
    fourth->next = NULL;

    printf("Linked list before deletion\n");
    linkedListTraversal(head);

    // head = deleteFirst(head); // For deleting first element of the linked list
    // head = deleteAtIndex(head, 2);
    head = deleteAtLast(head);
    printf("Linked list after deletion\n");
    linkedListTraversal(head);

    return 0;
}

Insertion of a Node

Circular Linked List and Operations

Deletion in a Linked List