1
00:00:00,710 --> 00:00:01,610
Hi everyone.

2
00:00:01,610 --> 00:00:06,830
Welcome to this Data Structures Crash course where we are going to discuss linked lists.

3
00:00:06,860 --> 00:00:10,670
Now in this video these are the three things that we will discuss.

4
00:00:10,670 --> 00:00:14,540
First let's try to understand singly linked lists and doubly linked lists.

5
00:00:14,540 --> 00:00:17,330
Then we will see how these are stored in memory.

6
00:00:17,330 --> 00:00:21,350
And then we will analyze the Big-O of common linked list operations.

7
00:00:21,350 --> 00:00:23,450
So let's get started with point number one.

8
00:00:23,450 --> 00:00:26,690
First we are going to try to understand singly linked lists.

9
00:00:26,690 --> 00:00:29,930
Now these are data structures that look like this.

10
00:00:29,930 --> 00:00:32,660
So you can see that over here you have nodes.

11
00:00:32,660 --> 00:00:33,110
All right.

12
00:00:33,110 --> 00:00:34,970
So this is an example of a node.

13
00:00:34,970 --> 00:00:37,640
And every node has a value.

14
00:00:37,640 --> 00:00:40,520
So for example this node has the value seven.

15
00:00:40,520 --> 00:00:44,720
And then it also has a pointer to the next node over here.

16
00:00:44,720 --> 00:00:47,150
Now the value in a node can be anything.

17
00:00:47,150 --> 00:00:51,080
It can be an integer a string or an array or anything.

18
00:00:51,080 --> 00:00:51,350
All right.

19
00:00:51,350 --> 00:00:53,060
So you have nodes over here.

20
00:00:53,060 --> 00:00:56,900
And every node has a value and a pointer to the next node.

21
00:00:56,900 --> 00:00:59,660
So this is how a singly linked list looks like.

22
00:00:59,660 --> 00:01:04,640
And then in the case of a singly linked list the first node is called the head.

23
00:01:04,640 --> 00:01:07,250
And the last node is called the tail.

24
00:01:07,250 --> 00:01:07,700
All right.

25
00:01:07,730 --> 00:01:13,580
Now let's say you want to come to this node over here which has the value nine for a singly linked list.

26
00:01:13,580 --> 00:01:14,000
All right.

27
00:01:14,030 --> 00:01:20,330
Now if you want to access this node or this value you cannot come directly over here as was the case

28
00:01:20,330 --> 00:01:21,350
in the case of an array.

29
00:01:21,350 --> 00:01:21,590
Right.

30
00:01:21,590 --> 00:01:26,630
So if you know the index then you can come directly to the value at a particular index in an array.

31
00:01:26,630 --> 00:01:31,550
But in the case of a singly linked list, you can't do that because we are only tracking the head and

32
00:01:31,550 --> 00:01:33,530
the tail and there are no indices over here.

33
00:01:33,530 --> 00:01:37,340
So what you would have to do is you would have to first access the head.

34
00:01:37,340 --> 00:01:43,100
And then from the head, you have to keep traversing the nodes till you reach the node that you want

35
00:01:43,100 --> 00:01:43,910
to access.

36
00:01:44,500 --> 00:01:46,600
So you come over here, then over here.

37
00:01:46,600 --> 00:01:49,300
Now that's what we call a singly linked list.

38
00:01:49,300 --> 00:01:49,570
All right.

39
00:01:49,570 --> 00:01:51,850
So this is an introduction to singly linked lists.

40
00:01:51,850 --> 00:01:56,380
So we have seen that these are data structures that have a head and a tail.

41
00:01:56,380 --> 00:01:58,390
So these are properties for this data structure.

42
00:01:58,390 --> 00:02:01,630
And then we also can track the length of the singly linked list.

43
00:02:01,630 --> 00:02:07,330
Now we have seen that when we implement singly linked lists or anything any data structure as a class

44
00:02:07,330 --> 00:02:09,100
it can have properties and methods.

45
00:02:09,100 --> 00:02:09,370
Right.

46
00:02:09,370 --> 00:02:12,880
So these are going to be the properties of any singly linked list.

47
00:02:12,880 --> 00:02:17,590
And then methods is what we will discuss over here, which is things like adding to the linked list

