Deletion
Linked lists also shine when it comes to deletion, especially when deleting from the beginning of the list.
To delete a node from the beginning of a linked list, all we need to do is perform one step: we change the first_node of the linked list to now point to the second node.
Let’s return to our example of the linked list containing the values "once", "upon", "a", and "time". If we want to delete the value "once", we could simply change the linked list to begin at "upon":
| | list.first_node = node_2 |
Contrast this with an array, in which deleting the first element means shifting all remaining data one cell to the left, which takes O(N) time.
When it comes to deleting the final node of a linked list, the actual deletion takes one step—we just take the second-to-last node and make its link None. However, it takes N steps to even access the second-to-last node in the first place, since we need to start at the beginning of the list and follow the links until we reach it.
The following table contrasts the various scenarios of deletion for both arrays and linked lists. Note how it’s identical to insertion:
Situation | Array | Linked List |
|---|---|---|
Delete at beginning | Worst case | Best case |
Delete at middle | Average case | Average case |
Delete at end | Best case | Worst case |
While deleting from the beginning or end of a linked list is straightforward, deleting from anywhere in the middle is slightly more involved.
Say we want to delete the value at index 2 ("purple") from our example linked list of colors, as shown in the following diagram:
To accomplish this, we need to first access the node immediately preceding the one we’re deleting ("blue”). Then we change its link to point to the node that is immediately after the node we’re deleting ("green").
The following visualization demonstrates us changing the link of the "blue" node from "purple" to "green":
It’s interesting to note that whenever we delete a node from our linked list, the node still exists in memory somewhere. We’re just removing the node from our list by ensuring that no other node from the list links to it. This has the effect of deleting the node from our list, even if the node still exists in memory.
(Different programming languages handle these deleted nodes in various ways. Some will automatically detect that they’re not being used and will “garbage collect” them, freeing up memory.)
Code Implementation: Linked List Deletion
Here’s what the delete operation might look like in our LinkedList class. It’s called delete, and we pass in the index we’re going to delete:
| | def delete(self, index): |
| | if index == 0: |
| | self.first_node = self.first_node.next_node |
| | return |
| | |
| | current_node = self.first_node |
| | current_index = 0 |
| | |
| | while current_index < (index - 1): |
| | current_node = current_node.next_node |
| | current_index += 1 |
| | |
| | node_after_deleted_node = current_node.next_node.next_node |
| | |
| | current_node.next_node = node_after_deleted_node |
This method is pretty similar to the insert method we saw earlier. Let’s highlight some of the novel points.
The method first deals with a case in which index is 0, meaning we intend to delete the first node of the list. The code for this is ridiculously simple:
| | if index == 0: |
| | self.first_node = self.first_node.next_node |
| | return |
All we do is change our list’s first_node to point to what is currently the second node, and we’re done!
The rest of the method handles deletions anywhere else from the list. To do this, we use a while loop to access the node immediately preceding the one we want to delete. This becomes our current_node.
We then grab the node that comes immediately after the node we’re going to delete and store it in a variable called node_after_deleted_node:
| | node_after_deleted_node = current_node.next_node.next_node |
Notice our little trick in accessing that node. It’s simply the node that comes two nodes after the current_node!
Then we modify the link of the current_node to point to the node_after_deleted_node:
| | current_node.next_node = node_after_deleted_node |
