Inserting Between Two Nodes
00:00 Inserting a new node between two existing ones is a little bit more complex because there are actually two approaches we can take. We can either insert the new node after the existing one or before it.
00:39 Again, we have to check for a special condition: that the list is empty. Before, we just inserted the new node as the first one, but this time it makes more sense to raise an exception saying that the list is empty.
Now, we can traverse through each
Node in the
LinkedList just like before.
if node.data == target_node_data, then set the
.next attribute of the
new_node to the
Node after the one we’re working on, and then set the
.next attribute of the current
Node equal to the new one. After all, we’re inserting after the current
Node. We don’t need to traverse anymore, so we can return here. In the event that the
Node to insert after was not found, we should raise an exception.
Lucky for us, we’ve already written a method to insert a node at the beginning of the list. In any other case, we need to perform some careful traversal to ensure that we can insert a new node before the one that contains
target_node_data. First, I’m going to store the head node in a variable called
prev_node (previous node).
Then, to re-link the rest, set the new node’s
.next attribute to the node, and stop execution. Each time we go through the loop, we should make sure we set the previous node equal to the node we just checked. In this way, we’re always storing a reference to the previous node we iterated over. That allows us to set its
.next value to the new node—effectively, inserting the new node before the one we desire.
Become a Member to join the conversation.