In this article, we will discuss about linked list deletion. We will see how to delete a node in a Singly linked list.
This article will be continuation of our Linked List tutorial series. You can navigate to other parts from here:
- Linked List Introduction – Linked List Tutorial series #1
- Linked List Insertion – Linked List Tutorial series #2
Agenda of this article
By the end of this article, you shall be able to delete a node at any position of a linked list.
Linked List Deletion
We may be asked to delete a node in a linked list at three different places:
- delete the first node
- delete the last node
- delete the node at a given position
Let us discuss one-by-one along with the coding examples.
1. Delete the first node
- Create a temp pointer that points to the same node as Head.
- Move head pointer to the next node and dispose the temp.
In python the temp will be garbage collected when it doesn’t have any reference.
Here’s the code to delete a node at start:
2. Delete the Last Node
- Traverse the list while maintaining previous node’s address also.
- After reaching the end of the list we will have two pointers -> one pointing to tail node, other pointing to the node before tail node.
- Update previous node’s next pointer to null
- Dispose the tail node.
Here’s the code to delete a node at end:
3. Deleting a node at a given position
- Maintain previous node and the node to be deleted.
- Once we find the node to be deleted, point the previous node’s pointer to the next pointer of the node to be deleted.
- Dispose the current node to be deleted.
Here’s the code to delete a node at a given position:
Now let us see the executable code of deletion of Linked list where we can call all the three functions discussed above.
Time Complexity
Time complexity for deleting a Node is O(n) where n is the length of linked list, as worst case might be last of the node to be deleted and we need to traversing the entire list.
Space Complexity
Space complexity – O(1) for a temp variable.