1
00:00:00,268 --> 00:00:03,758
Insert operations on link
lists are quite interesting.

2
00:00:03,758 --> 00:00:07,308
Unlike arrays, where you insert and
element into the array,

3
00:00:07,308 --> 00:00:10,801
all elements after the particular
index need to be shifted.

4
00:00:10,801 --> 00:00:12,077
Within linked lists,

5
00:00:12,077 --> 00:00:17,360
we just need to change the references to
next on a few nodes, and we're good to go.

6
00:00:17,360 --> 00:00:21,320
Since each node points to the next one,
by swapping out these references,

7
00:00:21,320 --> 00:00:25,660
we can insert a node at any point
in the list in constant time.

8
00:00:25,660 --> 00:00:28,430
Much like binary search,
though, there's a catch.

9
00:00:28,430 --> 00:00:31,805
To find the node at that
position we want to insert,

10
00:00:31,805 --> 00:00:35,110
we need to traverse the list and
get to that point.

11
00:00:35,110 --> 00:00:38,497
We just implemented our search
algorithm for the linked list type.

12
00:00:38,497 --> 00:00:40,841
And we know that his runs in linear time.

13
00:00:40,841 --> 00:00:43,392
So while actually inserting is fast,

14
00:00:43,392 --> 00:00:47,470
finding the position in the list
you want to insert it is not.

15
00:00:47,470 --> 00:00:50,971
This is why I mentioned that there
were some caveats to inserting.

16
00:00:50,971 --> 00:00:53,419
Anyway, let's see what
this looks like in code.

17
00:00:54,580 --> 00:00:58,170
We'll define a method named
insert that takes data to insert

18
00:00:58,170 --> 00:01:00,330
along with an index position.

19
00:01:00,330 --> 00:01:03,596
So we'll do this after search, right here.

20
00:01:03,596 --> 00:01:08,070
Say, def insert.

21
00:01:08,070 --> 00:01:14,814
And this takes some data to insert and
a position to insert it at.

22
00:01:14,814 --> 00:01:16,357
You may be thinking, wait a minute.

23
00:01:16,357 --> 00:01:19,482
Linked lists don't have
index positions right?

24
00:01:19,482 --> 00:01:24,365
And you're correct, but we can mimic that
behavior by just counting the number of

25
00:01:24,365 --> 00:01:26,007
times we access next node.

26
00:01:26,007 --> 00:01:29,349
If the index value passed
into this argument is 0,

27
00:01:29,349 --> 00:01:34,040
that means we want to insert the new
node at the head of the list.

28
00:01:34,040 --> 00:01:37,680
This is effectively the same
behavior as calling add,

29
00:01:37,680 --> 00:01:39,510
which means the logic is the same.

30
00:01:39,510 --> 00:01:41,240
So we don't need to repeat it.

31
00:01:41,240 --> 00:01:43,710
We can call the add
method we wrote earlier.

32
00:01:43,710 --> 00:01:48,893
So we'll say, if index, if index == 0,

33
00:01:48,893 --> 00:01:53,948
or if index is 0, then, self.add data.

34
00:01:53,948 --> 00:01:56,393
If the index is greater than 0,

35
00:01:56,393 --> 00:02:01,837
then we need to traverse the list to
find the current node at that index.

36
00:02:01,837 --> 00:02:05,505
So if index > 0.

37
00:02:05,505 --> 00:02:06,968
Now, before we do that,

38
00:02:06,968 --> 00:02:10,821
we need to create a new node
containing the data we want to insert.

39
00:02:10,821 --> 00:02:15,310
So we'll say new = node, with some data.

40
00:02:15,310 --> 00:02:20,060
I'm going to assign index the argument
passed to our function to a local

41
00:02:20,060 --> 00:02:25,350
variable named position and the head of
the list to a variable named current.

42
00:02:25,350 --> 00:02:28,588
position = index.

43
00:02:28,588 --> 00:02:32,440
current = self.head.

44
00:02:32,440 --> 00:02:37,110
Every time we call current.next_node,
meaning we're moving to the next node

45
00:02:37,110 --> 00:02:41,640
in the list,
we'll decrease the value of position by 1.

46
00:02:41,640 --> 00:02:45,540
When position is 0, we'll have
arrived at the node that's currently

47
00:02:45,540 --> 00:02:48,110
at the position we want to insert it.

48
00:02:48,110 --> 00:02:52,017
In reality though,
we don't to decrease it all the way to 0.

49
00:02:52,017 --> 00:02:57,614
Imagine we have a list with five nodes and
we want to insert in node at position 3.

50
00:02:57,614 --> 00:03:03,365
To insert a node at position 3, we need
to modify the node at position 2 and 3.

