1
00:00:00,000 --> 00:00:02,050


2
00:00:02,050 --> 00:00:02,800
CARTER: All right.

3
00:00:02,800 --> 00:00:04,070
Welcome, everyone.

4
00:00:04,070 --> 00:00:06,100
This is our second test review session.

5
00:00:06,100 --> 00:00:06,850
My name is Carter.

6
00:00:06,850 --> 00:00:10,390
I'm joined by Connor, one of
our head course assistants.

7
00:00:10,390 --> 00:00:15,170
And this is a pointer.

8
00:00:15,170 --> 00:00:17,920
When we were asking you all to
come up with test review questions,

9
00:00:17,920 --> 00:00:21,910
like I'd pose to you all in lecture,
or in some fun games later on,

10
00:00:21,910 --> 00:00:23,830
we asked you for a
particularly hard question.

11
00:00:23,830 --> 00:00:26,292
One of you wrote, "Literally
anything about pointers."

12
00:00:26,292 --> 00:00:28,750
And so I'm delighted to say
that we're going to be spending

13
00:00:28,750 --> 00:00:30,070
a little bit of time on pointers.

14
00:00:30,070 --> 00:00:31,445
Talking about how they're useful.

15
00:00:31,445 --> 00:00:34,090
How they can be used in
data structures later on.

16
00:00:34,090 --> 00:00:36,985
And talk about memory and data
structures in this review session.

17
00:00:36,985 --> 00:00:38,860
So, before we talk about
pointers, though, we

18
00:00:38,860 --> 00:00:41,235
have to talk about memory
addresses and memory locations.

19
00:00:41,235 --> 00:00:44,470
And, if you recall from week four, we
had this idea of a computer's memory

20
00:00:44,470 --> 00:00:46,900
as basically this collection of grids.

21
00:00:46,900 --> 00:00:51,010
And inside each of these
blocks, is a byte, eight bits,

22
00:00:51,010 --> 00:00:52,480
that represent information, right?

23
00:00:52,480 --> 00:00:55,720
And so in some cases, we might
care about some of these bytes,

24
00:00:55,720 --> 00:00:57,430
we might not about other bytes.

25
00:00:57,430 --> 00:00:59,800
Those are garbage values,
not used in our program.

26
00:00:59,800 --> 00:01:04,958
But again, the study of memory as this
sort of block of bytes in our computer.

27
00:01:04,958 --> 00:01:08,000
Now going back to representation, we
talked about how some of these bytes

28
00:01:08,000 --> 00:01:09,640
actually refer to characters.

29
00:01:09,640 --> 00:01:12,410
Or to refer to numbers and so on.

30
00:01:12,410 --> 00:01:15,160
In this case, the
characters are one byte,

31
00:01:15,160 --> 00:01:18,700
and these bits here
represent this sequence

32
00:01:18,700 --> 00:01:20,440
of characters, "HI!" exclamation point.

33
00:01:20,440 --> 00:01:22,450
Where there's no character at the end.

34
00:01:22,450 --> 00:01:25,990
4 bytes where each
character is one byte.

35
00:01:25,990 --> 00:01:29,390
Now, this is all fine and good for
storing these values in our memory,

36
00:01:29,390 --> 00:01:29,890
right?

37
00:01:29,890 --> 00:01:33,445
But it's also good to have a way to
talk about the location of these places.

38
00:01:33,445 --> 00:01:35,320
If you want to refer
back to them, if we want

39
00:01:35,320 --> 00:01:37,825
to use these later on
in our program, it's

40
00:01:37,825 --> 00:01:40,450
good to have a way to talk about
where these things are stored.

41
00:01:40,450 --> 00:01:42,640
And that's where memory
addresses come in.

42
00:01:42,640 --> 00:01:45,265
Where we can start to give a name
to these different locations.

43
00:01:45,265 --> 00:01:47,570
Different blocks in
our computer's memory.

44
00:01:47,570 --> 00:01:50,810
So here we have hexadecimal
notation, which you may recall,

45
00:01:50,810 --> 00:01:53,920
is basically talking in
base 16, where instead

46
00:01:53,920 --> 00:01:58,000
of having a single digit
correspond to numbers 0 through 9,

47
00:01:58,000 --> 00:02:00,490
they can also go up
to A through F, right?

48
00:02:00,490 --> 00:02:04,870
Having 16 different values we
can represent in a single place.

49
00:02:04,870 --> 00:02:10,430
And we notate this base 16 notation
with this 0x at the beginning.

50
00:02:10,430 --> 00:02:13,990
So we have 0x0 for this
very first location memory.

51
00:02:13,990 --> 00:02:15,730
0x1 and so on.

52
00:02:15,730 --> 00:02:22,000
We count up to nine, but then we can go
past nine, and we can say A B C D E F,

53
00:02:22,000 --> 00:02:24,460
and so on, having 16
different possible values

54
00:02:24,460 --> 00:02:27,950
we can show in that single digits place.

55
00:02:27,950 --> 00:02:30,250
So this works well
for our basically 16--

56
00:02:30,250 --> 00:02:34,200
or 4 by 4 grid, or 16
different possible values here.

57
00:02:34,200 --> 00:02:36,770
So, as a brief reflection
on this, we have

58
00:02:36,770 --> 00:02:39,300
this idea of mapping memory locations.

59
00:02:39,300 --> 00:02:43,100
Let's say I want the value at
0x0, well what character am I

60
00:02:43,100 --> 00:02:44,270
talking about in this case?

61
00:02:44,270 --> 00:02:45,860
Feel free to message me in the chat.

62
00:02:45,860 --> 00:02:47,490
Message me or Connor, here.

63
00:02:47,490 --> 00:02:49,985
Which character does 0x0 refer to?

64
00:02:49,985 --> 00:02:54,320


65
00:02:54,320 --> 00:02:54,980
All right.

66
00:02:54,980 --> 00:02:56,930
So I'm seeing H, in the chat.

67
00:02:56,930 --> 00:03:00,080
And it's definitely the case,
that 0x0 refers to H, right?

68
00:03:00,080 --> 00:03:02,870
If we go back to our little
map here, we see that 0x0

69
00:03:02,870 --> 00:03:04,450
is the location of this first byte.

70
00:03:04,450 --> 00:03:12,110
It certainly refers back to H.
But notice how 0x0 is not H,

71
00:03:12,110 --> 00:03:14,870
it's just pointing to H, right?

72
00:03:14,870 --> 00:03:17,160
It's not the actual value,
it's just telling us,

73
00:03:17,160 --> 00:03:18,410
hey this is where H is stored.

74
00:03:18,410 --> 00:03:20,160
And this is what we
call a pointer, right?

75
00:03:20,160 --> 00:03:21,890
A pointer is literally a memory address.

76
00:03:21,890 --> 00:03:24,420
A place in memory we
can point to and say,

77
00:03:24,420 --> 00:03:26,340
this is where this
certain value is stored.

78
00:03:26,340 --> 00:03:27,420
It's not that value.

79
00:03:27,420 --> 00:03:30,770
It's just the location of that value.

80
00:03:30,770 --> 00:03:33,440
And to show an example
by contrast, let's

81
00:03:33,440 --> 00:03:37,460
say I wanted to store a value like
H, and name it something, right?

82
00:03:37,460 --> 00:03:39,800
Maybe I want to store this
character H and call it

83
00:03:39,800 --> 00:03:43,250
C. Well, what would happen here,
is my compiler would go ahead

84
00:03:43,250 --> 00:03:48,590
and find location memory, put H there,
and sort of name that, quote, unquote,

85
00:03:48,590 --> 00:03:49,340
"c."

