Inserting a Node6:44 with Pasan Premaratne
Let's continue adding operations to our data structure to make it useful. In this video we'll implement an insert operation that takes an index as an insertion point.
Insert operations on link lists are quite interesting. 0:00 Unlike arrays, where you insert and element into the array, 0:03 all elements after the particular index need to be shifted. 0:07 Within linked lists, 0:10 we just need to change the references to next on a few nodes, and we're good to go. 0:12 Since each node points to the next one, by swapping out these references, 0:17 we can insert a node at any point in the list in constant time. 0:21 Much like binary search, though, there's a catch. 0:25 To find the node at that position we want to insert, 0:28 we need to traverse the list and get to that point. 0:31 We just implemented our search algorithm for the linked list type. 0:35 And we know that his runs in linear time. 0:38 So while actually inserting is fast, 0:40 finding the position in the list you want to insert it is not. 0:43 This is why I mentioned that there were some caveats to inserting. 0:47 Anyway, let's see what this looks like in code. 0:50 We'll define a method named insert that takes data to insert 0:54 along with an index position. 0:58 So we'll do this after search, right here. 1:00 Say, def insert. 1:03 And this takes some data to insert and a position to insert it at. 1:08 You may be thinking, wait a minute. 1:14 Linked lists don't have index positions right? 1:16 And you're correct, but we can mimic that behavior by just counting the number of 1:19 times we access next node. 1:24 If the index value passed into this argument is 0, 1:26 that means we want to insert the new node at the head of the list. 1:29 This is effectively the same behavior as calling add, 1:34 which means the logic is the same. 1:37 So we don't need to repeat it. 1:39 We can call the add method we wrote earlier. 1:41 So we'll say, if index, if index == 0, 1:43 or if index is 0, then, self.add data. 1:48 If the index is greater than 0, 1:53 then we need to traverse the list to find the current node at that index. 1:56 So if index > 0. 2:01 Now, before we do that, 2:05 we need to create a new node containing the data we want to insert. 2:06 So we'll say new = node, with some data. 2:10 I'm going to assign index the argument passed to our function to a local 2:15 variable named position and the head of the list to a variable named current. 2:20 position = index. 2:25 current = self.head. 2:28 Every time we call current.next_node, meaning we're moving to the next node 2:32 in the list, we'll decrease the value of position by 1. 2:37 When position is 0, we'll have arrived at the node that's currently 2:41 at the position we want to insert it. 2:45 In reality though, we don't to decrease it all the way to 0. 2:48 Imagine we have a list with five nodes and we want to insert in node at position 3. 2:52 To insert a node at position 3, we need to modify the node at position 2 and 3. 2:57 Node 2's next node attribute is going to point to the new node. 3:03 And the new node's next node attribute will point to node 3. 3:07 In this way, an insert is a constant time operation. 3:11 We don't need to shift every single element, 3:15 we just modify a few next node references. 3:18 In a doubly linked list, we can use node 3 to carry out both of these operations. 3:20 Node 3 in a doubly linked list would have a reference to node 2, and 3:26 we can use this reference to modify all the unnecessary links. 3:31 And a singly linked list though, which is what we have, 3:35 if we kept decreasing positions until we're at 0, we arrive at node 3. 3:39 We can then set the new node's next node property to point to node 3, but 3:44 we have no way of getting a reference to node 2, which we also need. 3:48 For this reason, 3:53 it's easier to decrease position to just 1 when it equals 1 and stop at node 2. 3:55 So in here we'll say, while position > 1. 4:01 That while the position is > 1, we'll keep calling next_node and 4:08 reassigning the current node. 4:12 So, current = node.next_node. 4:14 And at the same time, we'll decrement position. 4:18 So position = position- 1, 4:21 which you can also succinctly write as -= 1. 4:25 This way, when the position equals 1, the loop exits and 4:31 current will refer to the node at the position before the insert point. 4:36 So outside the while loop, we'll say, 4:41 prev = current, and next = current.next node. 4:45 To make things more clear, what I've done here is name the node before the new 4:51 one prev and the node after the new one next. 4:56 All that's left to do now is to insert the new node between prev and next. 4:59 So we'll say prev.next_ node = new. 5:04 And then, new next.node = next. 5:10 Now it seems like there's an issue with variable naming here, 5:17 and I'm most probably conflicting with some globally named next variable. 5:19 So I should go ahead and call this next_node and prev_node, 5:24 so that we don't mess things up here, prev_node. 5:29 So the .next_node is obviously the attribute on a node, but 5:36 this is just a local variable. 5:40 Lets document this method. 5:42 So up the top, we'll add a doc string and 5:43 we'll say, Inserts a new node containing data and index position. 5:48 Insertion takes constant time 5:57 But finding the node at the insertion 6:04 point takes the linear time. 6:11 Let's add this to the next line, there we go. 6:16 And then we'll say therefore, it takes an overall, Linear time. 6:20 This is why even though we can easily insert a new node without having to 6:28 shift the rest, ultimately, adding either to the head or the tail, 6:32 if you have a reference is much more efficient. 6:36 We have one more operation to add to our linked list that will make it a robust 6:39 data structure. 6:43
You need to sign up for Treehouse in order to download course files.Sign up