- [Instructor] A Linked List is a list of structs or classes
that include a pointer.
This pointer points to the next struct or class in its list,
as it gets added.
Normally we call these pointers Next
to give them a descriptive name,
as to what they're pointing to,
but they can be anything.
Unlike an array,
where you have to statically set
the number of elements you need,
a linked list is a great alternative,
because you can link them dynamically,
allowing your list to grow or shrink as needed.
To create a linked list,
we first need to create a struct or a class.
I'm going to use a struct.
I've defined my struct as Node.
In my node, I have a data point and I also have a pointer,
a pointer to another node.
This line: Node asterisk Link,
is a pointer to a node.
The line after that: Typedef Node asterisk,
is redefining what node pointer looks like.
So instead of having to require an asterisk,
anytime I use a pointer,
I can now just declare them as: type node pointers.
It's the same thing.
You can use Typedef anywhere you need,
but it's highly recommended to only use them when needed.
So in my main, I have nodePtr head.
This creates a new node pointer called Head.
Right now it's not pointing to anything,
but we'll get to that in a minute.
The next line says, "Head equals new node."
Now I'm going to point to a brand new node.
And remember, every time I create a node,
I get the same data points
that are defined in the struct node,
so I have an int data section, which I've defined in blue.
And then I have a node pointer.
Right now again, it's not pointing to anything.
The next two lines populate my new node with data.
We're also introducing the arrow operator.
This is used when you're using pointers
in reference to populating data.
So here I have my pointer head pointing to a new node,
and now I wanna put 20 in the data spot.
I'm also pointing the link portion to NULL.
Next line is just for data debugging.
If I try to print out the data that my head is pointing to,
it should give me a 20.
So all I need to say is, Head arrow Data,
and that will get the data
that the head pointer is pointing to.
But what if we have more data?
What if we want to insert a whole bunch of data
into our list?
Here I've written an insert function.
It requires a pointer, passed by reference.
Remember pass by reference, versus pass by value,
and a data point.
And it'll take that data point and populate a new node.
So the first line in my function
declares a new node pointer called, Temp Pointer.
I've named it T-E-M-P P-T-R for short.
All that is create a new pointer.
Currently it's not pointing to anything.
The next line creates a new node
and makes the tempPtr point to this new node.
So now I have a brand new node.
Anytime I declare a node, I get the same two pieces of data,
an integer for the data type,
and then a link for the next node.
I populate my data.
I put 30 from my parameter list into the data portion,
and then the next line says, tempPtr link.
Now I'm linking the next node to head.
Remember our head was pointing to a node with 20 in it.
Now I have two pointers pointing to the node with 20,
the last line redirects head to the front of my list.
Head should always be the front of your list.
It makes it easier to find the start of your list
if it's an empty list,
or where to start searching and sorting from.
So now my head is pointed back around
at the same place my tempPtrs pointing to,
which is the node that has 30.
As soon as I returned back from my function,
tempPtr will be deleted,
because remember it was only created in that function.
So now my list only contains a head pointer
pointing to the node with the 30.
The node with the 30 pointing to the next node with the 20,
and the node with the 20 pointing to NULL.
We could keep inserting, but let's print out our list.
When I return back from my function,
the next line creates a new temporary pointer
currently not pointing to anything,
then I set it to point to the same place as head.
Head should be at the front of my list,
and now I say, while temp, or that pointer,
is not equal to NULL.
So while I'm not at the end of my list,
I want to see out the data in the node that I'm pointing to
and then move to the next node.
So after it gums from head, points to 30,
it'll print 30,
and then this line will move the tempPtr
to the next node in the list.
The next move will end up being NULL
because the node with 20 and it's link does point to NULL.
So if I moved one more time,
I would be looking at NULL
and I would come out of my loop.
But by then I should have printed 20 and 30 on my console.
Let's take a look.
Here I have copied everything down,
just the way we had it.
If I run it, it prints 30 and finally 20,
so it works!
Although a linked list with only two pieces of data
is not very useful,
but you can see how you can insert and delete nodes
as you need them.
(uptempo music)