86
00:03:49,340 --> 00:03:52,430
So whenever I talk about c, I get
that value H. I order print c.

87
00:03:52,430 --> 00:03:58,100
I get that value H. So, c doesn't point
to H, c is like a name for H, right?

88
00:03:58,100 --> 00:04:02,040
It's different than the
pointer, it's like a name for H.

89
00:04:02,040 --> 00:04:06,930
But here, we started to add in this
syntax of ampersands and stars,

90
00:04:06,930 --> 00:04:10,590
and talking about more than
just about naming variables,

91
00:04:10,590 --> 00:04:14,110
getting their address
and their location.

92
00:04:14,110 --> 00:04:16,829
So, before we sort of
dive into the syntax,

93
00:04:16,829 --> 00:04:19,440
let's try to break it down,
and read it from right to left.

94
00:04:19,440 --> 00:04:23,250
We had first this &c, right?

95
00:04:23,250 --> 00:04:25,680
Well, what does the ampersand mean?

96
00:04:25,680 --> 00:04:28,140
I have this mnemonic
I really like to think

97
00:04:28,140 --> 00:04:31,650
about in my head, which is ampersand
begins with A, and so does address.

98
00:04:31,650 --> 00:04:33,930
So ampersand sort of
corresponds to this idea

99
00:04:33,930 --> 00:04:35,970
of an address in a computer's memory.

100
00:04:35,970 --> 00:04:40,920
If I were to say &c what I'm asking
for is the address of c right?

101
00:04:40,920 --> 00:04:47,190
&c address of c And of course, in
this case, since c refers to H,

102
00:04:47,190 --> 00:04:50,250
the address of C is 0x0.

103
00:04:50,250 --> 00:04:56,180
So, basically that's evaluating that
right side of this expression first.

104
00:04:56,180 --> 00:04:59,280
But then, we can also talk about what's
going on with this left hand side,

105
00:04:59,280 --> 00:04:59,780
right?

106
00:04:59,780 --> 00:05:04,730
This char *p, which is basically
defining for us, saying,

107
00:05:04,730 --> 00:05:10,190
I want a pointer called p,
that points to character.

108
00:05:10,190 --> 00:05:11,643
And this works out for us, right?

109
00:05:11,643 --> 00:05:13,310
Because we know a pointer is an address.

110
00:05:13,310 --> 00:05:16,520
And here we're actually giving an
address to this pointer, right?

111
00:05:16,520 --> 00:05:20,205
So this star notation is saying
p is a pointer to a character.

112
00:05:20,205 --> 00:05:21,080
It's not a character.

113
00:05:21,080 --> 00:05:24,440
It's not the actual value H, it's
just a pointer to that character.

114
00:05:24,440 --> 00:05:27,160
And we call it p.

115
00:05:27,160 --> 00:05:30,250
But you know, what happened
with that asterisk, right?

116
00:05:30,250 --> 00:05:33,790
We originally used it to
define p, but now it's gone.

117
00:05:33,790 --> 00:05:37,060
And this is where our syntax gets
a little bit confusing, right?

118
00:05:37,060 --> 00:05:39,940
We use it to define a pointer,
but we don't necessarily

119
00:05:39,940 --> 00:05:43,570
use it to reference or get
back the value of a point,

120
00:05:43,570 --> 00:05:45,460
or the actual address there.

121
00:05:45,460 --> 00:05:49,750
We do use that star to follow
a pointer, and get the value

122
00:05:49,750 --> 00:05:51,080
store to that location.

123
00:05:51,080 --> 00:05:56,230
So *p would give us that value H,
because it's saying follow that arrow

124
00:05:56,230 --> 00:06:00,750
to that location and get that value.

125
00:06:00,750 --> 00:06:04,140
So now is a bit of practice, based
on what we've just seen here, so far.

126
00:06:04,140 --> 00:06:07,710
Let's say I wanted to have
this value 'I' stored here.

127
00:06:07,710 --> 00:06:11,490
So what am I calling the
value of 'I' in this case,

128
00:06:11,490 --> 00:06:16,730
if I'm writing this code on the left,
char c = 'I' what am I now calling

129
00:06:16,730 --> 00:06:17,630
the value of 'I'?

130
00:06:17,630 --> 00:06:20,680


131
00:06:20,680 --> 00:06:21,180
Right.

132
00:06:21,180 --> 00:06:23,305
So in the chat, I'm seeing
I'm calling it c, right?

133
00:06:23,305 --> 00:06:26,880
This is literally, I'm
naming this value c.

134
00:06:26,880 --> 00:06:30,990
Now, if I want to get the location
of c, might something like this.

135
00:06:30,990 --> 00:06:31,870
I would say,

136
00:06:31,870 --> 00:06:35,670
OK, I want a new character
pointer called p,

137
00:06:35,670 --> 00:06:39,000
that's going to get the value of &c.

138
00:06:39,000 --> 00:06:40,983
So what is &c in this case?

139
00:06:40,983 --> 00:06:42,150
You want to add in the chat.

140
00:06:42,150 --> 00:06:48,010


141
00:06:48,010 --> 00:06:49,910
Right, so I'm seeing 0x1 right?

142
00:06:49,910 --> 00:06:52,970
Where this value of 'I' is now 0x1.

143
00:06:52,970 --> 00:06:59,990
And so this pointer, p, will point
to 0x1 in our computer's memory.

144
00:06:59,990 --> 00:07:02,810
Now again, to go and get that
value of 'I' what would we do?

145
00:07:02,810 --> 00:07:10,420
We would use this *p syntax, to
say, go and get me that value there.

146
00:07:10,420 --> 00:07:14,075
Now, that's sort of the gist of
pointers, and pointer syntax.

147
00:07:14,075 --> 00:07:16,450
Where we can do lots of really
cool things with pointers.

148
00:07:16,450 --> 00:07:19,030
One of them is about allocating memory.

149
00:07:19,030 --> 00:07:20,950
Giving our program
more memory it can use.

150
00:07:20,950 --> 00:07:23,080
And remember we saw this
idea of malloc, this

151
00:07:23,080 --> 00:07:26,530
function that we can use to give
us segments of a computer's memory.

152
00:07:26,530 --> 00:07:30,940
Now malloc as an argument, will
take a certain number of bytes

153
00:07:30,940 --> 00:07:31,850
at the space level.

154
00:07:31,850 --> 00:07:35,860
So here I might say, malloc
give me 4 bytes of memory,

155
00:07:35,860 --> 00:07:40,330
and then give me back a pointer
that I'm going to call s.

156
00:07:40,330 --> 00:07:43,570
And I say I'm wanting to
store characters in here,

157
00:07:43,570 --> 00:07:46,550
just as a sort of hint to the compiler.

158
00:07:46,550 --> 00:07:51,660
So, what I'm doing here, is saying,
OK malloc has given me these 4 bytes.

159
00:07:51,660 --> 00:07:56,750
And now s is pointing
to that first location.

160
00:07:56,750 --> 00:08:02,160
So 0x0 of those four bytes
that I've gotten, right?

161
00:08:02,160 --> 00:08:04,590
Again, if I want to add
a value in here, what

162
00:08:04,590 --> 00:08:12,870
I could do is say, OK let's go to that
value of s, and add the character h.

163
00:08:12,870 --> 00:08:16,110
So go to s, which is that
sort of asterisk there,

164
00:08:16,110 --> 00:08:18,390
and store the value of h.

165
00:08:18,390 --> 00:08:21,870
And now I would see that h sort
of gets into that first location

166
00:08:21,870 --> 00:08:25,110
of my malloc locked space, right?

167
00:08:25,110 --> 00:08:28,830
I could then sort of move one bite
over, using pointer arithmetic,

