[MUSIC PLAYING]
DOUG LLOYD: OK, so at this point in the course,
we've covered a lot of the basics of C. We know a lot about variables, arrays,
pointers, all that good stuff.
Those are all sort of built in to see as the fundamentals,
but we can do more, right?
We can combine things together in interesting ways.
And so let's do that, let's start to branch out of what C gives us,
and start to create our own data structures using these building
blocks together to do something really valuable, useful.
One way we can do this is to talk about collections.
So so far we've had one kind of data structure for representing collections
of like values, similar values.
That would be an array.
We have collections of integers, or collections of characters and so on.
Structures are also sort of a data structure for collecting information,
but it's not for collecting like values.
It usually mixes different data types together inside of a single box.
But it's not itself used to chain together
or connect together similar items, like an array.
Arrays are great for element look up, but recall
that it's very difficult to insert into an array,
unless we're inserting at the very end of that array.
And the best example I have for that is insertion sort.
If you recall our video on insertion sort,
there was a lot of expense involved in having
to pick up elements, and shift them out of the way to fit something
into the middle of your array.
Arrays also suffer from another problem, which is inflexibility.
When we declare an array, we get one shot at it.
We get to say, I want this many elements.
Might be 100, it might be 1,000, it might
be x where x is a number that the user gave us at a prompt or at the command
line.
But we only get one shot at it, we don't get to then say oh, actually I
needed 101, or I needed x plus 20.
Too late, we've already declared the array, and if we want to get 101 or x
plus 20, we have to declare an entirely different array,
copy all the elements of the array over, and then we have enough.
And what if we are wrong again, what if we actually need 102, or x plus 40,
we have to do this again.
So they're very inflexible for resizing our data,
but if we combine together some of the basics that we've already
learned about pointers and structures, in particular using dynamic memory
allocation with malloc, we can put these pieces together
to create a new data structure-- a singly linked list we might say--
that allows us to grow and shrink a collection of values
and we won't have any wasted space.
So again, we call this idea, this notion, a linked list.
In particular, in this video we're talking about singly linked list,
and then another video we'll talk about doubly linked lists, which
is just a variation on a theme here.
But a singly linked list is comprised of nodes,
nodes just being an abstract term-- it's just something I'm calling
that's a kind of structure, basically, I'm?
Just going to call it a node-- and this node has two members, or two fields.
It has data, usually an integer, a character float,
or could be some other data type that you've defined with a type def.
And it contains a pointer to another node of the same type.
So we have two things inside of this node, data and a pointer
to another node.
And if you start to visualize this, you can think about it
like a chain of nodes that are connected together.
We have the first node, it contains data, and a pointer
to the second node, which contains data, and a pointer to the third node.
And so that's why we call it a linked list, they're linked together.
What does this special node structure look like?
Well, if you recall from our video on defining custom types, with type def,
we can define a structure-- and type define a structure like this.
tyepdef struct sllist, and then I'm using the word value here arbitrarily
to indicate any data type really.
You could pass on an integer or float, you could have whatever you want.
It's not restricted to just integers, or anything like that.
So value is just an arbitrary data type, and then a pointer
to another node of the same type.
Now, there's a little catch here with defining a structure
when it's a self referential structure.
I have to have a temporary name for my structure.
At the end of the day I clearly want to call it
sll node, that's ultimately the new name part of my type definition,
but I can't use sll node in the middle of this.
The reason being, I haven't created a type called sll node
until I hit this final point here.
Up until that point, I have to have another way to refer to this data type.
And this is a self referential data type.
It;s a data type of a structure that contains a data,
and a pointer to another structure of the same type.
So I need to be able to refer to this data type at least temporarily,
so giving it a temporary name of struct sllist
allows me to then say I want a pointer to another struct sllist,
a struct sllist star, and then after I've completed the definition,
I can now call this type an sll node.
So that's why you see there's a temporary name here,
but a permanent name here.
Sometimes you might see definitions of structure,
for example, that aren't self referential, that
don't have a specifier name here.
It would just say typedef struct, open curly brace and then define it.
But if you're struct is self referential, as this one is,
you need to specify a temporary type name.
But ultimately, now that we've done this,
we can just refer to these nodes, these units,
as sll nodes for purposes of the rest of this video.
All right, so we know how to create a linked list node.
We know how to define a linked list node.
Now, if we're going to start using them to collect information,
there's a couple of operations we need to understand and work with.
We need to know how to create a linked list out of thin air.
If there's no list already, we want to start one.
So we need to be able to create a linked list,
we need to probably search through the link list
to find an element we're looking for.
We need to be able to insert new things into the list,
we want our list to be able to grow.
And similarly, we want to be able to delete things from our list,
we want our list to be able to shrink.
And at the end of our programs, especially
if you recall that we're dynamically allocating memory
to build these lists typically, we want to free all of that memory
when we're done working with it.
And so we need to be able to delete an entire linked list in one fail swoop.
So let's go through some of these operations
and how we might visualize them, talking in pseudocode code specifically.
So we want to create a linked list, so maybe we
want to define a function with this prototype.
sll node star, create, and I'm passing in one argument, some arbitrary data
type again, of some arbitrary data type.
But I'm returning-- this function should return to me a pointer, to a singly
linked list node.
Again, we're trying to create a linked list out of thin air,
so I need a pointer to that list when I'm done.
So what are the steps involved here?
Well, first thing I'm going to do is dynamically
allocate space for a new node.
Again, we're creating it out of thin air, so we need to malloc space for it.
And of course, immediately after we malloc,
we always check to make sure that our pointer-- we did not get back null.
Because if we try and deference a null pointer,
we're going to suffer a segfault and we don't want that.
Then we want to fill in the field, we want to initialize the value field
and initialize the next field.
And then we want to-- eventually as the function prototype indicates-- we want
to return a pointer to an sll node.
So what make this look like visually?
Well, first we're going to dynamically allocate space for a new sll node,
so we malloc-- that's a visual representation
of the node we just created.
And we check to make sure it's not null-- in this case,
the picture wouldn't have shown up if it was null,
we would have run out of memory, so we're good to go there.
So now we're on to step C, initialize the nodes value field.
Well, based on this function call I'm using here,
looks like I want to pass in 6, so I'll 6 in the value field.
Now, initialize the next field.
Well, what am I going to do there, there is nothing next, right,
this is the only thing in the list.
So what's the next thing in the list?
It shouldn't point to anything, right.
There's nothing else there, so what is the concept we know of that's nothing--
pointers to nothing?
It should be maybe we want to put a null pointer there,
and I'll represent the null pointer as just a red box,
we can't go any further.
As we'll see a little later on, we will have eventually chains
of arrows connecting these nodes together,
but when you hit the red box, that's null,
we can't go any further, that's the end of the list.
And lastly, we just want to return a pointer to this node.
So we'll call it new, and will return new
so it can be used in whatever function created it.
So there we go, We've created a singly linked list node out of thin air,
and now we have a list we can work with.
Now, let's say we already have a large chain,
and we want to find something in it.
And we want a function that's going to return true or false, depending
on whether a value exists in that list.
A function prototype, or declaration for that function,
might look like this-- bool find, and then we want to pass in two arguments.
The first, is a pointer to the first element of the linked list.
This is actually something you'll always want to keep track of,
and actually might be something that you even put in a global variable.
Once you create a list, you always, always
want to keep track of the very first element of the list.
That way you can refer to all the other elements by just following the chain,
without having to keep pointers intact to every single element.
You only need to keep track of the first one if they're all chained together.
And then the second thing we're passing in again
is arbitrarily some-- whatever data type we're
looking for there is inside of hopefully one of the nodes in the list.
So what are the steps?
Well, the first thing we do is we create a transversal pointer
pointing to the lists head.
Well, why do we do that, we already have a pointer at the lists head,
why don't we just move that one around?
Well, like I just said, it's really important for us
to always keep track of the very first element in the list.
And so it's actually better to create a duplicate of that,
and use that to move around so we never accidentally move away, or we always
have a pointer at some point that is right on the first element of the list.
So it's better to create a second one that we use to move.
Then we just compare whether the value field at that node
is what we're looking for, and if it's not, we just move to the next node.
And we keep doing that over, and over, and over,
until we either find the element, or we hit
null-- we've reached the end of the list and it isn't there.
This should hopefully ring a bell to you as just linear search,
we're just replicating it in a singly linked list structure
instead of using an array to do it.
So here's an example of a singly linked list.
This one consists of five nodes, and we have
a pointer to the head of the list, which is called list.
The first thing we want to do is again, create that traversal pointer.
So we have now two pointers that point to the same thing.
Now, notice here also, I didn't have to malloc any space for trav.
I didn't say trav equals malloc something, that node already exists,
that space in memory already exists.
So all I'm actually doing is creating another pointer to it.
I'm not mallocing an additional space, just have now two pointers
pointing to the same thing.
So is 2 what I'm looking for?
Well, no, so instead I'm going to move to the next one.
So basically I would say, trav equals trav next.
Is 3 what I'm looking for, no.
So I continue to go through, until eventually
get to 6 which is what I'm looking for based on the function call
I have at the top there, and so I'm done.
Now, what if the element I'm looking for isn't in the list,
is it still going to work?
Well, notice that the list here is subtly different,
and this is another thing that's important with linked lists,
you don't have to preserve them in any particular order.
You can if you want, but you may have already noticed
that we're not keeping track of what number element we are at.
And that's sort of one trade that we have with linked list verses arrays,
is it we don't have random access anymore.
We can't just say, I want to go to the 0th element,
or the 6th element of my array, which I can do in an array.
I can't say I want to go to the 0th element, or the 6th element,
or the 25th element of my linked list, there's no index associated with them.
And so it doesn't really matter if we preserve our list in order.
If you want to you certainly can, but there's
no reason why they need to be preserved in any order.
So again, let's try and find 6 in this list.
Well, we start at the beginning, we don't find 6,
and then we continue not finding 6, until we eventually get to here.
So right now trav points to the node containing 8, and six is not in there.
So the next step would be to go to the next pointer,
so say trav equals trav next.
Well, trav next, indicated by the red box there, is null.
So there's nowhere else to go, and so at this point
we can conclude that we've reached the end of the linked list,
and 6 isn't in there.
And it would be returned false in this case.
OK, how do we insert a new node into the linked list?
So we've been able to create a linked list out of nowhere,
but we probably want to build a chain and not
create a bunch of distinct lists.
We want to have one list that has a bunch of nodes in it,
not a bunch of lists with a single node.
So we can't just keep using the Create function we defined earlier, now we
want to insert into a list that already exists.
So this case, we're going to pass in two arguments,
the pointer to the head of that linked list that we want to add to.
Again, that's why it's so important that we always
keep track of it, because it's the only way we really
have to refer to the whole list is just by a pointer to the first element.
So we want to pass in a pointer to that first element,
and whatever value we want to add to the list.
And eventually this function is going to return a pointer
to the new head of a linked list.
What are the steps involved here?
Well, just like with create, we need to dynamically allocate
space for a new node, and check to make sure we don't run out of memory, again,
because we're using malloc.
Then we want to populate and insert the node,
so put the number, whatever val is, into the node.
We want to insert the node at the beginning of the linked list.
There's a reason that I want to do this, and it
might be worth taking a second to pause the video here,
and think about why I would want to insert at the beginning of a linked
list.
Again, I mentioned earlier that it doesn't really
matter if we preserve it in any order, so maybe that's a clue.
And you saw what would happen if we wanted to-- or from just a second
ago when we were going through search you
could see what might happen if we were trying
to insert at the end of the list.
Because we don't have a pointer to the end of the list.
So the reason that I would want to insert at the beginning,
is because I can do it immediately.
I have a pointer at the beginning, and we'll see this in a visual in a second.
But if I want to insert at the end, I have to start at the beginning,
traverse all the way to the end, and then tack it on.
So that would mean that inserting at the end of the list
would become an o of n operation, going back
to our discussion of computational complexity.
It'd become an o of n operation, where as the list got bigger, and bigger,
and bigger, it'll become more and more difficult to tack something
on at the end.
But it's always really easy to tack something on at the beginning,
you're always at the beginning.
And we'll see a visual of this again.
And then once we're done, once we've inserted the new node,
we want to return our pointer to the new head of a linked list, which
since we're inserting at the beginning, will actually be
a pointer to the node we just created.
Let's visualize this, because I think it'll help.
So here's our list, it consists of four elements, a node containing 15,
which points to a node containing 9, which
points to a node containing 13, which points to a node containing
10, which has the null pointer as its next pointer
so that's the end of the list.
So we want to insert a new node with the value 12
at the beginning of this list, what do we do?
Well, first we malloc space for the node, and then we put 12 in there.
So now we've reached a decision point, right?
We have a couple of pointers that we could
move, which one should we move first?
Should we make 12 point to the new head of the list--
or excuse me, should we make 12 point to the old head of the list?
Or should we say that the list now begins at 12.
There's a distinction there, and we'll look
at what happens with both in a second.
But this leads to a great topic for sidebar,
which is that one of the trickiest things with linked lists
is to arrange the pointers in the correct order.
If you move things out of order, you can end up accidentally
orphaning the rest of the list.
And here's an example of that.
So let's go with the idea of-- well, we've just created 12.
We know 12 is going to be the new head of the list,
and so why don't we just move the list pointer to point there.
OK, so that's good.
So now where does 12 next point?
I mean, visually we can see that it will point to 15,
as humans it's really obvious to us.
How does the computer know?
We don't have anything pointing to 15 anymore, right?
We've lost any ability to refer to 15.
We can't say new arrow next equals something, there's nothing there.
In fact, we've orphaned the rest of the list
by doing so, we've accidentally broken the chain.
And we certainly don't want to do that.
So let's go back and try this again.
Maybe the right thing to do is to set 12's next pointer
to the old head of the list first, then we can move the list over.
And in fact, that is the correct order that we
need to follow when we're working with singly linked list.
We always want to connect the new element into the list,
before we take that kind of important step of changing
where the head of the linked list is.
Again, that's such a fundamental thing, we don't want to lose track of it.
So we want to make sure that everything is chained together,
before we move that pointer.
And so this would be the correct order, which is to connect 12 to the list,
then say that the list starts a 12.
If we said the list starts at 12 and then tried to connect 12 to the list,
we've already seen what happens.
We lose the list by mistake.
OK, so one more thing to talk about.
What if we want to get rid of an entire linked list at once?
Again, we're mallocing all this space, and so we
need to free it when we're done.
So now we want to delete the entire linked list.
Well, what do we want to do?
If we've reached the null pointer, we want to stop, otherwise, just delete
the rest of the list and then free me.
Delete the rest of the list, and then free the current node.
What does that sound like, what technique have we talked
about previously does that sound like?
Delete everybody else, then come back and delete me.
That's recursion, we've made the problem a little bit smaller,
we're saying delete everybody else, then you can delete me.
And further down the road, that node will say, delete everybody else.
But eventually we'll get to the point where the list is null,
and that's our base case.
So let's take a look at this, and how this might work.
So here's our list, it's the same list we were just talking about,
and there's the steps.
There's a lot of text here, but hopefully the visualization will help.
So we have-- and I also pulled up our stack frames illustration
from our video on call stacks, and hopefully all of this
together will show you what's going on.
So here's our pseudocode code.
If we reach a null pointer, stop, otherwise,
delete the rest of the list, then free the current node.
So right now, list-- the pointer that we're
passing in to destroy points to 12.
12 is not a null pointer, so we're going to delete the rest of the list.
What is deleting the rest of us involved?
Well, it means making a call to destroy, saying
that 15 is the beginning of the rest of the list we want to destroy.
And so the call to destroy 12 is kind of on hold.
It's frozen there, waiting for the call to destroy 15, to finish its job.
Well, 15 is not a null pointer, and so it's going to say, all right,
well, delete the rest of the list.
The rest of the list starts at 9, and so we'll just
wait until you delete all that stuff, then come back and delete me.
Well 9's going to say, well, I'm not a null pointer,
so delete the rest the list from here.
And so try and destroy 13.
13 says, I'm not null pointer, same thing, it passes the buck.
10 is not null pointer, 10 contains a null pointer,
but 10 is not itself a null pointer right now,
and so it passes the buck too.
And now list points there, it really would point to some--
if I had more space in the image, it would point to some random space
that we don't know what it is.
It's the null pointer though, the list is literally now set it's values null.
It's pointing right inside that red box.
We reached a null pointer, so we can stop, and we're done.
And so that purple frame is now-- at the top of stack-- that's the active frame,
but it's done.
If we've reached a null pointer, stop.
We don't do anything, we can't free a null pointer,
we didn't malloc any space, and so we're done.
So that function frame is destroyed, and we
resume-- we pick up where we left off with the next highest one, which
is this dark blue frame here.
So we pick up right where we left off.
We deleted the rest of the list already, so now we're
going to free the current nodes.
So now we can free this node, and now we've reached the end of the function.
And so that function frame is destroyed, and we pick up at the light blue one.
So it says-- I've already done-- deleting the rest of the list, so
free the current node.
And now the yellow frame is back on top of the stack.
And so as you see, we're now destroying the list from right to left.
What would have happened, though, if we had done things the wrong way?
Just like when we tried to add an element.
If we messed up the chain, if we didn't connect the pointers
in the correct order, if we just freed the first element,
if we just freed the head of the list, now we
have no way to refer to the rest of the list.
And so we would have orphaned everything,
we would have had what's called a memory leak.
If you recall from our video on dynamic memory allocation,
that's not very good thing.
So as I said, there are several operations
that we need to use to work with linked list effectively.
And you may have noticed I omitted one, deleting a single element from a linked
list.
The reason I did that is it's actually kind of
tricky to think about how to delete a single element from a singly
linked list.
We need to be able to skip over something in the list, which
means we get to a point-- we want to delete this node--
but in order to make it so we don't lose any information,
we need to connect this node over here, here.
So I probably did that wrong from a visual perspective.
So we're at the beginning of our list, we're proceeding through,
we want to delete this node.
If we just delete it, we've broken the chain.
This node right here refers to everything else,
it contains the chain from here on out.
So what we need to do actually after we get to this point,
is we need to step back one, and connect this node over to this node,
so we can then delete the one in the middle.
But singly linked lists don't provide us a way to go backwards.
So we need to either keep two pointers, and move them
sort of off step, one behind the other as we go, or get to a point
and then send another pointer through.
And as you can see, it can get a little messy.
Fortunately, we have another way to resolve that,
when we talk about doubly linked lists.
I'm Doug Lloyd, this is CS50.