51
00:03:03,365 --> 00:03:07,838
Node 2's next node attribute is
going to point to the new node.

52
00:03:07,838 --> 00:03:11,716
And the new node's next node
attribute will point to node 3.

53
00:03:11,716 --> 00:03:15,323
In this way,
an insert is a constant time operation.

54
00:03:15,323 --> 00:03:18,249
We don't need to shift
every single element,

55
00:03:18,249 --> 00:03:20,960
we just modify a few next node references.

56
00:03:20,960 --> 00:03:26,932
In a doubly linked list, we can use node
3 to carry out both of these operations.

57
00:03:26,932 --> 00:03:31,347
Node 3 in a doubly linked list would
have a reference to node 2, and

58
00:03:31,347 --> 00:03:35,463
we can use this reference to
modify all the unnecessary links.

59
00:03:35,463 --> 00:03:39,163
And a singly linked list though,
which is what we have,

60
00:03:39,163 --> 00:03:44,064
if we kept decreasing positions until
we're at 0, we arrive at node 3.

61
00:03:44,064 --> 00:03:48,788
We can then set the new node's next
node property to point to node 3, but

62
00:03:48,788 --> 00:03:53,910
we have no way of getting a reference
to node 2, which we also need.

63
00:03:53,910 --> 00:03:55,245
For this reason,

64
00:03:55,245 --> 00:04:01,297
it's easier to decrease position to just
1 when it equals 1 and stop at node 2.

65
00:04:01,297 --> 00:04:08,094
So in here we'll say, while position > 1.

66
00:04:08,094 --> 00:04:12,127
That while the position is > 1,
we'll keep calling next_node and

67
00:04:12,127 --> 00:04:14,013
reassigning the current node.

68
00:04:14,013 --> 00:04:18,840
So, current = node.next_node.

69
00:04:18,840 --> 00:04:21,376
And at the same time,
we'll decrement position.

70
00:04:21,376 --> 00:04:25,514
So position = position- 1,

71
00:04:25,514 --> 00:04:31,890
which you can also
succinctly write as -= 1.

72
00:04:31,890 --> 00:04:36,215
This way, when the position equals 1,
the loop exits and

73
00:04:36,215 --> 00:04:41,525
current will refer to the node at
the position before the insert point.

74
00:04:41,525 --> 00:04:45,934
So outside the while loop, we'll say,

75
00:04:45,934 --> 00:04:51,521
prev = current, and
next = current.next node.

76
00:04:51,521 --> 00:04:56,509
To make things more clear, what I've done
here is name the node before the new

77
00:04:56,509 --> 00:04:59,940
one prev and
the node after the new one next.

78
00:04:59,940 --> 00:05:04,780
All that's left to do now is to insert
the new node between prev and next.

79
00:05:04,780 --> 00:05:10,394
So we'll say prev.next_ node = new.

80
00:05:10,394 --> 00:05:15,760
And then, new next.node = next.

81
00:05:17,020 --> 00:05:19,730
Now it seems like there's an issue
with variable naming here,

82
00:05:19,730 --> 00:05:24,220
and I'm most probably conflicting with
some globally named next variable.

83
00:05:24,220 --> 00:05:29,478
So I should go ahead and
call this next_node and prev_node,

84
00:05:29,478 --> 00:05:33,938
so that we don't mess things up here,
prev_node.

85
00:05:36,890 --> 00:05:40,570
So the .next_node is obviously
the attribute on a node, but

86
00:05:40,570 --> 00:05:42,422
this is just a local variable.

87
00:05:42,422 --> 00:05:43,861
Lets document this method.

88
00:05:43,861 --> 00:05:48,902
So up the top, we'll add a doc string and

89
00:05:48,902 --> 00:05:57,508
we'll say, Inserts a new node
containing data and index position.

90
00:05:57,508 --> 00:06:01,160
Insertion takes constant time

91
00:06:04,400 --> 00:06:11,244
But finding the node at the insertion

92
00:06:11,244 --> 00:06:16,770
point takes the linear time.

93
00:06:16,770 --> 00:06:20,298
Let's add this to the next line,
there we go.

94
00:06:20,298 --> 00:06:26,726
And then we'll say therefore,
it takes an overall, Linear time.

95
00:06:28,407 --> 00:06:32,719
This is why even though we can easily
insert a new node without having to

96
00:06:32,719 --> 00:06:36,958
shift the rest, ultimately,
adding either to the head or the tail,

97
00:06:36,958 --> 00:06:39,907
if you have a reference
is much more efficient.

98
00:06:39,907 --> 00:06:43,985
We have one more operation to add to our
linked list that will make it a robust

99
00:06:43,985 --> 00:06:44,969
data structure.