168
00:08:28,830 --> 00:08:31,460
and go ahead and add this 'I" in, right?

169
00:08:31,460 --> 00:08:33,210
I can sort of do that
all the way through.

170
00:08:33,210 --> 00:08:36,502
Sort of adding these characters until I
get to that terminating null character,

171
00:08:36,502 --> 00:08:37,659
right?

172
00:08:37,659 --> 00:08:41,720
But once we're done with this, one thing
we have to do is free up our memory.

173
00:08:41,720 --> 00:08:44,020
We don't want to just keep
adding more and more memory.

174
00:08:44,020 --> 00:08:46,513
You have to give it
back to our computer.

175
00:08:46,513 --> 00:08:48,430
And that's what this
idea of freeing comes in.

176
00:08:48,430 --> 00:08:51,430
I could free s, remember
s was our pointer

177
00:08:51,430 --> 00:08:54,460
to that first byte in our malloc space.

178
00:08:54,460 --> 00:08:56,240
And I want to say I'm going to free it.

179
00:08:56,240 --> 00:08:59,200
Which basically means I'm not
going to use this location anymore.

180
00:08:59,200 --> 00:09:01,690
It's free from their program to use.

181
00:09:01,690 --> 00:09:03,790
It doesn't necessarily
delete the values there.

182
00:09:03,790 --> 00:09:06,550
It doesn't necessarily change
where s is pointing to.

183
00:09:06,550 --> 00:09:10,000
It's just saying, hey, this memory,
I'm no longer going to touch it,

184
00:09:10,000 --> 00:09:13,360
and other programs are free
to go ahead and do that.

185
00:09:13,360 --> 00:09:16,170
So, what questions
are there on pointers?

186
00:09:16,170 --> 00:09:18,570
On malloc and free, so far?

187
00:09:18,570 --> 00:09:21,750
Before we go ahead and see how these
can be used in data structures.

188
00:09:21,750 --> 00:09:25,677


189
00:09:25,677 --> 00:09:27,510
And I'll pause here for
just a minute or so,

190
00:09:27,510 --> 00:09:30,120
so you have some time to write
some questions in the chat,

191
00:09:30,120 --> 00:09:32,640
or message them to me or to Connor.

192
00:09:32,640 --> 00:09:46,730


193
00:09:46,730 --> 00:09:50,150
All right, and certainly happy to keep
taking more questions if they come in.

194
00:09:50,150 --> 00:09:52,387
But, what we're going
to do now is see how

195
00:09:52,387 --> 00:09:54,470
these pointers can be
worked into data structures,

196
00:09:54,470 --> 00:09:56,512
and Connor is here, our
expert on data structure,

197
00:09:56,512 --> 00:09:58,550
to talk us through what
we can do, and what

198
00:09:58,550 --> 00:10:01,425
we should think about for data
structures, when it comes to the test.

199
00:10:01,425 --> 00:10:05,017


200
00:10:05,017 --> 00:10:05,600
CONNOR: Right.

201
00:10:05,600 --> 00:10:06,960
Hello, everyone.

202
00:10:06,960 --> 00:10:11,420
I am to go ahead and get started
with a little bit of review

203
00:10:11,420 --> 00:10:12,720
on data structures.

204
00:10:12,720 --> 00:10:17,650
So I'm going to go ahead
and share my screen.

205
00:10:17,650 --> 00:10:22,490
Yes, to this nice presentation
here, we have on data structures.

206
00:10:22,490 --> 00:10:26,380
So, to get started out, I'm just going
to ask people to put in the chat,

207
00:10:26,380 --> 00:10:30,340
like, what are some data structures
that we have learned about?

208
00:10:30,340 --> 00:10:34,150
Hopefully we'll get
some interaction here.

209
00:10:34,150 --> 00:10:38,650
To get everyone started to
thinking about this review.

210
00:10:38,650 --> 00:10:41,680
It's been a little bit since
we talked about them initially.

211
00:10:41,680 --> 00:10:43,180
Someone said trees.

212
00:10:43,180 --> 00:10:44,185
That's a great example.

213
00:10:44,185 --> 00:10:46,870


214
00:10:46,870 --> 00:10:50,240
Anybody else want to contribute
to the chat a little bit?

215
00:10:50,240 --> 00:10:51,100
Perfect.

216
00:10:51,100 --> 00:10:52,582
Someone said a single linked list.

217
00:10:52,582 --> 00:10:54,040
Yeah that's a really important one.

218
00:10:54,040 --> 00:10:56,110
One that we've worked with a lot.

219
00:10:56,110 --> 00:10:57,400
We'll definitely go over that.

220
00:10:57,400 --> 00:11:01,620
Hash tables as well, yeah we're
going to go over all of those.

221
00:11:01,620 --> 00:11:02,250
All right.

222
00:11:02,250 --> 00:11:04,140
Perfect.

223
00:11:04,140 --> 00:11:07,980
So, here's a little bit more of
a comprehensive list of the ones

224
00:11:07,980 --> 00:11:10,470
that we're going to be going over.

225
00:11:10,470 --> 00:11:13,740
We're going to talk
about all of these today.

226
00:11:13,740 --> 00:11:16,050
Notice they're in two categories here.

227
00:11:16,050 --> 00:11:22,560
Where we've got these top 5,
are all kind of concrete data

228
00:11:22,560 --> 00:11:25,770
structures, in that they
have specific implementations

229
00:11:25,770 --> 00:11:29,370
in C, or in Python, or in other
languages that we can talk about.

230
00:11:29,370 --> 00:11:32,320
Whereas stacks and queues
are abstract data structures,

231
00:11:32,320 --> 00:11:37,350
and we'll talk a little bit more about
what that means when we get to them.

232
00:11:37,350 --> 00:11:40,950
And then, also, if you
don't mind, if people

233
00:11:40,950 --> 00:11:45,060
could put in the chat as well some
ideas on why we use data structures.

234
00:11:45,060 --> 00:11:48,060
Why they might be helpful in our code.

235
00:11:48,060 --> 00:11:50,130
Why don't we just use
variables for everything?

236
00:11:50,130 --> 00:11:52,245
What are these data
structures useful for?

237
00:11:52,245 --> 00:12:04,310


238
00:12:04,310 --> 00:12:07,020
Yeah, someone said
making better algorithms.

239
00:12:07,020 --> 00:12:07,520
Yeah.

240
00:12:07,520 --> 00:12:10,680
So and that's a great
way of thinking about it.

241
00:12:10,680 --> 00:12:15,028
So, data structures really help
us to organize the information

242
00:12:15,028 --> 00:12:16,320
that we're storing in our code.

243
00:12:16,320 --> 00:12:20,990
So, while maybe we could do store
everything in individual variables,

244
00:12:20,990 --> 00:12:25,140
if we're storing like a bunch
of data, like a bunch of numbers

245
00:12:25,140 --> 00:12:29,120
then it's probably easier to store
an array with 100 numbers in it,

246
00:12:29,120 --> 00:12:35,530
rather than have 100 variables
all called x1, x2, x3.

247
00:12:35,530 --> 00:12:38,030
Yeah, and someone else said
searching large amounts of data.

248
00:12:38,030 --> 00:12:40,100
And that ties into this as well.

249
00:12:40,100 --> 00:12:42,950
We're going to have certain
data structures that are really

250
00:12:42,950 --> 00:12:45,748
useful for searching or sorting data.

251
00:12:45,748 --> 00:12:48,290
Specifically, we're going to
talk about the hash tables which

252
00:12:48,290 --> 00:12:53,450
you implemented for your Speller PSAT,
if you all remember back that far.

253
00:12:53,450 --> 00:12:55,550
I know it was a long time ago.

