>>All right, welcome to CS50.
This is the end of week 5,
so I felt that Monday's lecture fell a little flat,
I wasn't really feeling it so I thought we'd try to spice things
up perhaps today with some props.
So I went shopping there in the square.
But first, some good news and some bad news;
which would you like first?
>>Bad.
>>I heard 1 person say good first,
but then everyone else wants the bad news.
Bad news, Quiz 0 is next Wednesday.
But this is mitigated by the fact
that there's no class Monday and there's no problems
with next week as well.
So realize you have a handout in your hands from outside
that describes all of the particulars
for Wednesday's logistics.
Do not come here because of our size,
we'll split up into 3 different lecture halls,
where you actually have a decent writing surface for the quiz,
so that's all there and it's also on the course's website.
If you lose this piece of paper or tuning
in afar do not have this piece of paper,
it's under the "Quizzes" page.
Also on the "Quizzes" page are 5 previous quizzes,
along with their solutions.
I know, this is probably more interesting
than the quiz, but okay.
And actually the segue way here was this is a wonderful way
to waste a lot of time.
Not only was this implemented years ago, actually in ASCII
or ASCII Art, which is a complete tangent, isn't it?
So this was implemented in ASCII Art.
The relevance is that we used ASCII Art for last problem set,
for the game of 15, but we definitely raised the bar a bit
with Sodoku, where you're actually using a graphics
library, called N Curses,
albeit a very limited graphical library.
So this thing used to live on a server that you could TelNet to.
TelNet is like SSH, but it's unencrypted.
So this guy, years ago made this whole animation of Star Wars.
And now there's variants on the web and in Java applets.
But it's pure ASCII Art
for almost the entirety of that movie.
So we'll link to that
on the course's website, if you're curious.
It's an hour or more long.
Now, back to reality.
Let's see, we were on the bad news.
The bad news is that the Quiz 0 is Wednesday,
but there's innumerable resources
on the course's website under "Quizzes" from past quizzes.
Realize that the material does vary somewhat year to year.
So if you see some topic that's completely over your head,
it may very well be that it is completely over your head,
but we might not have covered it, either.
So do consult the syllabus or me or a teaching fellow.
And then also this week, on Sunday, Monday,
Tuesday the sections will obstinately be review
for the quiz.
And then, this Sunday at 7 pm
in Emerson 108 will be a course-wide review
which is optional, but you're welcome and encouraged to go.
It will be filmed and put online by Tuesday.
And this will supplant the regularly
scheduled walk-through.
So there's no walk-through this Sunday,
instead there's a review for this.
And all of that is on your PDF for your reference.
Okay, so let's see.
We did the good news.
No P Sets [assumed spelling], no lecture on Monday.
Which means this last time we'll see you for a week.
But without further ado, some stuff.
On Monday, we talked about pointers.
And we've been talking about pointers.
And this is the last piece of interesting, or dare I say,
complicated syntax that we're going to introduce
in the concept of C. Because once you have this ability
to manipulate memory at your will, you can do a lot
of interesting things.
And also thus far we've not have useful data structures.
You've had these things called primitives.
And primitive is an int, a char, a float.
Any of those little things that you get
for free in the language.
And then we have this data structure called an array.
But it's really just a nice conceptualization of a chunk
of memory back to back to back to back that you can address via
that square bracket operator.
But today, we introduce a fundamentally more interesting
data structure and it's more of a traditional data structure.
Or, as people call it, an abstract data type.
ADT, if you ever see that acronym somewhere.
And that just means that in general,
these more interesting data structures are things
that have data associated with them.
Properties, fields, call it whatever you want.
Pieces of information about variables, much like the structs
that we've discussed, but they also have operations related
to them.
So the thing about C is
that even though we have these structs that we started using
on Monday, just to encapsulate related information.
Those of you who have tackled P Set 4, know that all
of our global variables, which is tucked inside of a struct,
because it felt a little cleaner to encapsulate them.
And this word, encapsulate, is actually a theme in programming
because it means to gather together like, or related, data.
But there's no fundamental operations
that are supported by that struct.
There's no functions related to Sodoku's board.
Anything you do with G dot whatever has
to be done very manually.
G dot X gets some value, G dot Y gets some value.
You don't have any built-in mechanisms.
But now that we start talking
about these things called linked lists,
which will address some weaknesses in arrays,
can we actually say that there's some formal operations,
some features of these data structures that up until now,
we haven't really had.
But why care at all, why not just draw the line after arrays?
Well, arrays are only so good.
What is a downside, in your mind already perhaps, about arrays?
>>[inaudible audience comment]
>>Since it's not been working very well in past lectures,
I felt there are just some murmurings and then I fill
in the blank with my own answer.
So give me a hand, if you would, it's hard for me to hear you.
Okay, black shirt here.
Yes. You're wearing white.
>>[inaudible audience comment]
>>Good, so you need to know the size of the array
that you want before you create it.
And there's a couple of ways we can create arrays now, right?
One is just to declare it statically
within some function, or maybe globally.
But statically in the sense that you start int, then the name
of the array, open brackets, some number.
Closed brackets, semi-colon;
or maybe it's 2 dimensional or 3 dimensional.
But you have to know in advance what that size is going to be.
Or you can also allocate an array dynamically,
which means on demand using what new function
or what useful feature of C?
>>Malok [phonetic spelling].
>>Malok. And Malok doesn't give you an array, per say,
it just gives you a pointer to a chunk of memory that is as big
as you ask the operating system for.
But in the event the OS just doesn't have enough memory
to give you; you ask for 5 gigabytes,
and that's just unreasonable.
What will Malok return?
Quick review.
So it's going to return that null value.
So the best lesson you can hammer into your head
when you're playing with problem set 4,
5 and beyond is anytime you manipulate pointers in C,
constantly, very defensively check for null pointers.
Because otherwise these very bad things known
as Segfalls [phonetic spelling] happen a little too often.
So arrays require that you know in advance how big they are.
And that might be fine because we already saw
in that silly little registrar example that I did
where I inputted students' names and houses and ID numbers.
Well, I can just change the constant, called students,
from 3 to some other value.
So why is that not really a compelling argument that okay,
yes, you have to declare an array's size in advance,
but you can always change it.
What is the downside about that approach?
And recall in that example, there was sharp defined students
and then it was hard coded at 3.
But I could very easily change that, right?
That was the whole point of the constant.
So why is that not really a compelling argument
in favor of arrays?
Yes?
>>[inaudible audience comment]
>>Okay, so causes security vulnerably.
So the fact that arrays are fixed to 1 length and view,
you as the programmer have to check the length of them.
That's the security vulnerability, sure.
But specifically with regard to their size.
Why can I just not say array size can be changed,
just change the constant in your code?
>>[inaudible audience comment]
>>Right. So the user can't do that.
You, the programmer, absolutely can go into your dot C file
or dot H file, change that constant.
But then, what do you need to do?
Recompile, right?
And that's not that compelling.
Maybe now in ES50, week 5, it's pretty easy to recompile,
it's pretty fast because we're only writing so much code.
But if you're Microsoft,
if you're a company that's actually written a program
and ships it in a shrink-wrapped box,
or a user has downloaded it.
No, there's no chance thereafter to change anything
in the source code unless you update the whole darn thing.
So we need some more dynamisms.
So Malok does give us that,
because we can ask the user how many students are in the class.
And then we can allocate using Malok a chunk
of memory that's actually big enough.
But what happens if I start up my program
and I say I have 100 students this semester?
So give me enough memory for 100 students.
So 100 times the size of the student struct.
Okay. But what if there are some late registrants
at the university?
And this happens in every course here.
People add, they drop.
But after the program's already running,
after the program's already compiled.
So I now have an array of size 100, what do I then do
if while the program's running, I need to change its size?
What are my options?
>>[inaudible audience question]
>>I mean intuitively, would you like to do?
Right now, I have 100 students in an array,
but now I'm out of space.
So just intuitively, what would you do?
>>[inaudible audience question]
>>Make a new array, right?
So use Malok again, whatever technique you used the first
time, make a new array, maybe err on the side
of safety, make it 200.
Even though you might waste some memory, and then what do I do?
I have an array that's 100, and an array that's 200.
What do I do?
>>[inaudible audience question]
>>So copy one into the other,
that's a simple foreloop [assumed spelling],
wild loop [assumed spelling], whatever you want to use.
Then what should I do?
>>[inaudible audience question]
>>So free the first array, right?
And you can do this in relatively few steps.
We just rattled off maybe 5, 6 maybe max 10 lines
of code to call Malok again.
To use a loop to copy the contents of the old array
into the new; and then to call free on the original array.
But what do I probably need to keep track of now?
Arrays are just a chunk of memory,
what do I need to keep track of?
If I've now added some more students to this bigger array.
There's murmurings, what?
Okay, the size of it, right?
So this is one of the downsides, upsides,
however you want to view it to see.
The burden is on you to remember the size
of some integer called N. All right, but this is annoying
and we saw this ability in get strings.
You might not recall the CS50 source code, but you do have it
and at this point in the semester,
probably pretty accessible, reading it top
to bottom again at home.
But our get strength function is exactly this.
We took a guess.
We allocated, I forget what the constant is, 128 bytes.
Something arbitrary, but relatively big.
And then we have a loop that says if the user types
in 129th character, uh-oh, let's call a new function
and we actually slightly more fancy use reallocation,
which actually does that copying for you, so you don't need
to resort to the foreloop.
But the same idea this is arguably annoying.
Every time you want to add something to the array,
you have to check its length.
Too small reallocate an array.
That's a lot of minutiae just
to add something simple to your array.
So it turns out that there are data structures
that address this.
The downside of an array is that it's fixed eyes.
Well, why don't we craft a data structure that's
of variable size?
That grows when we want it to, and we don't have to jump
through all these stupid hoops of copying big chunks
of memory again and again and again just
because we didn't have the foresight to know
in advance how big this thing needs to be.
So we can express this data type,
frankly using a pretty clear picture.
So if I have an array, it looks like this.
And this is of size N or in this case size 4.
So I put a bunch of new students in here.
We've got Students 0, 1, 2, 3.
But now I'm screwed if I want to add more students here.
But this new data structure that we'll call a linked list
and is much more compelling is something
that might look like this.
Well, when I have one student,
let's allocate a student object a student struct in C speak.
Well, if I have a second student,
let's create another one.
Another student, another one.
Another student, let's create another one.
And then inside each of these structs,
just as in my example last week.
I had an ID field and I had a name field
and I had a house field and repeat
that for each of these guys here.
I can do the same thing here.
I can do ID, I can do name, I can do house.
But, because I've called Malok for each and every one
of these students on demand.
I need to somehow keep track of where they are in memory.
Because you call Malok, the stuff you get back,
the pointer you get back is not guaranteed,
in fact the pointer you get back does not guarantee it to be back
to back to back to back.
Maybe by chance it will be, especially if we call it
in rapid succession because no one else is using that memory,
but it's no guarantee.
So what you get back every time you call Malok is a pointer
to this thing, a pointer to this thing, a pointer to this thing.
And again.
And now we seem to have a downside.
An array is previously we could remember by way of 1 pointer
or by way of their name.
But how many pointers do I need now
to keep track of my 4 students?
So it seems 4, right?
4 unique addresses, they're not necessarily continuous,
which means I can't use pointer arithmetic
because I got back 4 unique addresses,
they're not contiguous,
which means I can't use pointer arithmetic,
I can't use square bracket notation because that assumes
that requires a leap of faith that everything is laid
out contiguously where it's expected.
So I intentionally left this extra field here.
So if we just are a little clever,
and define our student struct as not only having 3 fields
that we really need, but a 4th field,
maybe we can just string these things together.
We can daisy chain them, if you've heard the word.
So we have a pointer that yes,
points to the very first student.
But you know what?
We don't need pointers separate,
why don't we just include them in our struct?
And somehow link these things together in this fashion.
And the only thing I have to be really careful
about right now is what?
What goes here?
So you need some sentinel value
that will probably be null in this case.
Anytime you need the absence of a pointer,
or null, it's important.
If I hadn't done that, what might happen
if I traversed this list as by in the foreloop
or wild loop just following these pointers.
And how you follow the pointers we'll see some tactically today.
What could happen if this is not null, but some unknown value?
Garbage values, as we keep calling them?
>>[inaudible audience question]
>>A little louder?
>>[inaudible audience question]
>>Yes, you could follow the pointer that just so happens
to look like a number but really leads nowhere useful.
Nowhere you own and so you get
that typical segfall [phonetic spelling].
All right, so let's try to frame this specifically.
All right, so this, I would propose is a new struct
that we use.
And let's simplify.
Let's not use student objects just
yet because there's a whole bunch of additional data
which feels a little complicated to keep track of.
Let's reign it in, assume we're storing numbers, just the IDs.
So I'm going to use that same type of feature before
because I want to call this thing a node.
And so in general, anytime you have these graph-like
structures, these list-like structures in Computer Science
or Math are generally called nodes.
So we'll call this thing a node using the same syntax
as last week.
But, notice 1 difference here.
Last week, when I typed up something,
I didn't type deaf struct.
Name of the thing and then the curly braces the name
of the thing again at the end.
But in structure, notice how 1 of the fields,
even though this is the student version, notice how 1
of the fields needs to point to in object of the same type
as the thing storing this pointer.
In other words, we need a way to be self-referential
and this just means that using the syntax of C if you want
to store inside of a struct,
a pointer to that same kind of struct.
You just have to append its name here,
even though it looks somewhat redundant.
So just take it on faith for now, declare a struct
that is inside familiar syntax and if we want to have a pointer
that leads elsewhere, we simply define it
as struct node star next.
Although, next can be called anything we want.
So what does this mean specifically?
This just means that I declared a structure
that in general is going to look like this,
where this field is called N. This field is called next
and the data type of this thing is what?
[inaudible] That's just an end and this thing,
a pointer to a struct node.
So a pointer to a struct node, or a pointer to a node
if we just want to just simplify.
All right, let's just take a look at what we can do with this
and why we should actually care.
Let me go ahead and make something called List 1,
this is the same printout from Monday, if you have your handout
with you, or there's extras outside.
I'm going to go ahead and run List 1
and to demonstrate this use of linked lists I had
to write a quick and dirty program.
Because just coding up linked lists in no context really isn't
that useful, but if instead run this version here,
what I decided to do was turn it into a little bit
of an interactive interface.
So what's just executed as my main routine.
My main routine has some printout stuff
and it just prints out this quick and dirty menu
when I map numbers to different operations.
So a linked list, as this picture will be generally
called, has a bunch of operations that are inherent
to it, or related to it.
The things people like to do
with linked lists is find things inside of them.
So in this case, I might want to find an integer in this list
to answer questions in the form is this student in the list?
Is this integer in the list?
That's find, otherwise known as search
for any number of other things.
Traverse just means start at the beginning, go to the end
and maybe do something along the way, generally print things
out so that would be the traverse operation.
Insert, as the word implies, means add a number to the list,
but here's where things will get a little interesting
because if you have this string-like structure like this,
inserting can actually be tricky in some situations.
Because if you want to keep this list sorted,
which you probably do
for efficiency reasons, as we've seen.
Can actually search it a little more effectively.
We might want to put the new students here.
That looks like it's pretty easy.
I'll take this arrow and some other arrow in here.
But if it's sandwiched in the middle,
it feels like there's going to be some more code
and some more movement of pointers.
If it's at the end, again, it's a different case.
So this simple idea of inserting a number
into a sorted length list can actually be broken
down into 3 cases.
Beginning, middle, end.
And hopefully we can generalize in that way.
And delete, the same thing.
If I want to delete an arbitrary student or link from the list,
I might have to treat the front guy a little differently
from the end guy because they look different
from everything else in the middle.
So this is consistent with this idea we've been preaching
of design.
How can you break a problem down to its constituent parts?
Well, there's 3 cases, beginning, middle, end.
And that's precisely what we'll do.
So right now my length list, according to this program,
has nothing in so I'm going
to go ahead an insert by typing, "3."
It's going to ask me a number to insert and I'll say 50, enter.
So list is now 50.
So this is a very ugly, quick and dirty program
that I just spit out what this list currently is.
Let me insert another number.
Let me go ahead and insert.
Let's say the number 61, enter.
Program seems to be working.
I've inserted 50, then I inserted 61.
And maybe it was just appended,
but hopefully it's actually been appended
in sorted order, let's try again.
Insert 51, which will hopefully end up in the middle.
And yes, indeed, and we can continue along this way
and we'll insert 1 more for demonstration's sake.
And we seem to have a running list that if it's consistent
with what we're talking about here, is growing.
And is growing, and is growing.
So a very underwhelming program.
We could have implemented this a week,
2 weeks ago just using an array but if I start inputting
in enough numbers, as you pointed out,
eventually we're going to hit a hard coded limit
at which point you have to do this somewhat annoying,
somewhat time-consuming process of creating new array,
copying the old into the new and then repeat.
Now, give the examples we've discussed.
Students and the example last week,
it's really not such a big deal.
Looping from 0 to 3 or 0 to 10 or even 0
to 1,000 is really not all that problematic.
So why do you think that this constant resizing
of arrays might actually be a bad thing?
Why bother introducing what seems to be more complexity,
even though you could have solved this problem last week
using the semantics of last week?
At what point does that approach
to dynamism growth become a problem, do you think?
>>[inaudible audience question]
>>Yes.
>>[inaudible audience question]
>>Exactly.
When the time actually gets noticeable, either to your CPU
or worse to the human.
So a number of you have posted questions
on the course's bulletin board about problem set 4 in Sodoku,
like, is it okay to exhaustively check the whole board this 9
by 9 grid that's 81 separate cells.
It feels like a lot but again you have a billion hertz
at your disposal.
You have a gigahertz, 2 gigahertz.
Checking a 9 by 9 grid that's really meaningless.
And we saw as much when we talked about amitotic behavior
and we did some searches and sorts for small data sets.
The running time is fairly negligible, but these days,
and after a class like this, you're going to start playing
with much more interesting data sets, whether it's
because of computer science, or you go back to your bio labs
or your chem labs, where you actually had interesting sized
data sets.
Again this na�ve approaches, these week 2 approaches
of storing things contiguously in memory probably aren't going
to cut it because you're going to start to incur the costs
of time, of space, of CPU cycles.
All of that begins to add up.
So, how much do we go about doing this?
Let's take a look.
In this code is list 1 dot C. And we have the following setup.
Let's just glance at C for the moment.
So main looks like it's pretty simple here.
Print def I have some new lines, and this is a little trick.
If you've never picked up on this before,
or haven't seen it in a TF do it.
If you have a multi-line string, it's not the best thing
to call print def, for instance 6 or 6 times here
because anytime you recall a function,
you actually incur a bit of cost because of all
of the stack frame stuff that we discussed.
So you can actually call print def 1 as a multi-line string
and notice I have not put semicolons at the ends of any
of these lines but I have closed the strings
in double quotes each time.
All right, so scrolling down,
it looks like I'm using CS50's library, telling the user
to give me the command.
I'm using the perhaps now familiar script construct,
though I could have used an if-else.
I have 4 cases, I call a specifically named function
that's in the case that we need to delete, find,
insert or traverse the list
and then again we do this wild construct
because it's a user interface.
Well, let's see a hint of the notation here.
It looks like I'm doing some stuff with pointers
at the very end, just to free the whole list.
And that's consistent with this idea of managing our own memory.
But how do you represent linked list in the first place?
Well, if you have an empty list,
how can you represent an empty list?
What primitive do you need,
I potentially left the answer on the board.
How do you represent an empty list, what do you need?
Do you need a struct?
Do you need to call Malok to represent a list of size 0?
No, you just need what?
>>[inaudible audience question]
>>So a null pointer.
Where can you store it?
Looks like in this program we've decided globally
to declare a pointer called first.
It's a type of node star,
which means that this thing is just going to hold an address
of the thing that it's going to point to, is going to be a node.
So that's all that's saying, and it's consistent
with last week's definition of pointers and we're going
to initial it to null.
Which is to say, in the context of a data structure like this,
we simply want to create a new list
or represent a new list we won't have had occasion
to call Malok yet, so we won't have an valid addresses,
so we simply need to declare 32 bits of memory.
We'll call this apparently first.
And what's going to be inside of it?
Well, unless we assign it a value,
it's going to have junk in it.
Which is why in this case, we've initialized it to null.
So that's it.
So now think just conceptually.
When I call the insert function.
When I type in the number, what was it?
3, the insert function is called and I type
in thereafter the number 50.
So that's what I did in the little demo a moment ago.
What is the insert function probably doing?
Step 1. The insert function, based on the behavior
that we saw, is doing what first?
And just to remind, so if I run this linked list program,
and I type in 3, what's it doing first?
So it's doing a print def, and then I'll only jot
down the more interesting 1, it's doing a get in.
Right, it's probably using the CS50 library also.
And here's where I typed in 50.
So what did it do with this value?
Get it? It probably stored it in,
and I'll write slightly more complete code,
it probably stored it in a local variable called N, or whatever.
So N equals get in.
This is probably the code that was just executed.
What it probably doing is step 2, when I then proceeded
to hit enter, thereby putting a value in N. If the goal, again,
is to construct dynamically,
one of these things called a linked list.
Just conceptually, what did it have to do?
>>[inaudible audience question]
>>Sorry?
>>[inaudible audience question]
>>Okay, so it's got to somehow set this pointer,
which has up until now still null, to point to this value.
So we can't- this is not a pointer to an int,
so we cannot do, for instance, this.
We cannot, if this is the int in memory,
we cannot just have the pointer point to that int
and no longer be null because what is this a pointer to?
Not an int, but-
>>[inaudible audience question]
>> A node, okay.
So how do we make that happen?
If we need to have this pointer point to a node,
and all we've got in memory at the moment is apparently an int,
what do we need to do, or who do we need to call?
>>[inaudible audience question]
>>All right, so we call Malok.
So we call Malok with something like this.
I'm going to do a node star.
So this is pseudo-code at the moment.
So I'm just going to use PTR,
this is a constant variable people use as pointers.
So this gets what?
I need to call Malok, and then what do I ask Malok?
1 node, as I ask in that slightly sarcastic voice,
the answer is no.
So what do I put in here?
>>[inaudible audience question]
>>Yes, so size of the node.
So we need to ask Malok for a specific number of lights.
Now maybe I know how many bytes there are in a struct.
In fact, if I think it through, a struct called node has an int.
If it has an int and a pointer,
I actually can guess how much space it's going to take up.
How many bytes is a node struct can you infer?
>>[inaudible audience question]
>>So it looks like it's 8.
Because I need 4 bytes, 32 bits for the int.
And another 4 bytes, 32 bits, for the pointer,
because all pointers are 32 bits in this environment.
So that means 8 bytes so that means I actually go a bit
riskily type in 8 there and get the number of bytes I need.
This is not a safe assumption to make,
because it's not necessarily the case that the compiler
or the computer is going to give you just 8 bytes.
There are cases in which you actually get back more bytes
and things would so let's instead use the size
of the operator.
I pass in the size of what?
Not ints but node and now, dynamically,
I will hopefully get back either a null pointer,
but that's pretty unlikely given how few things I've asked
for so far, or I'm going to get back the address of a chunk
of memory that is now mine to manipulate.
Now this is just raw memory but the neat thing is
that I can treat it as this is a node.
Because the thing about C is that just handed a chunk
of memory that has no data type associated
with it fundamentally, you if you know how big it is,
can just assume that you can treat it
as the struct in question.
So the fact that we're saying node star pointer means
that with the memory I'm getting back,
even though it's just a generic address, I'm going to proceed
to treat it as though it's the address
of a node struct in memory.
So now what do I do in step 3, most likely?
I've got an N and an int.
I've got the address of a chunk of memory
that I can use for a node now.
What do I need to do as the next step to create the beginning
of this linked list structure?
What needs to happen next?
So here I have, just pictorially, my int,
it's got my number in it.
This thing's a little bigger
because it has 2 fields ready and waiting for me.
So what do I need to do?
>>[inaudible audience question]
>>Yes, so put the int into the node, so how do I do this?
Well, we've seen that we've not used it that much.
In fact, before, if I want to go into that address and follow
that address to the memory location, but I want to go
to a specific field, the notation is this arrow notation
so I'm going to go pointer, arrow and then the field I want
to update is called what?
>>[inaudible audience question]
>>Little bolder.
N, right? So go to that address, go the field.
I have defined as N and assign it a value
of N. Now you might be recalling issues of scope,
you might recall when we had the same variable names before
was problematic.
But this is okay, because the compiler very quickly realizes
that you want the variable called N, the field called N,
that's associated with this pointer,
with this chunk of memory.
Whereas N just in this vacuum clearly refers
to the local variable that we're using here.
And let me reangle this, in case those of you
on the side are having trouble.
So there's 1 last step to clean
up the memory I've just been given.
I have this.
I have the same memory question mark question mark But,
at the top now, I just have the value of N is,
so let's put 50 in here.
50 is now also in here, but what's this?
>>[inaudible audience question]
>>It's just garbage value.
Because it's just a chunk of memory I've been handed.
So step 4 is probably going to be to do what here?
>>[inaudible audience question]
>>So create a null pointer.
And it's probably not the best verb to use,
since you don't actually create pointers.
This is just a hard coded value of zero,
but that's the right idea.
The next field of this struct is just going to be null.
And now what I have is something that looks like this, 50,
and then null field here
and actually I'll draw it graphically,
but what most people do
to represent null is just a backslash, or some kind
of angled slash in the box.
Okay, now that's step 4,
but I haven't actually created a linked list.
At this point in the story,
my linked list appears still to be empty.
So the fifth and final step is going to be what here?
What needs to happen now?
So we're so close.
We have this thing just floating somewhere in memory
and that's fine, because memory does not need
to be contiguous for lists.
This thing here is our global variable called first,
which we initialized per the code we saw,
is initialized to null.
So in order to literally connect these things,
what do I need to do?
>>[inaudible audience question]
>>Yes, so assign first the value of pointer.
So the last step is first get, which is currently null.
Let's overwrite the value of null with the address
of this struct in memory.
So pictorially, what I just did in step 5,
is that I changed the value of first to be from null
to being something like O, X, 1, 2, 3.
Or wherever this thing happens to be in memory,
but that's not really interesting any more.
The specifics anymore, so let's just draw it
with our familiar value notation.
Now what I have is that.
So to do recap in step 1, this old school stuff.
Get the ints.
Step 2, allocate space for the structure that's going
to store that int.
And another pointer, so metadata, if you will.
So that we can string these things together.
Then what do you do?
Put the int into that structure.
What do you do then?
Put null in the next field of that structure
so that you don't reach a garbage value
and assume more things in this list than there are.
And then finally, you just need to link things together.
Your list was previously empty.
You now need to wire things together.
So now what do I have in memory,
even though this thing's a bit messy on the board,
let's spin it around for 1 final clear picture.
Our linked list now is quite simply first
and then we have the number 50 stored in a node here.
This arrow points here, this is a null pointer.
Voila. That's our linked list.
Now, this felt like a lot of work.
It's easy to create an array with the number 50, done.
We did that last week, we just syntax int.
We'll call this array, bracket, 1.
So we've just done a lot more work.
But, if we now factor out these concepts, these operations,
like insert and later delete, spine and traverse.
Then you just have to call it a function.
Hand it the linked list, or have it have access
to this first pointer, and then you can repeat these same
operations again and again and you
as the programmer no longer have to worry
about how big this structure needs to be
in advance unless the user really wants to push the limits
of reality and ask for billions of things, which again tends
to run afoul of some real world limitations.
So, any questions?
So that was either really clear or really confusing,
and I'm not sure which, so I'll ask you again.
Any questions?
Well that's good.
Thank you.
So I'm not sure you can see this,
but thanks to Harvard's financial crisis the temperature
is intentionally being raised in the rooms so I apologize
if you can see the glistening here.
But, let's now put you guys in the spotlight.
So we're not going to use the clay.
I'm not sure I can take myself seriously playing
with Play-Dough in science [phonetic spelling] theater.
But if we could get 4 humans up here, we won't be playing
with this, you'll be a compliment to the clarity.
So come on up, you're number 1.
Someone else, yes in front?
2. And you do have to be comfortable,
yada yada on film here.
3. And 4, you stood up so you nominated yourself.
Okay. So we've done things like this before
and I'm always amazed by how many humans are willing to come
up here and do these silly things.
But what I hope is that what we just did
on the board is very easily forgotten.
It's fairly esoteric kinds of low level details.
But let's see
if the visualization doesn't make things a bit clearer.
So let me go ahead and I'm going to use 3 of you guys,
just as a chunk of memory.
So if you could duck off to the side, for just a moment.
We're going to allocate you in a moment.
And you're name is again?
>>Alex.
>>Alex, you are a pointer.
So you're a null pointer,
it's just say you keep your hands at your side there.
Just don't point at anyone just yet.
So you guys are a chunk of memory.
So you are RAM.
And now, we'll start with small numbers.
I decide here that I want to insert
into this currently empty list called Alex.
A number 2.
So I call get int, I am handed the number 2.
What's my next step?
Malok. So I'm going to allocate memory.
I'm going to ask the operating system
for 8 bytes of RAM please.
Nominate who you will.
Okay. So I get back a pointer to- your name is?
>>Olga.
>>Olga. So I get a pointer to Olga here.
She is 8 bytes of memory.
I'm now going to do what, with respect
to our chunk of memory here?
>>[inaudible audience question]
>>It's not fun if we're the only ones playing this
awkward exercise.
I'm going to store in the field called on, which they're going
to represent with their hands, just as Alex is doing.
And value 2, and why don't we stalk here just
on the side a little bit so we're out of the way.
So now she has a pointer.
And your left hand is your value
and your right hand is the pointer.
Or actually, let's do the opposite.
That way, that'll make sense.
So now we were at wherever we were-
this is, we just did step 3.
So actually, we're almost there.
So that's step 3, but we really don't have a linked list,
we've got a null pointer and we've got a chunk
of memory only half of which has been used
in an interesting way by storing 2 there.
What do we now need to do?
So we now need to store a null pointer here.
So for dramatization's sake,
can you make a garbage value with your left arm?
So that's before, and now we initialize your pointer to null.
Excellent.
First time we've ever done this demonstration in CCS50,
so we're figuring out as we go.
So now what's the fourth step?
>>[inaudible audience question]
>>So actually point the first variable, that's right,
to this new chunk of memory.
So Alex, your time to shine.
Excellent.
Good. So we've now just recreated what we had
on the board, except with a slightly different number.
So now things get a little more interesting, though.
Because now I get a little greedy and I decide that I want
to put in, say, the number 3.
So I call get int.
I am handed by the user the number 3
and I just side step 2 to call Malok again.
So Malok away.
Hello, what's your name?
>>Julie.
>>Julie is returned to me, the address of Julie.
She too has in her right hand space for an int.
And in her left hand, what's in both of- oh,
this will embarrass you.
What are your 2 values right now,
we need you to represent 2 garbage values.
Thank you.
So now we store in Julie's N field
in her right hand is the value 3.
What do we do for step- let's keep track
for those following notes.
We just did step 3, step 4 is to do what?
>>[inaudible audience question]
>> Good. Assign null to her left hand.
Done. And step 5, finally, is to have what?
Alex point at Julie?
>>[inaudible audience question]
>>No, right?
So, what do we need to do if the goal,
to be clear, is to sort the list?
So here we need actually a bit more work.
Here we need a temporary pointer.
So I'll play that role, and I need to initialize myself
to the start of the list.
What does this mean?
It really means that I'm going to point
to the same thing Alex is pointing at.
So now I'm going to check, let's check Olga's N field.
Is 3 less than 2?
No, so I'm going to keep going.
Now, unfortunately, I'm pointing at nothing.
Which means I've reached the end of the list,
because Olga has nowhere else for me to go and so this implies
that this number 3 goes here.
So now, very carefully, and we haven't walked
through these steps, what needs to happen now?
To add Julie to the correct location on the list?
1 step, in fact.
Your time to shine.
>>[inaudible audience question]
>>Very good.
But for intentionally plucking off some of the easier ones.
Now, finally, we're going to go with the number 1.
All right.
So things get a little trickier.
I call int, I store number 1
in my variable called N. I then call Malok.
Hello, what's your name?
>>Robert.
>>Robert, nice to meet you.
So you look like what at this point in the story?
That's great.
So now we assign you this number 2 N,
which goes in this hand here.
Now, again, Robert, if I can drag you in this direction.
You're anywhere in memory.
So you could be here, okay.
Yes. Can't see in the camera.
So now Robert has his N field initialized.
Left hand is still doing whatever.
So step 4 here is nullify your pointer.
Good. So now he's in good shape.
So now it's my turn, the temporary pointer and I have
to have some kind of loop again.
Maybe it's a foreloop, maybe it's a wide loop so I point
where Alex is pointing.
I then check, does Alex belong here- sorry,
does Robert belong here?
Yes, to the left of Olga.
So now there's a bit of trickery.
So now let's see what we need to do?
What would you, the audience propose that we insert Robert
into the right location here?
What's the first step?
By a show of hands, so we can actually pinpoint the voice?
Yes, in back.
>>[inaudible audience question]
>>Alex has to point to Robert.
Alex, please point to Robert.
Okay, now what?
>>[inaudible audience question]
>>Yes. So now dangling pointer, as this is called.
Because we've now lost Olga.
We've lost Julie, which means you've just cost us a lot
of RAM.
Now your computer is going to slow to a crawl.
But thank you for playing, that's good.
Let's roll back.
R, Control C back up.
Rerun the program here.
And again, Alex is pointing at Olga, we do do this check,
we realize Robert doesn't belong to the left,
let's do a new first step.
>>[inaudible audience question]
>>Okay, so Robert points to Olga.
Robert points to Olga, looks a little weird
but maybe this is okay.
Then what?
>>[inaudible audience question]
>>Now Alex points to Robert.
Now, this is actually realistic in that the memory can be all
over the place for visualization's sake,
let's cheat and have Robert come
over here even though he really is anywhere in memory.
But now notice what's- so that was actually a bad part
of the visualization, because the compelling thing
about linked lists is that you don't actually have
to shuffle people all around.
And this was one of the problems initially with arrays,
which is if you wanted to insert something
in the middle, we had a problem.
We saw this with our searching algorithms
and our sorting algorithms.
And if we wanted to put somebody into the middle,
we had to shift all of those people over.
But as soon as we started shifting,
we started increasing our running time,
and we started devolving, if you recall,
to things that are quadratic and no longer linear.
But yes, even though the humans here didn't need to make room
for the addition of Robert, technically,
they're just updating pointers.
So the first pictorial with him way over there speaks
to the fact that it's much more efficient to insert here
because we don't need to worry about contiguousness
of all of these elements.
But big round of applause if we can for these 4.
[ Applause ]
>>We have a little parting gift here for you today,
I'm not sure how you'll use this.
But thank you, let's take a 5 minute break.
And you people, I need to see you in the corner.
>>I already signed this.
>>Okay.
>>All right, we are back.
Brings the fun to a crashing halt,
because now we have some code on the board.
So you have, in your slides, that will be available online,
there's actually a number of depictions
of what we just did with humans.
So realize and refer back to this couple of weeks time,
because what this is meant to seize your minds for,
for problems that sticks, which is a little bit aways away
but it's problems in t6 you'll find
that your challenge is implementing the fastest
spellchecker possible.
And we pretty much take off the training wheels at that point
and encourage you, and invite you
to implement your own choice of data structure.
We haven't seen many yet, we've seen linked lists,
but you'll find that these linked lists
from today will become a building block
for much more sophisticated data structures
that we do in 2 week's time.
So these pictures realize walk you through the process
of what just happened, perhaps a little quickly
with humans on stage.
But what I'm going to do instead, instead of walking
through this again and again,
which is what we pretty much just did,
let's focus on the actual implementation of this.
Because some of the syntax is new, but hopefully the concepts,
once visualized with some people is now a bit more clear.
So this is the guts of the insert function.
So again, you'll have a printout of this, this is list 1.C.
In lists.H, note actually has the definition list 1.H has the
definition of the struct.
Just to be clear, I factored it out to this header file,
which again is pretty typical and any time you want
to declare some data structures or you want to create a file
that other people might also use via sharp include.
So here's the function insert.
It takes no argument because we're going to ask the user
for a number to insert this coin.
But notice what I'm first doing.
I've decided at the very start of the function called insert.
Try to substantiate a node for the number.
Now I'm doing this because I know that once I get a number
from the user, I've got to tuck it away inside of things.
So the order of operations here is a little different
than we did verbally, but we're going to cover the same steps.
So the syntax for this is, give me a pointer called New Pointer,
could come up with most any variable name there,
and it's of type node star.
Let me scroll back to that.
So it's of type node star, which means give me a pointer
to a struct that a type node.
Okay, I'm calling Malok, passing in the size of a node.
And just to be clear, why not just hard code the number 8?
Why incur the expense of calling this?
Yes?
>>[inaudible audience question]
>>In case you want to enlarge the struct, and again,
even though this is more of a corner case
but we can see a taste of it in problem set 5,
forensics problem said you're not, even though we draw N
on top of next sort of back to back in our picture,
that doesn't mean they're going
to be perfectly back to back in memory.
Now, in this case, in reality, they probably will.
But if we start creating data structures
that don't have these 4 by values,
an int and then a pointer,
or maybe a char another char, a float.
And then you start to comingle lots of different data types
for efficiency's sake what the computer will do is word align
these values, which just means that it's going to try,
for efficiency's sake, to line them up every 4 bytes
which means you might have gaps.
Another motivation for actually keeping track
of this thing here by a size.
So here's a little sanity check.
If I get back null, just return.
Now I don't bother in this particular demo
to tell the user anything.
I just ignore the user.
So it's unfortunate,
but at least we handled the return of null.
Because if you take a null pointer and try to follow it,
you will in fact segfault.
And that's a feature of the language.
Null is a constant that represents the number 0.
The number 0 is a valid address and memory.
Right? 0 byte of RAM, but the authors of C essentially decided
that this byte will never be owned by the user.
So it will always trigger, a segfault,
so you know there's a problem.
So that's actually a good thing, initialized to some known value.
So here's what our first step was.
Printout, number to insert.
Let me go into that, and actually saved a step here.
Didn't bother wasting the space for a local variable.
I just flopped to the end
of the user give me directly into the struct.
Reasonable optimization, but it achieves the same task.
But then I do very carefully initialize the next field
of my node pointer to null.
So that's precisely what we did
on the board and pictorially here.
Now I'm just going to check the 3 cases.
So at this point in the story, we had Olga holding a number
and then we had Alex pointing at nothing.
So we now needed to consider the scenarios.
Is Alex pointing too something?
Because if so, we're going to have to traverse the list.
If he's pointing to nothing, that's actually really nice
because it's really easy to code.
If Alex is currently null,
if the first pointer is null, well this is so easy.
First gets new pointer.
Just make Alex point at Olga as he did, then we're done.
But there's a couple of other cases.
Apparently, I need to check if the number belongs at the head
of the list, the start of the list, or if it belongs
in the middle or turns out you can model the tail,
the end of the list, in pretty much the same way as the middle.
And the only way you would realize this, frankly,
is by thinking it through.
This is not necessarily obvious.
But let's go with the slightly easier case.
I like 2 lines of code instead of several there.
So case 2 is, if the number we just inserted belongs
to the list's head.
So now fast-forward to the situation involving Robert.
Robert was number 1, he belonged to the right of Olga.
So Alex would have to start pointing to him,
so the case there, we had them update 2 things.
And we didn't quite get it right at first,
but we did subsequently.
We first told Robert to point at first.
Wait, I'm a little confused.
Isn't first Alex?
Why does this actually work?
What is first?
First is a pointer, it's an address.
What's it the address of, to be clear?
So it's Olga.
So even though we talked about Alex
and representing this first pointer, the value of side
of him actually represents the address of Olga
at that point in the story.
He's just a container storing an address.
So when I say that the new pointer's next field equals
first follow Alex's hand, which leads to Olga and store
that address inside that field.
So it's the same thing, but just realize
that Alex himself was not a node,
Alex did not have 2 fields, he just had an address
which is why this direct assignment makes sense.
Now we told Alex, go ahead an update yourself
to be the address of this new node, that is point to Robert.
So at this point, I'm not sure whether your mind prefers the
model of just thinking about things as arrows
and human's pointing at each other, or if you prefer thinking
in terms of addresses,
this approach too is literally a translation of what we did
in that demonstration.
So if you're more comfortable thinking of things as addresses,
if you're more comfortable thinking of them as arrows
or hands, that too is fine.
Now let's glance at the slightly more complicated case
and this is where your brain gets a little squeezed
because you have to very carefully consider how
to do this.
But thankfully, you do it once,
and then your insert function works.
So let's consider, ideally without getting lost,
how we go about inserting in the middle of the list
or to the end, the tail of the list as we did with Julie
in that second scenario.
So what I'm going to first do is this apparently my role.
When I came over,
I was pred-pointer, predecessor pointer.
And I chose these variable names just to be consistent
with the textbook's figures.
I pointed at the same thing Alex was pointed at.
So that highlighted line of code is exactly what I did,
with that temporary variable called,
apparently, pred-pointer.
Now I just need an infinite loop, and it's okay
to produce an infinite loops using fore or wild,
so as long as you are sure, logically, that you break
out of it, if that's your clear goal.
So I'm first going to check this,
and we didn't bother doing this
because I didn't print duplicates on paper,
but I am going to check.
If the pred-pointer is end field equals the new nodes end field,
we'll forget about this.
I don't want duplicates in this list.
This is an undocumented feature of the demo that we just did.
This feels a little foolish, though.
So some of you might notice, I just wasted some time
and allocating a node at the top of the file,
the top of the function using Malok.
And yet this feels dumb.
Only then do I check for duplicates
and deallocate by calling free.
What would be an alternative to this because this feels
like I'm wasting time by allocating the node
and then realizing, damn I don't need this node,
here it is back by calling free.
What's an alternative to that approach?
>>[inaudible audience question]
>>Yes.
>>[inaudible audience question]
>>So just intuitively, I'll just do a pre-check.
Let me run through the whole list, which is pretty easy to do
with the foreloop and I just did it by pointing again and again
to the humans on stage.
Let me just do a sanity check and if I find a duplicate then,
maybe then I can actually quit.
But now I've essentially doubled my running time
because if I do this pre-check, I have to linearly go
across the whole list, then I might say there's no duplicates,
now I have to find where to go.
So that would work maybe we could do slightly better.
And maybe better just means let me just allocate the moment I
need it, this node, and don't do it at the front of the list.
In other words, let me go ahead and copy these lines
and down here, when I actually needed the new node,
I could insert this code here.
But the reason I didn't is that I have these multiple cases.
If I had done this approach, allocating this node on demand,
now what do you notice me doing, which is generally a bad thing?
>>[inaudible audience question]
>>Copy paste, right?
Duplication of code, there's clearly an opportunity to rip
that code out, so it's just a trade-off
and it's a design decision that one could argue.
Maybe either way, but generally when you resort to copy paste,
there's probably a better way.
So at this point, we're going the right direction, it seems.
I have my node and maybe duplicates are a rare thing.
So maybe we could argue that it happens so rarely, who cares?
Every once in a while we spend a few extra cycles.
That's a reasonable decision to make.
So let's see.
Check for insertion at tail.
So there's 2 cases in this bigger case.
Is it in the middle, or is it the tail?
After a lot of thought, and maybe some trial and error,
I realized that it's a little easier for me
to check insertion at the tail.
So if the temporary pointer, me, if I'm pointing at nothing,
as I was in one situation when we were inserting Julie,
then it's actually a really easy case.
Go ahead a new structure, go ahead an point to the end
of the list, whom I'm currently pointing at, to the new node.
And again, I won't go too long on too much of the code
because I know it's easy to get caught
in some stupid little detail and that's fine reasoning through it
with the picture in hand can certainly help afterwards.
This is just the translation of what I did to insert Julie
at the end of the list when only Olga was there.
The list was size 1.
So now let's assume, and we didn't do this per say,
because we inserted Robert at the beginning,
not at the middle, but there is this last case.
So this is interesting.
You can actually chain together this arrow notation.
If I am the temporary pointer, pred-pointer,
and I follow the next field and then I follow
down into the end field, so gone 2 steps.
If that equals the N in the new node,
I know that this node belongs somewhere in the middle
and so I need to update 2 pointers here.
And again, I don't want to dwell too much on the syntax here,
because I think it's best done by drawing a picture
on the sides, thinking this through.
But the takeaway, that I think is interesting,
that there just needs to be 2 pointer updates.
So we've really only seen 2 general cases.
1 pointer update, which was terribly easy,
and that's why we did those examples first,
and that's why I myself coded them up first
and the only more interesting examples is
when the thing belongs to the list's head,
we realized we needed to update 2 pointers in the proper order,
and similarly if it belongs in the middle,
just conceptually we have someone here,
someone here- certainly we need to update 2 pointers
so they point to me and then I point to them.
So the reason for this double traversal is
because once you go left, you can't go right
in a singly linked list.
A singly linked list, by definition,
has only single lists going in 1 direction.
So as this picture here depicts, this is how it relates
to deletion, which is the same idea when searching
through a list and then wanting to delete a node,
what do we do- let's actually do insert in the middle.
And this is the one with several steps.
If we want to traverse this list, notice,
just as the arrows indicate, we can only go left to right.
So it turns out that sometimes, for programmer's convenience
or for algorithm's sake, you can throw more metadata
into these structures, there's nothing stopping us
from having not only a next pointer,
but also a previous pointer.
Because in fact, it would have simplified some of my code
if I had the ability to traverse the list this way,
and then looked backwards
because then I could have eliminated, if you look closely
at the code in problem set 6, I could have eliminated one
of my temporary variables.
Because, again, in that code I had myself
and then there's also a temporary variable who's
essentially following what's going
on in the story a left hand and a right hand, if you will.
But if I have the ability from any node to go left or right,
can I then get rid of one of those temporary variables?
But this, again, hints at this trade-off.
I can double my number of pointers,
save myself some thought, saver myself some logical coding,
but the downside of course is that I'm spending twice
as much memory on these pointers.
But here's another question,
and this picture spoils the fun answer.
How do you determine the length of a linked list,
according to how we've implemented it thus far?
Which is a picture more like this.
How do you determine the length of this thing?
>>[inaudible audience question]
>>Just traverse it, right?
Start at the beginning, start where Alex was,
and go duh-duh-duh-duh, following the arrows and as soon
as you hit what do you stop counting?
The null. As soon as you hit the null pointer,
which was originally at Olga then at Julie,
their left hand was null, then you know that you're at the end.
And so long as you are keeping track
with an N plus plus plus plus,
you know that the list if size three.
But that's a little inefficient.
Here, too, is this trade-off.
We could probably spend 32 more bits up front
and actually avoid having to recount the length of this list.
If I'm writing some programs that constantly requires
that I know the length of the list,
why not just compute it once, and keep that answer around.
So what this picture also hints at is
that Alex did not need to be so simple.
He did not just have to be a pointer to a node.
He himself could have been an entirely separate structure.
We've seen how to define a struct.
Type def struct and then some name,
whatever you want to put inside.
We could have made Alex a special struct
that we used 1 copy of, 1 of his fields is
in fact a pointer to a node.
But his other field maybe is, as this picture implies,
an int, the size of the list.
So what I could go do, is go back through all of my code
and go back through all my demonstration
and every time I insert, say, Julie.
Every time I insert Robert, not only do I update the 1
or 2 pointers that a requisite for that.
I also do what to keep track of the current length?
Then do the plus plus there.
So again, this hints at the opportunities that you,
as the designer as a computer scientist has
to solve problems more efficiently.
If you don't want to waste time again and again.
Incur linear costs, linear costs just to compute the size
of something, the length of something, you can solve
that a priori by keeping that information around.
Linked lists are only 1 interesting data structure.
And again, we will use these before long for a problem set.
Another canonical example is this 1 here, a stack.
And the cheesy example most any instructor gives
when discussing stacks is that it takes some photographs
of some phrase like this and cafeteria and much
like you experience as a human, when you put a tray on top.
When the folks running the dining hall put trays on top
on top on top of one another,
the last 1 in is the first 1 out.
In other, words, the top tray is the first one you,
the customer actually take off.
So a stack is another data structure
that is what's called a LIFO data structure.
Last in, first out.
Now this actually has some applications that you'll cover
in courses like CS121 or even, if you've ever written HTML,
made web pages, you know there's a structure to them.
There's a hierarchy where literally,
if you indent things properly, even though it's not required,
it gets in deeper and deeper and deeper and deeper.
You can actually parse, you can actually analyze a webpage
for correctness and for other purposes, using a stack
and the idea, just as an aside is that each tag you read,
you push onto the stack, push onto the stack,
push onto the stack, so you have the most recent tag latest
and then you can check your indentation and all
of your symmetry is right by going backwards.
But there's more useful purposes than just that.
But this is a LIFO data structure,
but all a stack is some chunk of memory
that you can put something here, then something here.
Here, here, here, here.
But this is just a general data type, an abstract data type.
How could you implement this idea of a stack?
Using what C primitives or basics?
>>[inaudible audience question]
>>Sorry?
>>[inaudible audience question]
>>So we have a couple of data structures that are disposable.
What is the simplest way to dispose of this idea
of a data structure that looks like you put something on top
of something on top of something.
We've done this, right?
We just always drew the picture like this.
Something, then something
and then something and then something.
Right, it's just an array,
just flipped conceptually upside down.
But there are some constraints.
And here's the distinction array is really not an abstract data
type, it's not a proper data structure
in that you can go anywhere you want.
So in that sense, there's no- it's much simpler
than the things we're now discussing.
Whereas a linked list, you can't go to a random element.
You have to start at the beginning, search through it
and that now has a more interesting cost
but with stacks, what is the only element in a stack,
at least in reality, that you can access in a given time?
The top tray, right?
If you assumed 1 stack of trays here,
the only one realistically you're going
to get is the top tray.
Going anywhere in the middle
or bottom is just not physically feasible, generally,
so the operations that a stack typically supports is something
called push and something called pop.
And these functions would just be implemented,
whether they're using an array or even a linked list to add
or remove elements from this stack.
But there's another one.
So this is a silly picture of some crazy people lined
up for the iPhone 3G in New York.
So this is a queue.
This is a line, this happens all day long
but there is dare I say even more common data structure.
In computer science or in programming in general,
because this data structure is a FIFO structure.
First in, first out.
That is, if you get there first at the front of the line,
you're the first one to buy the iPhone.
And this has fundamentally different applications, right?
Queues, or queues in this real world sense are a much better
solution to the problem of fairness than a stack.
Imagine if you were 1 of those crazy people who wanted
to get an iPhone that first day and Apple,
because they're a computer-minded people,
decided to implement this thing as a stack.
Right? You'd be ticked off, right?
Right now, that's something
that a computer scientist might actually do.
But anyone with a queue similarly has insert operations
and remove operations.
But fundamentally those operations manipulate different
pieces of data.
So anytime fairness is important, queues are used.
So in fact, you might generally note
that the internet has routers.
Devices that take data from point A to point B
and they send them every which way.
Well, routers have RAM they have memory,
they have hard disks often.
So when they get overwhelmed by traffic spikes,
a lot of people downloading something in a given time,
the routers can't handle everyone's traffic all at once,
so traffic starts to back up.
So thankfully routers and many other devices have queues,
chunks of memory, whereby a packet comes in
and then it queues up, a whole bunch of packets come in
and when the router finally has a moment to deal with your data,
or your download, does it finally move you
through the line.
But here, too, there are interesting opportunities.
You might note that some people
like to prioritize on the internet.
Or would like to prioritize data like voice traffic.
Or they'd like to deprioritze downloads of illegal movies.
And the ways you can do this is
by using different data structures at the router level
to prioritize different data.
Queues is a pretty fair thing, but if you want some other type
of traffic to go through that router first,
a queues is not necessarily the right data structure to deploy.
So those are just teases of some of the data structures to come.
What I thought we'd do is end on this note.
Very common in this point
in the semester are bugs in your own code.
We mentioned several weeks ago, that 1 of the first bugs,
or one 1 of the most defining bugs
in our history is this one here.
When the great Grace Hopper or one of her colleagues pulled
out what was literally a bug from the Mark 2 computer
and then was entered into the notebook here
and they had a good laugh, ha-ha,
computer actually has bug.
Well, there's been some stupid bugs.
And we are at the stack, by no means guilt-free of this.
We make mistakes, you make mistakes
and so what I did was troll around for some inspiring,
reassuring, if not humorous errors.
This one you might have seen.
How many of you have ever seen this on your own piece of tape.
So this is called the "Blue Screen of Death."
Not a terribly helpful message, but frankly at this point
in the course a fatal exception 0 E. I have no idea what
that means, but hexadecimal.
I can now understand a little bit more of this thing.
Has occurred at 0 0 28 cog pull in some other stuff.
VXD, that happens to represent virtual device driver.
You wouldn't know that other than by Googling.
But this was Microsoft's early on form
of a really bad error message that you know what?
Is actually useful, just not to most of us in this room.
In fact really none of us, to Microsoft's engineers,
on the rare occasion you might be able
to tell them what number you're experiencing, this is some kind
of error code indicating a problem in this driver.
Well, this one, too.
Similarly arcane, but perhaps is a little more accessible.
I have no idea what the problem was
in this program, explorer dot exe.
But the instruction at OX77FF.
So that's an int.
That's an address in memory, referenced memory
at some other address.
The memory, and this is the funny part, I think.
The memory cannot be read, just want to emphasize that.
But this was just a bug in the program and frankly,
it sounds like it was some stupid pointer mistake.
So if you ever do see this message,
that's really what they're hinting at.
This is just a bug in many ways.
So this is a legitimate error
that someone took a screenshot of.
Now things devolve into less compelling ones.
This is cute.
[ Laughter ]
>>This one, you have to think about it, that is true.
So that is many years old and quite popular.
This is just a problem.
This is within a browser using JavaScript,
bad things can happen in even just the confines here.
So this is just weird.
This is what happens when you start using Google images
too much.
So this is a tattoo of a blue screen
of death on this fellow's arm.
He's still red from it, I don't know why.
I'm a little uncomfortable with it,
but we'll leave the slides online.
So this, too, is bad, And I actually thought
of this the other day.
Fidelity Investment bank on the corner of some street,
maybe in New York, so that's a scrolling blue screen
of death, essentially.
An error has occurred and Windows has been shut down,
or something to that effect.
And I wish I'd had the foresight to pull
out my camera at the time.
I was just going through the subway the other day
in Harvard Square and the swipe machines that they have
to the entrance to the T, I was very sad to realize
that whoever designed them, they used Windows
to run these things, because the little thing that normally says,
"Enter Here," said this.
So that was amusing, if you can catch a photo of that, do.
So to be fair, this one was actually fun.
So this was an advertisement for Windows Vista.
The machine, funny enough, was behind glass.
Macs are not infallible.
This is the Mac version of this.
They simplified it, it's a little less scary
than the blue cryptic message.
Apple, in fact, doesn't tell you there's a problem, just,
"You need to restart your computer,"
cutting corners there.
So there's 2, if you start Googling.
There's the sad Mac users get.
I will not follow the link on the page I found this.
And some people have done some sketchy things
to their bodies using error messages from computers.
I'll link it on the website.
This is from Scent OS, a version of Linux.
So this, too, happens sometimes.
Please insert negative disk 099 to continue.
But perhaps the best 1 of all time, no- second to best.
This 1 I snapped myself.
I was ordering pizza late at night, being a geek,
I thought a printout error was cool.
So I was offered this upsell to buy some chicken in addition
to my pizza, do you see the mistake?
This is a print-def fail.
They didn't use the right width for the floating points value.
So this is $6.30, but they haven't padded it properly
to half that 0.
And this 1 is perhaps the most famous 1.
So some engineer somewhere, years ago,
maybe at HP to the light decided
that paper cassette would load a letter,
or a PC load letter would be sufficient information
for millions of people over 10 years to understand
when it's time to load the paper into the machine.
We are perhaps not the only ones who find this aggravating.
I thought we'd end on this infamous note.
Slightly R-rated, but we'll end with this.
We'll end with this final moment, a wonderful movie,
if you've never seen it called, Office Space.
>>What would I do if I had million dollars?
I would invest half of it in low-risk mutual funds,
and then take the other half to my friend [inaudible]
who works in securities.
>>Samir, you're missing the point.
Point of the exercise is to figure
out what you'd want to do with it.
PC load letter, what the fuck does that mean?
[ Crash ]
[ Music ]