48
00:02:17,590 --> 00:02:19,960
or removing from the linked list etc..

49
00:02:19,960 --> 00:02:20,530
All right.

50
00:02:20,560 --> 00:02:21,790
Now let's proceed.

51
00:02:21,790 --> 00:02:24,610
And let's take a look at what is a doubly linked list.

52
00:02:24,640 --> 00:02:28,210
Now, a doubly linked list is pretty similar to a singly linked list.

53
00:02:28,210 --> 00:02:32,260
The only difference is that you can see over here there is an extra pointer.

54
00:02:32,260 --> 00:02:36,490
So there is an extra pointer which points to the previous node as well.

55
00:02:36,940 --> 00:02:37,210
All right.

56
00:02:37,210 --> 00:02:38,380
So that's the only difference.

57
00:02:38,380 --> 00:02:38,770
All right.

58
00:02:38,770 --> 00:02:41,050
And again the first node is called the head.

59
00:02:41,050 --> 00:02:43,210
And the last node is called the tail.

60
00:02:43,210 --> 00:02:45,040
For a doubly linked list as well.

61
00:02:45,040 --> 00:02:45,430
All right.

62
00:02:45,430 --> 00:02:48,250
So that's a singly linked list and a doubly linked list.

63
00:02:48,280 --> 00:02:51,850
Now let's take a look at how linked lists are stored in memory.

64
00:02:51,880 --> 00:02:55,960
Now that's something that differentiates a linked list from an array.

65
00:02:55,960 --> 00:02:56,350
All right.

66
00:02:56,380 --> 00:02:57,910
Now we have seen that previously.

67
00:02:57,910 --> 00:03:02,140
In the case of an array we need memory slots back to back to store an array.

68
00:03:02,140 --> 00:03:06,970
But in the case of a linked list we don't need back to back memory slots.

69
00:03:06,970 --> 00:03:09,010
We just can store them anywhere.

70
00:03:09,010 --> 00:03:09,370
All right.

71
00:03:09,400 --> 00:03:16,030
Now for every node, memory slots will be used up to store the value of that particular node and to

72
00:03:16,030 --> 00:03:17,260
store the pointers.

73
00:03:17,290 --> 00:03:22,690
Now I have pointers over here because in the case of a singly linked list, we only have the next pointer.

74
00:03:22,690 --> 00:03:26,350
But in the case of a doubly linked list we also have the previous pointer.

75
00:03:26,350 --> 00:03:31,870
So again we will take we will make use of this when we discuss the big O of common linked list operations.

76
00:03:31,870 --> 00:03:35,020
So let's proceed and take a look at point number three.

77
00:03:35,650 --> 00:03:39,550
First we take a look at big O of common singly linked list operations.

78
00:03:39,550 --> 00:03:41,590
So this deals with singly linked lists.

79
00:03:41,590 --> 00:03:45,040
Now if you want to insert into a singly linked list.

80
00:03:45,040 --> 00:03:46,750
So let's take a look at that over here.

81
00:03:46,750 --> 00:03:48,520
Now for this let's take an example.

82
00:03:48,520 --> 00:03:51,940
So I have this singly linked list over here 753.

83
00:03:51,940 --> 00:03:53,320
And then it's pointing to null.

84
00:03:53,320 --> 00:03:55,900
Now let's say you want to insert at the beginning.

85
00:03:55,900 --> 00:03:59,560
So for this you just need to create a new node with the value.

86
00:03:59,560 --> 00:04:02,470
So let's say you want to insert a node with value eight.

87
00:04:02,470 --> 00:04:04,540
So you have that node over here.

88
00:04:04,540 --> 00:04:05,980
So you have to create this node.

89
00:04:05,980 --> 00:04:09,730
And you need to make this node point to the previous head.

90
00:04:09,730 --> 00:04:12,880
And then you have to make this node over here the new head.

91
00:04:12,880 --> 00:04:13,600
So that's it.

92
00:04:13,600 --> 00:04:16,900
So you can see this is a constant space and time operation.

93
00:04:16,900 --> 00:04:19,690
And no indexing is involved over here.

94
00:04:19,690 --> 00:04:20,020
Right.

95
00:04:20,020 --> 00:04:23,740
If you remember we have discussed that we don't need back to back memory slots.