254
00:12:55,550 --> 00:12:58,320
But today, we're going to
start out talking about arrays.

255
00:12:58,320 --> 00:13:00,620
So, arrays are kind of
the first data structure

256
00:13:00,620 --> 00:13:02,030
we talked about in this class.

257
00:13:02,030 --> 00:13:08,060
And essentially, they look
like a list of some data type.

258
00:13:08,060 --> 00:13:09,360
In this case, it's integers.

259
00:13:09,360 --> 00:13:14,780
But it could also be characters, or
floats, or whatever data type you want.

260
00:13:14,780 --> 00:13:17,660
And some interesting things
to keep in mind about arrays,

261
00:13:17,660 --> 00:13:19,700
is that we index starting at 0.

262
00:13:19,700 --> 00:13:22,190
So remember that this
is the 0th element.

263
00:13:22,190 --> 00:13:25,340
This is the first, second,
third, fourth, and so on

264
00:13:25,340 --> 00:13:27,280
if you have a longer one.

265
00:13:27,280 --> 00:13:31,970
To look up or to change an element
in array, it takes constant time.

266
00:13:31,970 --> 00:13:35,320
So if I want to say, get me the
fourth element of this array,

267
00:13:35,320 --> 00:13:39,170
it'll go right over in
constant time to 25 here.

268
00:13:39,170 --> 00:13:41,492
And so that's really quick.

269
00:13:41,492 --> 00:13:42,700
They're fixed length, though.

270
00:13:42,700 --> 00:13:45,550
So, this is the big drawback
of arrays, is that I've

271
00:13:45,550 --> 00:13:47,660
got this list of five numbers here.

272
00:13:47,660 --> 00:13:50,020
If I want to add a sixth,
then I'm going to have

273
00:13:50,020 --> 00:13:52,750
to go through a whole process
of making it a new array,

274
00:13:52,750 --> 00:13:54,400
allocating some new memory.

275
00:13:54,400 --> 00:13:57,260
Essentially some difficult stuff.

276
00:13:57,260 --> 00:14:00,520
And so we're going to
want to try and fix that.

277
00:14:00,520 --> 00:14:02,680
And the way that we're
going to try and fix that

278
00:14:02,680 --> 00:14:04,690
is with this really cool
data structure that we

279
00:14:04,690 --> 00:14:08,060
learned about called linked lists.

280
00:14:08,060 --> 00:14:12,340
So the idea of a linked list
is to get that variable length

281
00:14:12,340 --> 00:14:17,450
that we don't have for an array.

282
00:14:17,450 --> 00:14:21,670
And so the base of a linked list
is this struct called a node.

283
00:14:21,670 --> 00:14:25,640
That you've seen a lot in
our labs and PSAT so far.

284
00:14:25,640 --> 00:14:27,520
So I want to go over
it a little bit more.

285
00:14:27,520 --> 00:14:32,102
Where everything in our node is
going to have some sort of value.

286
00:14:32,102 --> 00:14:34,810
In this case, we're saying the
value is an integer, because we're

287
00:14:34,810 --> 00:14:35,920
storing a list of numbers.

288
00:14:35,920 --> 00:14:40,340
But that could also be a char,
or a float, or anything else.

289
00:14:40,340 --> 00:14:44,810
And then we're going to have
this pointer called "next."

290
00:14:44,810 --> 00:14:47,960
And that is going to point to
the next thing in our list.

291
00:14:47,960 --> 00:14:51,940
So the way I like to
think about a linked list

292
00:14:51,940 --> 00:14:56,320
is it's kind of like a treasure
hunt or something like that,

293
00:14:56,320 --> 00:14:58,840
where you know where the
first item is, but then you

294
00:14:58,840 --> 00:15:01,810
have to go to that first item to
get to the next item, and then

295
00:15:01,810 --> 00:15:04,340
the next, and then the next after that.

296
00:15:04,340 --> 00:15:07,310
And so this is kind of what
that can look like graphically.

297
00:15:07,310 --> 00:15:10,420
So we've got like some
variable called my_linked_list.

298
00:15:10,420 --> 00:15:14,290
And that variable is just a
pointer to a node over here.

299
00:15:14,290 --> 00:15:17,650
And that node can have a value,
which in this case is five.

300
00:15:17,650 --> 00:15:21,760
And then a pointer to another node,
which has a value, and then a pointer

301
00:15:21,760 --> 00:15:26,732
to another node, which has a value,
and a pointer to or-- and then this one

302
00:15:26,732 --> 00:15:28,190
doesn't have a pointer to anything.

303
00:15:28,190 --> 00:15:31,130
It just has null here at the end.

304
00:15:31,130 --> 00:15:34,420
And so that's going to be our
sign that the list is over,

305
00:15:34,420 --> 00:15:37,930
that that's our last
element in the list.

306
00:15:37,930 --> 00:15:43,080
And notice these nodes
aren't lined up neatly,

307
00:15:43,080 --> 00:15:46,110
and that's not just because I'm
not great at making Google Slides

308
00:15:46,110 --> 00:15:47,160
line up well.

309
00:15:47,160 --> 00:15:52,230
It's also to show that when you're
allocating memory for a linked list,

310
00:15:52,230 --> 00:15:55,810
the memory doesn't all have to be
next to each other like in an array.

311
00:15:55,810 --> 00:15:58,920
We can have one chunk of memory
over here, another chunk over here,

312
00:15:58,920 --> 00:16:00,090
another chunk over here.

313
00:16:00,090 --> 00:16:03,510
If we add a new element, the chunk
of memory might be over here.

314
00:16:03,510 --> 00:16:05,100
They can be all over the place.

315
00:16:05,100 --> 00:16:09,240
Just as long as they're
pointing to each other.

316
00:16:09,240 --> 00:16:12,770
And then I'm going to talk briefly about
how we add elements to a linked list.

317
00:16:12,770 --> 00:16:14,970
Because that's some
pretty interesting stuff.

318
00:16:14,970 --> 00:16:18,590
So when we start out,
with the linked list,

319
00:16:18,590 --> 00:16:21,050
we'll essentially just
have it be null at first.

320
00:16:21,050 --> 00:16:24,800
So our variable my linked list
will be this pointer to null.

321
00:16:24,800 --> 00:16:27,500
And then let's say I want to add
an element with a value of one

322
00:16:27,500 --> 00:16:28,670
to the list.

323
00:16:28,670 --> 00:16:32,690
What I have to do first is
I'll use malloc to allocate

324
00:16:32,690 --> 00:16:34,650
some memory for that element.

325
00:16:34,650 --> 00:16:38,660
So now we've got this new node over
here, but there's nothing in it yet.

326
00:16:38,660 --> 00:16:41,130
And then what I'll do is
update the value of that node.

327
00:16:41,130 --> 00:16:44,270
So I'll say, I want this
node to have a value of one.

328
00:16:44,270 --> 00:16:46,910
And then what I'll do is
I'll update this next--

329
00:16:46,910 --> 00:16:50,450
this bottom part as the
next element of the node--

330
00:16:50,450 --> 00:16:54,630
and I'll say point to wherever
my linked list is pointing now.

331
00:16:54,630 --> 00:16:57,580
So I'll point here to this null.

332
00:16:57,580 --> 00:17:00,970
And then finally, I'll update
this variable my linked list

333
00:17:00,970 --> 00:17:04,349
so that it's pointing to my new node.

334
00:17:04,349 --> 00:17:07,109
So now those steps have
gone through have made it

335
00:17:07,109 --> 00:17:11,690
so that I now have a linked
list with one element, one node,

336
00:17:11,690 --> 00:17:13,506
and then it's pointing to null.

