Deletion in Linked List

Linked list is one of the fundamental concept in computer science and we have already covered linked list data structure and now we are covering deletion in linked list.

We are going to cover every possible way to delete a node in the linked list whether we need to delete a node in the beginning of a linked list, deletion of a node at the specified location (any random node) and the last node in a linked list.

Let’s begin first with the deletion of linked list from the beginning or start.

Deletion in linked list from the beginning

Deletion in linked list from the beginning is a simple deletion operation. In a singly linked list, each node points to the next node in a linked list and the entire list start with the head node.

To delete the first node, we need to simply move the head pointer to the next node in the list and deallocate the memory occupied by the first node node in a list. This operation is quiet efficient as it does not require traversing the linked list. It requires a pointer change and memory free operation.

C Implementation

This code helps you to implement the deletion of a linked list in c programming language.

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

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

void deleteFromBeginning(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty.\n");
        return;
    }

    struct Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

C++ Implementation

Below is the implementation of deleting the first node from a linked list in C++ programming language.

#include <iostream>
using namespace std;

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

void deleteFromBeginning(Node*& head) {
    if (head == nullptr) {
        cout << "List is empty." << endl;
        return;
    }

    Node* temp = head;
    head = head->next;
    delete temp;
}

Deletion in linked list from a specified position

Deletion in linked list from a specified position requires careful traversal. Suppose you want to delete the node at the position pos(1-based index) as You will need to traverse the list up to the node just before the target position and then change its next pointer to skip the node that needs to be deleted. After adjusting the pointer you have to deallocate the memory for the removed node. Boundary checks are necessary to ensure the position is valid and the list is not empty.

C Implementation

void deleteFromPosition(struct Node** head, int position) {
    if (*head == NULL || position <= 0) {
        printf("Invalid position or list is empty.\n");
        return;
    }

    struct Node* temp = *head;

    if (position == 1) {
        *head = temp->next;
        free(temp);
        return;
    }

    for (int i = 1; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) {
        printf("Position exceeds list length.\n");
        return;
    }

    struct Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    free(nodeToDelete);
}

C++ Implementation

void deleteFromPosition(Node*& head, int position) {
    if (head == nullptr || position <= 0) {
        cout << "Invalid position or list is empty." << endl;
        return;
    }

    if (position == 1) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }

    Node* current = head;
    for (int i = 1; current != nullptr && i < position - 1; i++) {
        current = current->next;
    }

    if (current == nullptr || current->next == nullptr) {
        cout << "Position exceeds list length." << endl;
        return;
    }

    Node* nodeToDelete = current->next;
    current->next = nodeToDelete->next;
    delete nodeToDelete;
}

Deletion in linked list from the end

To delete the last node in a singly linked list, you must traverse the list until you reach the second-last node, then set its next pointer to NULL and free the last node. This operation has a linear time complexity as traversal is required. Special care must be taken when the list has only one node.

C Implementation

void deleteFromEnd(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty.\n");
        return;
    }

    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }

    struct Node* temp = *head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }

    free(temp->next);
    temp->next = NULL;
}

C++ Implementation

void deleteFromEnd(Node*& head) {
    if (head == nullptr) {
        cout << "List is empty." << endl;
        return;
    }

    if (head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }

    Node* current = head;
    while (current->next->next != nullptr) {
        current = current->next;
    }

    delete current->next;
    current->next = nullptr;
}

FAQs

What happen if we try to delete from the empty linked list?

The program should check for this case and handle it gracefully by printing a message or returning early.

What is the time complexity for deletion in a linked list?

• Deletion from the beginning: O(1)
• Deletion from a given position or end: O(n) due to traversal