Preview
Video Player
00:00
00:00
Inserting a Node
6:44Let'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