337
00:17:13,506 --> 00:17:14,839
So we can go through this again.

338
00:17:14,839 --> 00:17:16,940
Where if I want to add
another element to this

339
00:17:16,940 --> 00:17:20,839
I'll malloc to create space
for it, I'll add the value,

340
00:17:20,839 --> 00:17:23,390
I'll add a pointer to
my current linked list,

341
00:17:23,390 --> 00:17:28,670
and then I'll update my linked
list to point to this new node.

342
00:17:28,670 --> 00:17:32,390
And then, just to get us up
to speed with our last one,

343
00:17:32,390 --> 00:17:35,120
we can do this to get our
whole linked list here.

344
00:17:35,120 --> 00:17:38,090


345
00:17:38,090 --> 00:17:39,890
Just some features of
linked lists that is

346
00:17:39,890 --> 00:17:43,010
going to be good to remember
for the upcoming test.

347
00:17:43,010 --> 00:17:45,740
Linked lists have linear time indexing.

348
00:17:45,740 --> 00:17:50,750
So unlike arrays, we can't just grab
the third element, or something,

349
00:17:50,750 --> 00:17:51,710
or the second element.

350
00:17:51,710 --> 00:17:55,850
If we want to get to this element
one, this element with index two,

351
00:17:55,850 --> 00:18:00,320
we would have to search, first through
this node, then through that node,

352
00:18:00,320 --> 00:18:01,817
and then finally to this node.

353
00:18:01,817 --> 00:18:03,650
So it's going to be
linear time, because you

354
00:18:03,650 --> 00:18:09,340
might have to go through all
n elements of a linked list.

355
00:18:09,340 --> 00:18:11,890
If we want to add to the front,
like we just demonstrated,

356
00:18:11,890 --> 00:18:13,750
that will be constant
time, because we won't

357
00:18:13,750 --> 00:18:16,347
have to iterate through
the entire linked list.

358
00:18:16,347 --> 00:18:19,180
But adding to the end is going to
be linear time as well, because we

359
00:18:19,180 --> 00:18:22,240
need to find that last element.

360
00:18:22,240 --> 00:18:25,670
But the nice thing about linked lists
is that they're of variable length.

361
00:18:25,670 --> 00:18:31,810
So unlike arrays, we can keep adding
and adding to linked lists indefinitely.

362
00:18:31,810 --> 00:18:35,890
And I'll just pause here, since linked
lists are a very important concept.

363
00:18:35,890 --> 00:18:40,272
And something that we know that
there can be pretty confusing.

364
00:18:40,272 --> 00:18:42,230
I definitely get confused
by them all the time.

365
00:18:42,230 --> 00:18:44,560
I'll just pause and ask what
questions you have about

366
00:18:44,560 --> 00:18:45,940
linked lists at the moment.

367
00:18:45,940 --> 00:18:52,825


368
00:18:52,825 --> 00:18:54,450
And feel free to send them in the chat.

369
00:18:54,450 --> 00:19:07,200


370
00:19:07,200 --> 00:19:08,790
All right.

371
00:19:08,790 --> 00:19:12,070
Feel free to keep sending
questions, if any come up.

372
00:19:12,070 --> 00:19:15,780
But for now I'm going to go ahead
and move on to our next topic, which

373
00:19:15,780 --> 00:19:17,280
are going to be hash tables.

374
00:19:17,280 --> 00:19:22,170
Which is the big topic in our
Speller PSATs, looking back to that.

375
00:19:22,170 --> 00:19:25,110
The major thing to
remember about hash tables

376
00:19:25,110 --> 00:19:28,270
is that it's just an
array of linked lists.

377
00:19:28,270 --> 00:19:33,550
So here we have a visualization of this
hash table that we're working with.

378
00:19:33,550 --> 00:19:39,490
And you can see over on the left, we
just have this array of 26 elements.

379
00:19:39,490 --> 00:19:42,120
And each of the elements
of that array is

380
00:19:42,120 --> 00:19:44,650
going to be a pointer to a linked list.

381
00:19:44,650 --> 00:19:47,310
And so we can see that like in
the zero index of this array,

382
00:19:47,310 --> 00:19:51,150
we've got this linked list
with just the name Albus.

383
00:19:51,150 --> 00:19:55,530
In the 25th index of this array,
we've got this linked list

384
00:19:55,530 --> 00:19:57,660
with one element, Zacharias.

385
00:19:57,660 --> 00:20:02,340
But we can also see in this element
of the array we've got this linked

386
00:20:02,340 --> 00:20:05,200
list with multiple items here.

387
00:20:05,200 --> 00:20:08,400
And so this is essentially what your
linked lists are going to look like.

388
00:20:08,400 --> 00:20:10,830
Although, in practice,
and for a lot of you,

389
00:20:10,830 --> 00:20:14,490
in Speller, your linked lists
might not be an array of length 26,

390
00:20:14,490 --> 00:20:19,500
they might be an array of length 50,000,
or 100,000, or something a little bit

391
00:20:19,500 --> 00:20:22,720
crazier like that.

392
00:20:22,720 --> 00:20:25,570
The really important thing when
we're creating a hash table

393
00:20:25,570 --> 00:20:28,070
is finding a good hash function.

394
00:20:28,070 --> 00:20:33,640
So a hash function is what we use to
find the array index of an element.

395
00:20:33,640 --> 00:20:38,280
So if I decide I want to add
a new word to this hash table,

396
00:20:38,280 --> 00:20:40,380
if I want to add Carter
to this hash table,

397
00:20:40,380 --> 00:20:44,010
then I'd have to figure out
which index to put it in.

398
00:20:44,010 --> 00:20:47,620
And to do that, I'm going to have a
function that takes in the element.

399
00:20:47,620 --> 00:20:50,160
So in this case, it would
take in the string Carter,

400
00:20:50,160 --> 00:20:52,270
and they would output an integer.

401
00:20:52,270 --> 00:20:55,080
So in this case, we might
want it to output two

402
00:20:55,080 --> 00:21:02,650
here so that Carter could be part of
this linked list with all of the Cs.

403
00:21:02,650 --> 00:21:06,280
Just some properties of
a good hash function.

404
00:21:06,280 --> 00:21:09,290
A good hash function uses
all of the data available.

405
00:21:09,290 --> 00:21:12,820
So if we've got like
a string, we probably

406
00:21:12,820 --> 00:21:15,010
don't want to use only
like three letters of it,

407
00:21:15,010 --> 00:21:16,750
we probably want to
use the whole string.

408
00:21:16,750 --> 00:21:17,920
It's deterministic.

409
00:21:17,920 --> 00:21:19,870
This is the most
important part, is that I

410
00:21:19,870 --> 00:21:22,150
can't have Carter
sometimes mapped to two,

411
00:21:22,150 --> 00:21:24,670
but Carter also sometimes maps to 24.

412
00:21:24,670 --> 00:21:26,920
I need it to always
map to the same thing.

413
00:21:26,920 --> 00:21:30,710
And hopefully it uniformly
distributes data.

414
00:21:30,710 --> 00:21:35,210
So I'll pause here and ask
you all to think, for a minute

415
00:21:35,210 --> 00:21:39,770
or so, about which of
these properties, if we're

416
00:21:39,770 --> 00:21:43,133
thinking about our hash
function here, first of all,

417
00:21:43,133 --> 00:21:45,050
you can think about what
our hash function is.

418
00:21:45,050 --> 00:21:48,020
It looks to me like we're just
sorting things alphabetically.

419
00:21:48,020 --> 00:21:51,210
So like A would be zero, Z would be 25.

420
00:21:51,210 --> 00:21:52,430
And everything in between.

421
00:21:52,430 --> 00:21:55,190
Just based on the first
letter of the word.