96
00:04:23,740 --> 00:04:28,960
So making this the head does not involve shifting these nodes over here in memory.

97
00:04:28,960 --> 00:04:32,530
So that's why this is a constant time and space operation.

98
00:04:32,530 --> 00:04:35,200
Again we don't use any extra or auxiliary space.

99
00:04:35,200 --> 00:04:37,690
So that's why this is constant space as well.

100
00:04:37,690 --> 00:04:41,980
Now let's take a look at inserting a new value at the end.

101
00:04:42,010 --> 00:04:46,900
Now if you want to do this, all that you need to do is you need to create a new node with the value.

102
00:04:46,900 --> 00:04:50,110
Let's say you want to insert a node with value four.

103
00:04:50,110 --> 00:04:53,530
So you have to create a new node with that particular value.

104
00:04:53,530 --> 00:04:58,720
And then you need to make the previous tail which is this node over here point to the new node.

105
00:04:58,720 --> 00:05:01,270
And then you have to make the new node the tail.

106
00:05:01,270 --> 00:05:01,690
All right.

107
00:05:01,690 --> 00:05:05,740
So this also you can see is a constant space and time operation.

108
00:05:05,740 --> 00:05:10,030
Again note this will be constant time only if you're storing the tail.

109
00:05:10,030 --> 00:05:14,350
Now you can store the tail as one of the properties of the singly linked list.

110
00:05:14,350 --> 00:05:16,810
And it will depend on how you write your class.

111
00:05:16,810 --> 00:05:21,550
Now, if you are not storing the tail, then you would have to traverse from the head till the tail.

112
00:05:21,550 --> 00:05:25,180
So in that case it would be a o of n time operation.

113
00:05:25,180 --> 00:05:29,830
Again, it's constant space because we are not using any auxiliary or extra space.

114
00:05:29,830 --> 00:05:34,450
Now if you want to insert in between somewhere in between the head and the tail, then you would have

115
00:05:34,450 --> 00:05:36,730
to create a new node with that particular value.

116
00:05:36,730 --> 00:05:40,510
And then you have to identify the previous node and the next node.

117
00:05:40,510 --> 00:05:40,780
Right.

118
00:05:40,780 --> 00:05:42,910
So let's say you want to insert between these two.

119
00:05:42,940 --> 00:05:45,460
So this is the previous node and this is the next node.

120
00:05:45,460 --> 00:05:48,700
Now you have to make this node over here point to the new node.

121
00:05:48,700 --> 00:05:51,880
And then the new node has to point to the next node.

122
00:05:52,000 --> 00:05:52,270
All right.

123
00:05:52,270 --> 00:05:54,610
So this is how you would insert in between.

124
00:05:54,610 --> 00:06:00,520
And in this case it's going to be an O of X operation with respect to time and a constant space operation.

125
00:06:00,520 --> 00:06:04,450
Now it's O of X over here because you have to traverse to the previous node.

126
00:06:04,450 --> 00:06:04,870
Right.

127
00:06:05,380 --> 00:06:06,880
Let's say you want to insert over here.

128
00:06:06,880 --> 00:06:08,620
So you have to start from the head.

129
00:06:08,620 --> 00:06:10,570
And then you have to traverse to seven.

130
00:06:10,570 --> 00:06:12,400
And you have to identify the previous node.

131
00:06:12,400 --> 00:06:14,470
So there is some traversing involved over here.

132
00:06:14,470 --> 00:06:16,930
So that's why this is a O of X time operation.

133
00:06:16,930 --> 00:06:21,880
And then we are not using any extra or auxiliary space because of which this is going to be constant

134
00:06:21,880 --> 00:06:22,480
space.

135
00:06:22,480 --> 00:06:26,290
Now let's go ahead and take a look at removing from the singly linked list.

136
00:06:26,290 --> 00:06:28,510
Now let me just clean this up a little bit.

137
00:06:29,780 --> 00:06:30,200
All right.

138
00:06:30,200 --> 00:06:33,410
Now, first we take a look at removing from the beginning.

139
00:06:33,410 --> 00:06:35,630
If you want to remove from the beginning, right.

140
00:06:35,630 --> 00:06:40,250
All you have to do is you have to make the next node, which is this one over here, the head.

