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:
Subscribe to our Newsletter!
Never miss Upcoming articles, free e-books, weekly updates on latest news from Android and Coding Community.
- 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:
| def delete_at_start(head): | |
| # edge case: return if head is null | |
| if not head: | |
| return None | |
| head = head.next # moving head to next node | |
| return head |
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:
| def delete_at_end(head): | |
| if not head: | |
| return None | |
| prev_node = head | |
| while prev_node.next.next: | |
| prev_node = prev_node.next | |
| prev_node.next = None | |
| return head |
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:
| def delete_at_pos(head, position): | |
| if not head: | |
| return None | |
| if position is 0: | |
| return head.next | |
| prev_node = head | |
| curr_node = head.next | |
| current_pos = 1 | |
| while curr_node and current_pos < position: | |
| current_pos += 1 | |
| prev_node = prev_node.next | |
| curr_node = curr_node.next | |
| prev_node.next = curr_node.next | |
| return head |
Now let us see the executable code of deletion of Linked list where we can call all the three functions discussed above.
| class Node: | |
| def __init__(self, data=None): | |
| self.data = data | |
| self.next = None | |
| """ | |
| Deleting a node at start. | |
| """ | |
| def delete_at_start(head): | |
| # edge case: return if head is null | |
| if not head: | |
| return None | |
| head = head.next # moving head to next node | |
| return head | |
| """ | |
| Deleting a node at end. | |
| """ | |
| def delete_at_end(head): | |
| # edge case | |
| if not head: | |
| return None | |
| prev_node = head | |
| # traversing until current node's next is null | |
| while prev_node.next.next: | |
| prev_node = prev_node.next | |
| # deleting the reference of previous node's next | |
| prev_node.next = None | |
| return head | |
| def delete_at_pos(head, position): | |
| # edge case | |
| if not head: | |
| return None | |
| if position is 0: | |
| return head.next | |
| # maintaining previous and current nodes | |
| prev_node = head | |
| curr_node = head.next | |
| current_pos = 1 | |
| while curr_node and current_pos < position: | |
| current_pos += 1 | |
| prev_node = prev_node.next | |
| curr_node = curr_node.next | |
| prev_node.next = curr_node.next | |
| return head | |
| def insert(head, data): | |
| if not head: | |
| return Node(data) | |
| temp = Node(data) | |
| temp.next = head | |
| head = temp | |
| return head | |
| if __name__ == '__main__': | |
| # start with empty list | |
| head = None | |
| head = insert(head, 5) | |
| head = insert(head, 4) | |
| head = insert(head, 3) | |
| head = insert(head, 2) | |
| head = insert(head, 1) | |
| # delete at a given position | |
| head = delete_at_pos(head, 2) | |
| # deleting a node at start | |
| head = delete_at_start(head) | |
| # deleting a node at end | |
| head = delete_at_end(head) | |
| while head: | |
| print("{}".format(head.data), end=" ") | |
| head = head.next |
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.