422
00:21:55,190 --> 00:21:58,280
And so our hash function would
essentially be taking in a string,

423
00:21:58,280 --> 00:22:03,490
and then converting the first
character of that string to an integer.

424
00:22:03,490 --> 00:22:06,960
And so, I'm curious as
to what you all think

425
00:22:06,960 --> 00:22:09,660
about which of these
three characteristics

426
00:22:09,660 --> 00:22:12,030
are true of this hash function
that we're talking about?

427
00:22:12,030 --> 00:22:13,860
Does it use all the data available?

428
00:22:13,860 --> 00:22:15,060
Is it deterministic?

429
00:22:15,060 --> 00:22:17,860
And does it uniformly distribute data?

430
00:22:17,860 --> 00:22:21,520
So if you could all make a guess
in the chat, that would be great.

431
00:22:21,520 --> 00:22:23,520
And then we can come
together and talk about it.

432
00:22:23,520 --> 00:22:32,790


433
00:22:32,790 --> 00:22:33,290
All right.

434
00:22:33,290 --> 00:22:35,780
We got one person saying
it is deterministic.

435
00:22:35,780 --> 00:22:37,880
And that is great.

436
00:22:37,880 --> 00:22:41,360
If we're taking the first letter of the
word and turning that into an integer,

437
00:22:41,360 --> 00:22:43,890
that first letter of a word
is never going to change.

438
00:22:43,890 --> 00:22:46,100
So, we're always going
to get the same value.

439
00:22:46,100 --> 00:22:49,950
Carter is always going to be two here.

440
00:22:49,950 --> 00:22:52,950
What about using all
of the data available?

441
00:22:52,950 --> 00:22:55,050
Maybe just send a quick
yes or no in the chat.

442
00:22:55,050 --> 00:22:57,750
Yes, does it use all of the
data, or no, it does not?

443
00:22:57,750 --> 00:23:05,580


444
00:23:05,580 --> 00:23:08,640
All right and here we've
got some mixed reviews.

445
00:23:08,640 --> 00:23:11,400
So we've got some people saying
it doesn't use all of the data,

446
00:23:11,400 --> 00:23:13,380
and some people saying it does.

447
00:23:13,380 --> 00:23:18,570
So this is an interesting question,
in that if we're hashing the string

448
00:23:18,570 --> 00:23:22,360
Carter, are we using all of the data?

449
00:23:22,360 --> 00:23:26,940
And in this specific case, with
this specific hash function,

450
00:23:26,940 --> 00:23:28,560
the answer is going to be no.

451
00:23:28,560 --> 00:23:36,700
Because any string with the first letter
C is going to hash to the same value.

452
00:23:36,700 --> 00:23:41,370
So, even though Carter and
Connor are two different names,

453
00:23:41,370 --> 00:23:43,437
and could potentially be
in two different spots,

454
00:23:43,437 --> 00:23:45,270
they're always going
to be in the same spot,

455
00:23:45,270 --> 00:23:49,320
here, because they both
start with the same letter.

456
00:23:49,320 --> 00:23:51,680
So it does not use all the data.

457
00:23:51,680 --> 00:23:54,320
And then what about
uniformly distributing data?

458
00:23:54,320 --> 00:23:56,272
This is a kind of tougher one.

459
00:23:56,272 --> 00:23:58,730
And you might have to think a
little bit harder about this,

460
00:23:58,730 --> 00:24:01,715
but any guesses, yes or no, does
it uniformly distribute data?

461
00:24:01,715 --> 00:24:17,780


462
00:24:17,780 --> 00:24:21,500
All right and it looks like we've got
some mixed reviews on this one, too.

463
00:24:21,500 --> 00:24:25,500
And so, this one really
depends on what you're storing.

464
00:24:25,500 --> 00:24:27,050
So, in this case--

465
00:24:27,050 --> 00:24:30,350
yeah, and someone asked if I could go
over what uniformly distributing data

466
00:24:30,350 --> 00:24:31,010
is--

467
00:24:31,010 --> 00:24:37,940
what it means is that we don't want
a hash table with one of these spots

468
00:24:37,940 --> 00:24:41,420
in the arrays having like 30
elements, and all of the others

469
00:24:41,420 --> 00:24:42,500
don't have any elements.

470
00:24:42,500 --> 00:24:45,230
Because then it's essentially
a big linked list.

471
00:24:45,230 --> 00:24:48,770
And we get rid of our
constant time lookup,

472
00:24:48,770 --> 00:24:51,750
we have to use linear
time like a linked list.

473
00:24:51,750 --> 00:24:56,690
And so, that can be a problem in this
case, because if we're storing names,

474
00:24:56,690 --> 00:25:01,250
I know a lot more people with a first
name that starts with M than people

475
00:25:01,250 --> 00:25:05,610
with a first name that starts
with X. And so in our case,

476
00:25:05,610 --> 00:25:09,920
we might have a lot more people
in the M or T or C or A category,

477
00:25:09,920 --> 00:25:11,990
than we have in the X category.

478
00:25:11,990 --> 00:25:15,950
So it maybe doesn't do a great job
at uniformly distributing data.

479
00:25:15,950 --> 00:25:18,827


480
00:25:18,827 --> 00:25:20,910
And we already talked about
where Carter would go,

481
00:25:20,910 --> 00:25:24,900
Carter would go in this
index two spot here.

482
00:25:24,900 --> 00:25:27,330
And then some general
thoughts about hash tables

483
00:25:27,330 --> 00:25:30,190
it's constant time to add an element.

484
00:25:30,190 --> 00:25:33,070
It's constant time to look up
if your hash function is good.

485
00:25:33,070 --> 00:25:36,770
Like I said, if the hash function
isn't uniformly distributing data,

486
00:25:36,770 --> 00:25:40,630
then we could end up with a really
long list in one of the buckets.

487
00:25:40,630 --> 00:25:43,360
And we don't want that.

488
00:25:43,360 --> 00:25:46,060
And importantly, it is a variable size.

489
00:25:46,060 --> 00:25:50,290
Because we have this flexibility of
each of these spots being a linked list,

490
00:25:50,290 --> 00:25:55,330
we can store as many
elements as we want in these.

491
00:25:55,330 --> 00:25:56,170
All right.

492
00:25:56,170 --> 00:25:58,870
Now we'll move on to talking
a little bit about trees.

493
00:25:58,870 --> 00:26:01,990
So trees are very similar
to the linked list

494
00:26:01,990 --> 00:26:05,710
that we just talked about, in
that the base element of a tree

495
00:26:05,710 --> 00:26:07,490
is going to be a node.

496
00:26:07,490 --> 00:26:09,970
The only difference is
that in a tree, the node

497
00:26:09,970 --> 00:26:12,380
might point to more other nodes.

498
00:26:12,380 --> 00:26:15,880
So, here we have this base
node, or the root node four,

499
00:26:15,880 --> 00:26:20,500
and it's pointing to
a two and a six here.

500
00:26:20,500 --> 00:26:24,970
There are also many different ways that
we can use trees to represent data.

501
00:26:24,970 --> 00:26:28,170
So like in lecture, we talked
about a binary search tree,

502
00:26:28,170 --> 00:26:30,220
and we'll look at one
of those in a second.

503
00:26:30,220 --> 00:26:32,370
But we also in lab use
like a family tree.

504
00:26:32,370 --> 00:26:37,050
Where each node was a child, and that
child pointed to both of its parents,

505
00:26:37,050 --> 00:26:42,045
when we were doing the heredity lab.

506
00:26:42,045 --> 00:26:43,920
When we're starting with
trees, we're usually