141
00:06:40,250 --> 00:06:40,460
Right.

142
00:06:40,460 --> 00:06:43,100
So if you make this the head then we are losing this.

143
00:06:43,100 --> 00:06:45,560
And in that way you have removed from the beginning.

144
00:06:45,560 --> 00:06:47,750
So you can see this is a constant time operation.

145
00:06:47,750 --> 00:06:52,940
Because no matter how big the singly linked list is, it's just going to be the same number of operations.

146
00:06:52,940 --> 00:06:53,210
Right.

147
00:06:53,210 --> 00:06:54,890
So it's constant number of operations.

148
00:06:54,890 --> 00:06:57,140
We don't need to traverse the singly linked list.

149
00:06:57,140 --> 00:07:01,100
And hence removing from the beginning is constant time and constant space.

150
00:07:01,100 --> 00:07:04,520
It's constant space because we are not using any auxiliary space.

151
00:07:04,520 --> 00:07:10,220
Now if you want to remove from the end, you can see that it's O of n time and constant space.

152
00:07:10,220 --> 00:07:14,480
Now, even though we track the tail right, we are tracking the tail as a property.

153
00:07:14,480 --> 00:07:20,000
Even then it's o of n time complexity because we have to identify the previous node, right?

154
00:07:20,000 --> 00:07:25,400
For example, if you want to remove this, we have to traverse from the head till the previous node

155
00:07:25,400 --> 00:07:27,290
to identify the previous node.

156
00:07:27,680 --> 00:07:30,380
And then we can make the previous node point to null.

157
00:07:30,380 --> 00:07:33,200
And in that way remove the last node.

158
00:07:33,290 --> 00:07:37,430
So traversing to the previous node is going to be an O of n operation.

159
00:07:37,430 --> 00:07:37,730
Right.

160
00:07:37,730 --> 00:07:40,250
So and then we just have to set this to the tail.

161
00:07:40,400 --> 00:07:42,920
So that's why this is an O of N operation.

162
00:07:42,920 --> 00:07:43,280
All right.

163
00:07:43,280 --> 00:07:48,590
So this is something which is different when we compare singly linked lists and doubly linked lists,

164
00:07:48,590 --> 00:07:50,420
which is something that we will soon see.

165
00:07:50,420 --> 00:07:50,870
All right.

166
00:07:50,900 --> 00:07:51,740
Now let's proceed.

167
00:07:51,740 --> 00:07:56,810
And if you want to remove in between again it's going to be an O of X time operation because you have

168
00:07:56,810 --> 00:07:57,920
to traverse the node right.

169
00:07:57,920 --> 00:07:59,660
So you have to traverse the singly linked list.

170
00:07:59,660 --> 00:08:04,610
For example if you want to remove this node over here you have to reach till this node.

171
00:08:04,610 --> 00:08:08,090
And then you have to disconnect this connections, these two connections.

172
00:08:08,090 --> 00:08:11,150
And you have to make this node point to this one over here.

173
00:08:11,150 --> 00:08:12,950
So you have to establish this connection.

174
00:08:12,950 --> 00:08:16,190
So so the point is that you have to traverse the singly linked list.

175
00:08:16,190 --> 00:08:17,570
So you have to start from the head.

176
00:08:17,570 --> 00:08:18,740
Let's say this is the head.

177
00:08:18,740 --> 00:08:22,520
So you have to start traversing from the head and come to the previous node.

178
00:08:22,520 --> 00:08:23,450
So identify it.

179
00:08:23,450 --> 00:08:25,670
And then you have to identify the next node.

180
00:08:25,670 --> 00:08:28,700
And you have to make the previous node point to the next node.

181
00:08:28,700 --> 00:08:31,190
In this way you're actually deleting this node over here.

182
00:08:31,190 --> 00:08:33,770
So again it involves traversing the singly linked list.

183
00:08:33,770 --> 00:08:36,740
And that's why this is an O of X time operation.

184
00:08:36,740 --> 00:08:37,220
All right.

185
00:08:37,250 --> 00:08:38,300
Now let's proceed.

186
00:08:38,300 --> 00:08:42,290
Now if you want to access the X node again this is just an index.

187
00:08:42,290 --> 00:08:47,660
So in this case again you have to keep traversing the singly linked list from the head till the x node.

