Understanding deletion of first node
Similar to insertion, deletion is one of the most common operations in a linked list. Deleting the first node of a singly linked list is similar to inserting a node at the beginning. We need to consider two cases.
1. The list is empty
When the list is empty, meaning it contains no elements, any attempt to delete a node is unnecessary because there are no nodes in the list. Since there is nothing to remove, the list remains unchanged. We can return the existing head, as the list is empty, and no node needs to be deleted.
The list is empty
Algorithm
- Step 1: Return the original head node.
2. The list is not empty
In this scenario, we update the head to hold the reference of the next node in the list, the second node, and then delete the current head node. However, before updating the head, we need to use a temporary variable to store the reference of the current head node so that we can delete it later.
The list is not empty
Algorithm
- Step 1: Create a temporary pointer to store the current head node.
- Step 2: Move the head pointer to the next node.
- Step 3: Delete the original head node to free up memory.
- Step 4: Return the new head node.
next pointer will be null. So, once we update the head to hold the reference of the second node, it will just hold null, as expected from an empty list. Then, we can delete the old head node.Implementation
When implementing the logic for deleting the first node operation, we consider both possible cases and write the code for each in conditional blocks.
C++
Java
Typescript
Javascript
Python
Complexity Analysis
Looking at the logic, it is straightforward to understand the complexity of this operation in terms of time and space. In any case, we delete the first node and change the value of the head, which takes constant time and space.
Best Case
- Space Complexity - O(1)
- Time Complexity - O(1)
Worst Case
- Space Complexity - O(1)
- Time Complexity - O(1)