507
00:26:43,920 --> 00:26:49,970
going to start with the root of a
tree and then branch off of that.

508
00:26:49,970 --> 00:26:52,220
And for the sake of time,
I'm going to move on for now

509
00:26:52,220 --> 00:26:54,710
and not talk about the
specific binary search tree,

510
00:26:54,710 --> 00:26:56,550
but it was covered in lecture.

511
00:26:56,550 --> 00:26:59,960
I want to talk quickly about tries.

512
00:26:59,960 --> 00:27:03,350
And tries are a lot like trees.

513
00:27:03,350 --> 00:27:06,200
I'm having a little bit of trouble
switching through slides here.

514
00:27:06,200 --> 00:27:07,100
OK perfect.

515
00:27:07,100 --> 00:27:11,250
A tri is a tree where
each node is an array.

516
00:27:11,250 --> 00:27:13,220
So here we can see we
have this root, that's

517
00:27:13,220 --> 00:27:16,250
an array representing all 26 letters.

518
00:27:16,250 --> 00:27:19,970
And then the index of
that array representing H,

519
00:27:19,970 --> 00:27:25,830
is going to point to another node,
and that other node is also an array.

520
00:27:25,830 --> 00:27:30,080
And so the idea here is
that we can store our data.

521
00:27:30,080 --> 00:27:34,550
We can store this name
Hagrid, as a set of arrays.

522
00:27:34,550 --> 00:27:37,550
Where we've got like, this
index points to another array,

523
00:27:37,550 --> 00:27:42,320
where the A points to another array,
where the G points to another array,

524
00:27:42,320 --> 00:27:44,010
and so on, and so on.

525
00:27:44,010 --> 00:27:46,520
And then when we have
a successful word, when

526
00:27:46,520 --> 00:27:49,530
we follow this path all the
way down to get to the end,

527
00:27:49,530 --> 00:27:53,030
then we can turn this green, or
maybe out of value true here,

528
00:27:53,030 --> 00:27:59,510
to show that Hagrid is a
word in our system here.

529
00:27:59,510 --> 00:28:02,720
An advantage of a tri is its
constant time to add an element.

530
00:28:02,720 --> 00:28:05,510
Its constant time to look up an element.

531
00:28:05,510 --> 00:28:07,280
Its variable size.

532
00:28:07,280 --> 00:28:09,680
The big problem with the
tri, though, other than them

533
00:28:09,680 --> 00:28:12,440
being a little bit complicated
and difficult to implement,

534
00:28:12,440 --> 00:28:15,830
is that the size required
to store it can be huge.

535
00:28:15,830 --> 00:28:19,670
So, notice here, just
to store one name, we

536
00:28:19,670 --> 00:28:26,670
needed six arrays, each of length
26, just to store this one name.

537
00:28:26,670 --> 00:28:31,700
So it can get a little bit unwieldy in
terms of the actual size of this data.

538
00:28:31,700 --> 00:28:34,720


539
00:28:34,720 --> 00:28:35,220
All right.

540
00:28:35,220 --> 00:28:38,012
And then lastly, we're going to
talk about stacks and queues, which

541
00:28:38,012 --> 00:28:40,390
are abstract data types.

542
00:28:40,390 --> 00:28:44,820
So a stack is first in and last out.

543
00:28:44,820 --> 00:28:49,140
Which means that the first item I put
into this stack is going to stay there

544
00:28:49,140 --> 00:28:53,260
and it's going to be the
last one to come out.

545
00:28:53,260 --> 00:28:58,025
And so what I mean by that is
that our two functions in a stack

546
00:28:58,025 --> 00:29:00,150
are going to be pushed, so
I want to add something.

547
00:29:00,150 --> 00:29:02,520
Or pop, I want to take something off.

548
00:29:02,520 --> 00:29:05,040
And so if I push the
element five to the stack,

549
00:29:05,040 --> 00:29:07,500
I'm just going to have
this element five there.

550
00:29:07,500 --> 00:29:10,140
If I push another thing
to the stack I push seven,

551
00:29:10,140 --> 00:29:13,330
then I put that on top of five here.

552
00:29:13,330 --> 00:29:16,530
If I push three, I'm
going to put that on top.

553
00:29:16,530 --> 00:29:20,340
And now if I decide to pop something,
so I just call this pop function,

554
00:29:20,340 --> 00:29:22,020
there's no arguments here.

555
00:29:22,020 --> 00:29:25,710
Then what it's going to do is it's
going to do is take away the last thing.

556
00:29:25,710 --> 00:29:27,810
It's going to take away this three.

557
00:29:27,810 --> 00:29:29,670
And it's going to return that to me.

558
00:29:29,670 --> 00:29:32,070
And then if I pop another
element, it'll return

559
00:29:32,070 --> 00:29:36,580
seven it'll take away this seven.

560
00:29:36,580 --> 00:29:38,770
The reason I call this
an abstract data type

561
00:29:38,770 --> 00:29:41,420
is that we can use
different things to do this.

562
00:29:41,420 --> 00:29:43,510
So I can have these numbers.

563
00:29:43,510 --> 00:29:47,920
These five, seven, three, as like
an array, or as a linked list,

564
00:29:47,920 --> 00:29:49,550
or as some other data type.

565
00:29:49,550 --> 00:29:52,600
And so it's kind of flexible,
which concrete data type we

566
00:29:52,600 --> 00:29:56,500
use for this abstract idea of a stack.

567
00:29:56,500 --> 00:30:01,000
And then finally, I'll talk a
little bit about what a queue is.

568
00:30:01,000 --> 00:30:02,350
If I can get to that slide.

569
00:30:02,350 --> 00:30:02,950
Perfect.

570
00:30:02,950 --> 00:30:06,310
So queues are essentially the opposite,
in that they're still in abstract data

571
00:30:06,310 --> 00:30:09,580
type, but they're first in, first out.

572
00:30:09,580 --> 00:30:13,990
And so, we can push this five same as
we did last time, we can push the seven,

573
00:30:13,990 --> 00:30:15,490
we can push the three.

574
00:30:15,490 --> 00:30:18,855
But this time when we say pop, we're
going to take the bottom element.

575
00:30:18,855 --> 00:30:20,980
We're going to take the
element that went in first.

576
00:30:20,980 --> 00:30:24,655
If we push, say pop again, we're going
to take the next element to the bottom.

577
00:30:24,655 --> 00:30:27,180


578
00:30:27,180 --> 00:30:32,600
And so I'll pause there and just ask
a quick question, again in the chat.

579
00:30:32,600 --> 00:30:37,100
Can anyone give me an example of
when we might use a stack versus when

580
00:30:37,100 --> 00:30:38,120
we might use a queue?

581
00:30:38,120 --> 00:30:42,800


582
00:30:42,800 --> 00:30:45,110
I can give an example to start off.

583
00:30:45,110 --> 00:30:47,750
I consider my desk to be a stack.

584
00:30:47,750 --> 00:30:49,260
Because my desk is very messy.

585
00:30:49,260 --> 00:30:52,585
And so when I have something that
I'm working on, I put it on the desk.

586
00:30:52,585 --> 00:30:55,460
And then when I'm working on something
else, I put it on top of that,

587
00:30:55,460 --> 00:30:57,200
and then on top of that again.

588
00:30:57,200 --> 00:31:00,320
And then when I need to-- when
I'm working on things again,

589
00:31:00,320 --> 00:31:03,770
I'll take the thing off the top, and
do some work on it, and finish that.

590
00:31:03,770 --> 00:31:06,510
And then take the next thing and
work on that, and finish that.

591
00:31:06,510 --> 00:31:08,510
So, even though it might
not be the best system,

592
00:31:08,510 --> 00:31:10,610
my desk is a little bit of a stack.