188
00:08:47,660 --> 00:08:49,910
So that's why this is an O of x time operation.

189
00:08:49,910 --> 00:08:55,580
And we are not using any auxiliary space because of which this is an O of one or a constant space operation.

190
00:08:55,580 --> 00:09:00,770
Now similarly, if you want to set the value of the x node, you have to access that node first, and

191
00:09:00,770 --> 00:09:03,530
then it's a constant time operation to change the value.

192
00:09:03,530 --> 00:09:08,270
So that's why this is again O of X time complexity and constant space complexity.

193
00:09:08,270 --> 00:09:13,910
Now if you want to copy a singly linked list and create a new singly linked list, that's O of n time

194
00:09:13,910 --> 00:09:19,520
and space again, it's taking O of n space because you are creating a new copy of the singly linked

195
00:09:19,520 --> 00:09:20,240
list, right.

196
00:09:20,240 --> 00:09:21,380
Which has n elements.

197
00:09:21,380 --> 00:09:25,730
And then to copy the elements you have to traverse the given singly linked list as well.

198
00:09:25,730 --> 00:09:28,790
So that's why the time complexity over here is O of N.

199
00:09:28,790 --> 00:09:32,360
Now to traverse and search for an element in a singly linked list.

200
00:09:32,360 --> 00:09:37,370
In the worst case is going to be O of n, so the time complexity is O of n and the space complexity

201
00:09:37,370 --> 00:09:37,910
is O of one.

202
00:09:37,910 --> 00:09:39,890
Because we are not using any extra space.

203
00:09:39,890 --> 00:09:44,840
Now, the time complexity is O of n, because the value for which you are searching in the worst case

204
00:09:44,840 --> 00:09:46,280
can be the last node, right?

205
00:09:46,280 --> 00:09:48,830
And then this is pointing to let's say null.

206
00:09:49,190 --> 00:09:51,110
And again it could be the second last also.

207
00:09:51,110 --> 00:09:53,690
So let's say you're saying that we are already tracking the tail.

208
00:09:53,690 --> 00:09:54,080
Yes.

209
00:09:54,080 --> 00:09:57,830
If you build in that check you can check the head and you can check the tail.

210
00:09:57,830 --> 00:10:01,850
And if the value is not equal to the value of these two, then let's say it's over here.

211
00:10:01,850 --> 00:10:03,980
The value is over here for which you are searching.

212
00:10:03,980 --> 00:10:07,520
You would have to traverse the singly linked list starting from here till here.

213
00:10:07,520 --> 00:10:13,850
So that's going to be almost N operations because of which this is an O of n time complexity operation.

214
00:10:13,850 --> 00:10:14,270
All right.

215
00:10:14,270 --> 00:10:17,810
So we are done with common operations for a singly linked list.

216
00:10:17,810 --> 00:10:21,290
Now let's take a look at common operations for a doubly linked list.

217
00:10:21,320 --> 00:10:26,870
Now if you compare the operations for singly linked list and doubly linked list, you will see that

218
00:10:26,870 --> 00:10:27,920
it's almost the same.

219
00:10:27,920 --> 00:10:32,900
So when it comes to inserting, it's the same in all the three cases, which is inserting at the beginning,

220
00:10:32,900 --> 00:10:34,460
at the end and in between.

221
00:10:34,460 --> 00:10:39,350
Now when it comes to removing, you will see that it's different when you remove from the end.

222
00:10:39,350 --> 00:10:41,720
So let's say you have a doubly linked list over here.

223
00:10:42,350 --> 00:10:47,750
And if you want to remove the tail, if this was a singly linked list we have already seen this is an

224
00:10:47,750 --> 00:10:52,280
O of N time operation because we have to traverse the array to identify the previous node.

225
00:10:52,280 --> 00:10:56,300
But in the case of a doubly linked list you we have this connection, right.

226
00:10:56,300 --> 00:10:57,320
So we have this connection.

227
00:10:57,320 --> 00:11:00,410
So we can just start at the tail and then move one back.

228
00:11:00,410 --> 00:11:04,970
So that's why this is going to be a constant time operation for a doubly linked list.

229
00:11:05,750 --> 00:11:11,120
And then all the other operations are just the same as the case was for a singly linked list.