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:15 There are times when we’d want to use one over the other, so the best thing to do here is separate this out into two distinct methods: .add_after() and .add_before().

00:27 Let’s start with .add_after(). This method will take a string called target_node_data, which is the data of the node to insert after, and a new_node to insert.

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.

00:55 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.

01:35 .add_before() is a similar method. It too will take a target_node_data as well as a new_node. Just like before, I’ll perform some error checking to see if the .head is None.

01:49 Another special condition is if the first node in the linked list is the one we’re searching for. In that case, we know the new node should be the first node in the linked list.

02:02 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).

02:26 Now we can start iterating. If the current node’s data equals the target data, then set the previous node’s .next attribute to the new node.

02:39 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.

03:12 If this seems a little bit confusing or unintuitive, don’t sweat it. Pause the video and think through this until it makes sense. Implementing data structures can take a lot of practice.

03:26 Just like before, if we don’t find the desired node, we’ll raise an exception.

03:34 We can create a new empty linked list by instantiating the LinkedList class.

03:41 Let’s start by testing the .add_before() method on our empty list.

03:48 Good. We’re hitting the Exception. I’ll recreate this linked list with some values so that we can test the proper functionality of the method.

04:00 Add a new node before "b" with data "a".

04:07 There we go. .add_after() should work similarly, except it’ll add a node after the supplied data target.

04:19 And it looks like that method works too. Now you have all the methods you need to add a new node at the beginning or somewhere in the middle of your linked list.

04:30 The last operation we’ll implement is removing a node.