593
00:31:10,610 --> 00:31:11,990
And then a queue would be--

594
00:31:11,990 --> 00:31:14,690
we see those all the time
just in waiting in line.

595
00:31:14,690 --> 00:31:18,407
When you get into a line, the
first one to be in that line

596
00:31:18,407 --> 00:31:20,240
is usually the first
one to get out of line.

597
00:31:20,240 --> 00:31:23,700


598
00:31:23,700 --> 00:31:27,510
And then Carter mentioned that you
want to keep your clothes in a queue.

599
00:31:27,510 --> 00:31:29,130
Which is also a great idea.

600
00:31:29,130 --> 00:31:31,260
If I kept my clothes
in a stack, and I just

601
00:31:31,260 --> 00:31:34,740
took off my favorite pair of jeans, and
put them on top of the stack, and then

602
00:31:34,740 --> 00:31:37,770
the next day, grabbed them
off of the stack again,

603
00:31:37,770 --> 00:31:41,100
then I'm going to be wearing the
same pair of jeans every single day.

604
00:31:41,100 --> 00:31:43,420
And they'll start to smell.

605
00:31:43,420 --> 00:31:48,890
So a queue would be good for
rotating your wardrobe, as well.

606
00:31:48,890 --> 00:31:51,990
That's all I have, right now,
in terms of data structures.

607
00:31:51,990 --> 00:31:54,670
Data structures are
a very complex topic,

608
00:31:54,670 --> 00:31:57,250
and we went over them very quickly.

609
00:31:57,250 --> 00:32:00,550
If you have more questions, feel
free to ask them now in the chat.

610
00:32:00,550 --> 00:32:03,790
But I would also recommend
heading through the lecture notes

611
00:32:03,790 --> 00:32:05,440
from week five.

612
00:32:05,440 --> 00:32:07,630
Or potentially rewatching
parts of lectures,

613
00:32:07,630 --> 00:32:10,670
based on which parts were
more or less confusing,

614
00:32:10,670 --> 00:32:14,410
but I'll pause now and ask what
questions you all have from the chat.

615
00:32:14,410 --> 00:32:18,870


616
00:32:18,870 --> 00:32:22,410
CARTER: Connor, one
question we had was asking

617
00:32:22,410 --> 00:32:26,170
what does it mean to
index a linked list?

618
00:32:26,170 --> 00:32:28,828
Do you have anything to say on that?

619
00:32:28,828 --> 00:32:30,370
CONNOR: Yeah that's a great question.

620
00:32:30,370 --> 00:32:35,260
So, we can-- let me get back
to my linked list slide.

621
00:32:35,260 --> 00:32:38,600


622
00:32:38,600 --> 00:32:49,250
So indexing linked list is something
that we might not necessarily

623
00:32:49,250 --> 00:32:51,000
do in all situations.

624
00:32:51,000 --> 00:32:53,750
And a lot of the times when
we've been using a linked list,

625
00:32:53,750 --> 00:32:57,140
we have not been thinking
about them as having an order.

626
00:32:57,140 --> 00:33:00,980
So, like when we did our
hash table down here,

627
00:33:00,980 --> 00:33:04,520
I won't try to go through all the sides
again, but when we did our hash table,

628
00:33:04,520 --> 00:33:06,830
we didn't really care
where in the linked list

629
00:33:06,830 --> 00:33:10,040
an item was, we just cared
whether or not it was in the list.

630
00:33:10,040 --> 00:33:14,390
But sometimes, the linked list
the order will actually matter.

631
00:33:14,390 --> 00:33:18,200
And so I might want to say, get me
the fourth thing in the linked list,

632
00:33:18,200 --> 00:33:20,610
or get me eighth thing
in the linked list.

633
00:33:20,610 --> 00:33:24,390
And so if I want the 12th
thing in the linked list,

634
00:33:24,390 --> 00:33:27,980
then I'm going to have to go through
the first, second, third, fourth, all

635
00:33:27,980 --> 00:33:32,120
the way up through the 11th,
before I can find the 12th.

636
00:33:32,120 --> 00:33:34,340
And so that's essentially
what I mean by indexing,

637
00:33:34,340 --> 00:33:41,250
is that action of saying get me
the x element in this linked list.

638
00:33:41,250 --> 00:33:44,190
And then I had a question here
about-- going to the slide--

639
00:33:44,190 --> 00:33:48,900
about adding elements, and
finding elements in hash tables.

640
00:33:48,900 --> 00:33:51,720


641
00:33:51,720 --> 00:33:54,040
This slide right here.

642
00:33:54,040 --> 00:33:58,090
And I'll pause and ask if people
have some more specific questions

643
00:33:58,090 --> 00:33:58,750
about this.

644
00:33:58,750 --> 00:34:03,600


645
00:34:03,600 --> 00:34:07,270
CARTER: One thing that I've seen
is a question about is a hash table

646
00:34:07,270 --> 00:34:10,048
the same thing as a dictionary?

647
00:34:10,048 --> 00:34:11,590
CONNOR: Yeah that's a great question.

648
00:34:11,590 --> 00:34:14,469


649
00:34:14,469 --> 00:34:15,719
Let me think.

650
00:34:15,719 --> 00:34:24,620
So, Carter I don't know if you
have a better answer for this,

651
00:34:24,620 --> 00:34:31,560
I'm actually not totally sure how
dictionaries are implemented in Python.

652
00:34:31,560 --> 00:34:35,130
CARTER: Yeah I think that's something
the Python documentation can certainly

653
00:34:35,130 --> 00:34:36,840
tell you.

654
00:34:36,840 --> 00:34:39,389
I think one of the main
things to highlight

655
00:34:39,389 --> 00:34:42,330
is that very similar ideas are going on.

656
00:34:42,330 --> 00:34:46,199
We're trying to basically
map a key to a value.

657
00:34:46,199 --> 00:34:50,219
Like, we're trying to map Carter
to 28, or in a Python dictionary,

658
00:34:50,219 --> 00:34:53,639
we're trying to map name
to the value Carter.

659
00:34:53,639 --> 00:34:56,820
So there's certainly there's this
underlying idea of mapping keys

660
00:34:56,820 --> 00:34:59,650
and values, I think.

661
00:34:59,650 --> 00:35:01,990
CONNOR: Yeah, and an
interesting side note on that,

662
00:35:01,990 --> 00:35:07,130
is that a Python set is
implemented as a hash table.

663
00:35:07,130 --> 00:35:12,415
So if you ever find yourself using a set
in Python, that's why they're so fast.

664
00:35:12,415 --> 00:35:18,950


665
00:35:18,950 --> 00:35:20,373
All right.

666
00:35:20,373 --> 00:35:22,790
Do you think this would be a
good time to move into a walk

667
00:35:22,790 --> 00:35:26,000
through of a practice problem?

668
00:35:26,000 --> 00:35:27,500
CARTER: I think so.

669
00:35:27,500 --> 00:35:29,588
So we thought for the
rest of the session--

670
00:35:29,588 --> 00:35:31,130
let me see if this will work-- right.

671
00:35:31,130 --> 00:35:34,280
We have a practice test question
that focuses on data structures

672
00:35:34,280 --> 00:35:36,950
and our favorite song Baby Shark .

673
00:35:36,950 --> 00:35:39,860
We'll be going through this
in the form of a walk through.

674
00:35:39,860 --> 00:35:42,050
Where you'll be able to
ask questions, certainly

675
00:35:42,050 --> 00:35:44,120
feel free to unmute yourselves.

676
00:35:44,120 --> 00:35:46,810
We're going to pause the stream here.

677
00:35:46,810 --> 00:35:48,000