In our previous lesson, we saw how we can
map the logical view of a linked list into a C or C++ program. We saw how
we can implement two basic operations: one traversal of the linked list and
another inserting a Node at the end of the linked list. In this lesson we
will see a running code that will insert a Node
at the beginning of the linked list. So let's get started. I will write a 'C'
program here. the first thing that we want to do in
our program is that we want to define a Node. A Node
will be a structure in C. It will have two fields: One to store the data, let's say we
want to create a linked list of Integers, so our data type will be integer. If we
wanted to create a linked list of characters, then
our type would be character here. So we will have
another field that will be pointer to Node, that will
store the address of the next Node. We can name this variable link or
some... some people also like to name this
variable next because it sounds more intuitive. This variable will store the
address of the next Node in the linked list. In C, whenever we have to declare Node or pointer to Node, we will have
to write struct Node or struct Node* (star). In C++, we will have to write
only Node*, and that's one difference. Okay, so this
is the definition of a Node. Now to create a linked list
we will have to create a variable that will be pointer to Node
and that will store the address of the first Node in the
linked list, what we also call the head Node. so I will create a pointer to Node here.
struct Node*, we can name this variable
whatever. Often for the sake of understanding, we name this variable head. Now I have declared this variable as a
global variable. I have not declared this variable inside
any function and I'll come back to why I am doing so. And now I'll write the main method. This
is the entry point to my program. The first thing that I want to do is I
want to see if head is equal to null which will mean
that this pointer variable points nowhere. So right now the list is empty. So far
what we have done here in our code, is that we have created a global
variable named head which is of type pointer to Node and the value in
this pointer variable is null, so So far the list is empty. Now, what I want to do
in my program is that I want to ask the user to input some numbers and I want to
insert all these numbers into the linked list. so I'll print
something like how many numbers? Let's say the user
wants to input n number so I'll collect this number in this variable 'n' and then I'll
define another variable 'i' to run the loop and so I'm running a loop here. If it was C++
I could declare this integer variable right here inside the loop. Now i'll write a print statement like this, and I'll define another variable 'x' and
each time I'll take this variable 'x' as input from
the user and now I will insert this particular
number 'x', this particular integer 'x' into the
linked list, by making a call to the method 'insert' and
then each time we insert, we will print all the Nodes in the linked list, the
value of all the Nodes in the linked list by calling a function named print. There
will be no argument to this function print. Of course we need
to implement these two functions insert and print. Let me first
write down the definition of these two functions. So let us implement these two functions:
insert and print. Let's first implement the
function insert that will insert a Node at the beginning
of the linked list. Now in the insert function what we
need to do is we first need to create a Node. In C we
can create a Node using malloc() function. We have
talked about this earlier. malloc() returns a pointer to the starting
address of the memory block we are having to
type cast here because malloc returns a void pointer and we need a pointer to
Node, a variable that is pointer to Node and
then only if we dereference we derefernce using an Astrix(*) sign
then we will be able to access the fields of the Node, so that the data part will be 'x' and we
have an alternate syntax for this particular syntax. We could simply
write something like temp and this arrow and it will mean the same thing and
this is more common. With these two lines in the insert
function, all we're doing is, we're creating a
Node. Let's say we get this Node and let's assume that the address that we get for this Node is 100.
Now there is a variable temp where we are storing the
address. We can do one thing whenever we
create a Node, we can set data to whatever we want to set and we can set
the link field initially to null and if needed we can
modify the link field. So I'll write one more statement temp->
next is equal to null. Remember temp is a pointer variable here
and we are dereferencing the pointer variable to modify the value at this
particular Node. temp will also take some space in the
memory that's why I have shown this rectangular block for both the pointer
variables head and temp. and Node has two parts: one for the
pointer variable and one for the data. So this part, the link part is null, we can
either write null here or we can write it like this. It's the same
thing. Logically it means the same. Now if we want to insert this Node in
the beginning of the list, there can be two scenarios: one when
the list is empty, like in this case. So the only thing that
we need to do is, we need to point head to this particular Node, instead of pointing to null. So I will
write a statement like head is equal to temp and the value in head now will be
address 100. And that's what we mean when we say a
pointer variable points to a particular Node. We store the address of
that Node. So this is our linked lis, after we insert
the first Node. Let us now see what we can do to
insert a Node at the beginning if the list is not
empty like what we have right now. Once again we can create a Node, fill in
the value 'x' here that is passed as argument.
Initially, we may set the link field as null,
and let's say this Node gets address 150 in the memory and
we have this variable temp through which we are referencing this particular memory
block. Now unlike the previous case, if we just
set head = temp, this is not
good enough because we also need to build this link. We need to
set the next or the link of the newly created Node
to whatever the previous head was. So what we can do is, we can write
something like if head is not equal to null or if the list is not empty, first set
temp->next equal head so we first build this link. The address
here will be 100 and then we say head = temp, so we cut this link and point head to this newly created Node, and this is our
modified linked list after insertion of this second Node at the
beginning of the list. Now one final thing here: this
particular line the third line temp->next = null, this is getting
used only when the list is empty. If you see, when the list is empty
head is already null. So we can avoid writing two statements.
We can simply write this one statement, temp->next = head and this will also cover the scenario
when the list is empty. Now the only thing remaining in this
program to get this running, is the implementation of this print
function, so let's implement this print function.
What I will do here is that I'll create a local variable which is pointer to Node,
named temp and I need to write struct Node here.
I keep missing this. In C, you need to write it like
this and I want to set this as address of the head Node so
this global variable has the address of the head Node. Now I want to traverse the linked list.
so I will write a loop like this: while temp is not equal to null, I'll keep going to the next Node using
this statement temp is equal to temp dot next and at each stage I'll print the value in that Node as temp->data. Now I'll write two more print. One outside this while
loop, and one outside after this while loop to
print an end of line. Now why did we use a
temporary variable? Because we do not want to modify head, because we will lose the reference of
the first Node. So first we collect the address in head
in another temporary variable, and we are modifying the addresses in this
temporary variable using temp is equal to temp->next to traverse the list. Let us now run this program and
see what happens. So this is asking how many numbers you
want to insert in the list. Let's say we want to insert 5 numbers.
Initially the list is empty. Let's say the first number that we want
to insert is 2. At each stage, we are printing the list so
the list is now 2. The first element and the last element is 2. We will insert another number. The list
is now 5 2. 5 is inserted at the beginning of the list. Again we insert 8 and 8 is also
inserted at the beginning of the list. Ok... Let's insert number 1. The list
is now 1 8 5 2. And finally I insert the number 10.
so the final list is 10 1 8 5 2. This seems to be working. Now if we were writing this code in C++,
we could have done couple of things. We could have written a class and
organize the code in an object-oriented manner. We
could also have used new operator, in place of the malloc function. Now,
coming back to the fact that we have declared this head as global variable. What if this was
not a global variable, this was declared inside this main function as a local
variable? so I'll remove this global declaration.
Now this head will not be accessible in other
functions, so we need to pass address of the first Node as argument
to other functions: to both these functions, print and
insert. So to this print method, we'll pass, let say we name this
argument as head. We can name this argument...argument as
head or a or temp or whatever. If we name
this argument as head, this head in print will be a local variable of print
and will not be this head in main. And these two heads
will be different, these two variables will be different. When the main function calls print,
passing its head then the value in this
particular head in the main function is copied to this another head in the print
function. So now in the print function, we may not use this temp variable.
What we can do is, we can use this variable head itself to traverse the list and this should be
good. We're not modifying this head here in the main. Similarly to the insert function we will
have to pass the address of the first Node. And this head again is just a copy. This
is again a local variable, so after we modify the linked list, the
head in main method, should also be modified
and there are two ways to do it. One: we can pass the pointer to Node as return from this method. So in the main
method, insert function will take another argument head, and we will have to collect the
return into head again so that it is modified. Now this code will work fine. Oops, I
forgot to write a return here, return head and we can run
this program like before. We can give all the values and see that the list is
building up correctly. There was another way of doing this.
Instead of asking this insert function to return
the address of head, we could have passed this particular
variable head by reference. So we could have passed insert
&head. head is already a pointer to Node, so in the insert function we will have
to receive pointer to pointer. Node** and to avoid confusion
let's name this variable something else. This time, let's name this pointertohead. So to get head, we will have to write
something like we will have to dereference this
particular variable and write *pointertohead every where and
the return type will be void. Sometimes we want to name this
variable as head, this local variable as head. Doesn't
matter, but we'll have to take care of using it properly. Now this code will
also work. As you can see here, we can insert Nodes
and this seems to be going well. If you do not understand this concepts of
scope, you can refer to the description of this video for additional
resources. So this was inserting a Node at the
beginning of the linked list. Thanks for watching!
