Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in C++

Deletion in a Singly Linked List

Understand how to perform deletions in singly linked lists by updating pointers correctly. Explore deletion from the beginning, by value, and by position, and learn their time and space complexities. This lesson helps you avoid common errors and solidify core linked list operations in C++.

We'll cover the following...

By now, insertion and traversal in a singly linked list are clear. The next core operation is deletion, which removes a node from the list while keeping the remaining nodes properly connected.

Deletion in a linked list is performed by updating pointers between nodes. As a singly linked list only moves forward, careful handling of pointers is required to ensure that no part of the list becomes disconnected. Understanding how these pointers change is crucial for implementing deletion correctly and analyzing its time complexity.

Linked list deletion

Deletion means removing a node from a singly linked list while keeping the remaining nodes properly connected. As each node only points forward, deletion is done by updating the next pointer of the node just before the one being removed. If the removed node is the first node, the head pointer must be updated.

Deletion is usually handled in three cases:

  1. Deletion from the beginning

  2. Deletion by value

  3. Deletion by position

Deletion from the beginning

Deleting from the beginning removes the current head node. This operation is simple because the head is updated to point to the second node.

The following interactive visualizer helps to better understand the deletion from the beginning of a linked list.

C++ implementation

The method below deletes the first node by moving the head pointer to the next node and freeing the removed node.

C++ 17
void deleteFromBeginning() {
    // If the list is empty, throw exception
    if (head == nullptr) {
        throw std::out_of_range("Cannot delete from empty list");
    }
    // Remove the first node and update head
    ListNode* temp = head;
    head = head->next;
    delete temp;
}
Delete from the beginning of Linked List

  • Time complexity: Deletion from the beginning takes O(1)O(1) ...