Why is deleting in a Singly Linked List O(1)?

In this tutorial, we will discus about the deleting operations in singly linked list.

How does a Node in a Singly Linked List get deleted?

To remove a node from a linked list, we must first break the link that connects that node to the one that points to it. Assume node P must be deleted, and node Q is the one pointing to P. So, we'll need to remove the link between P and Q, and Q will point to the node that P was pointing to.

Different kinds of Linked List Node Deletion

Deletions are classified into three types:

• Deletion from the linked list's start
• Deletion from the end of the linked list
• Deletion between the start and the end.

All of the situations may not require O(1) time. The time complexities of various operations are listed in the section below.

Different deletion Operations' Time Complexity

Deletion from the start:

• Point the pointer to the next node.
• Time Complexity will be O(1).

Deletion from the end:

• Traverse to the second last element
• Set the next pointer to NULL.
• Time Complexity will be O(N).

Delete a linked list item from the middle:

• Go to the element immediately preceding the element to be eliminated.
• Change the following points to remove the node from the list.
• Time Complexity will be O(N).

When does deletion take O(1) Time in a Singly Linked List?

Because we do not have to traverse the list, deleting in a single linked list is O(1) in three circumstances.

First, let us designate the pointer pointing to the node that needs to be erased "previous." So that is what we must do.

• current = previous->next
• previous->next = current->next
• current->next = NULL
• delete current

Because current is the node removed from the singly linked list.

Second case: Let's call it head when it is necessary to delete the first/start/head node. So that is what we must do.

• head = head->next

As a result, head points to the next node.

Third case: When we need to delete the last/end/tail node, we'll call it tail. As a result, we must act accordingly.

• tail = NULL

This is only possible if we keep an extra pointer, namely, tail, for addressing the end node of the linked list. Meanwhile, we can only perform this once since we end up losing the reference to the last node and there is no solution in O(1) in a singly linked list to find the reference to the new last node. Because it contains the preceding pointer, it is permissible in a doubly linked list.

The following is an implementation of various deletion procedures in a singly linked list:

C++ Program:

Output:

Original list: 15 25 35 45 List after eliminating the first node: 25 35 45 List after eliminating the last node: 25 35 List after eliminating the specified node: 25