We continue our exploration of linked lists in this lesson. We will learn how to insert nodes at any place, as well as delete a node at any place.
Taking what we learned in the previous lesson, if we wish to insert or delete a node, we should first iterate through the linked list and stop once we find a target node. Then we can use a temporary variable to update the references and finish the insertion or deletion.
Let's take a step back for a second. What was that about a temporary variable? Imagine you are holding an apple in your left hand and an orange in your right hand. Now you wish to swap them. How can we do this? To be safe about it, we put the apple down on a table, swap the orange to the left hand, then pick up the apple with the right hand. Does it matter that we started with apple and not orange? Nope! The order is arbitrary, the outcome is exactly the same if we started with the orange.
Why does this matter? Because we can make use of a temporary variable to swap elements in two variables. Let's see a basic example.
Great! Let's use this to write an insert function to
insert a node into a linked list after some target value.
create_node and iterate are already
imported for you. The former takes an array to make a linked list,
returning the head of it. The latter is the same as we saw in the
previous lesson.
We should also write functions that allow us to insert at the head and tail of a linked list. For consistency, we will return the head of the linked list, even if it doesn't change.
Notice how easy it is to insert at the head and harder at the tail. This is because we already know what the head is and don't know where the tail is.
What if we change our parameters such that we are given a target node to insert after from. In this case, we no longer need an iteration, we can simply update our references. This is one of the benefits linked lists may have. Note that this function may insert at any position except the very head of a linked list.
We've learned how to insert into a linked list. How about deleting from one? The approach is similar. However as we need to update a node previous to the target, we opt to pass in the head as well so that we may find a reference to the node previous to the target. If we do this, then we may also handle the edge case where the target node is the head node. If so, then we should return a new reference to head.
Assume we want to delete a tail node while only given a head node. Please fill out the following code to do so.