In our previous lessons, we described linked list, we saw the cost of various operations in linked list and we also compared Linked List with arrays. Now, let us implement Linked List, the implementation will be pretty similar in c and c++. there will be slight differences that we will discuss. the prerequisite for this lesson is that you should have a working knowledge of pointers in C/C++ and you should also know the concept of dynamic memory allocation. If you want to refresh any of these concepts check the description of this video for additional resources. Ok so let's get started. As we know in a linked list, data is stored in multiple non-contiguous blocks of memory and we call each block of memory a node in the linked list. So Let me first draw a linked list here, so we have a linked list of integers here with three nodes as we know each node has two fields or two parts one to store the data and another to store the address of the next node what we can also call link to the next node. So Let's say the address of the first node is 200 and address of the second node is 100 and the address of the third node is 300 for this linked list. This is only a logical view of the linked list.So the address part of the first node will be 100 and the address of the second node will be 200 and we will have 300 here. The address part of the last node will be null which is only a synonym or macro for address 0. 0 is an invalid address a pointer variable equal to 0 or null with address 0 or null means that the pointer variable does not point to a valid memory location. The memory block the address of the memory block allocated to each of the node is totally random, there is no relation. Its not a guarantee that the addresses will be in increasing order or decreasing order or adjacent to each other. So that's why we need to keep these links.Now the identity of the linked list that we always keep with us is the address of the first node what we also call the head node. So we keep another variable that will be of type pointer to node and this guy will store the address of the first node. And we can name this pointer variable whatever lets say this pointer variable is named A. The name of this particular pointer variable that points to the head node or the first node can also be interpreted as the name for the linked list also because this is the only identity of the linked list that we keep with us all the time. So let us now see how this logical view can be mapped to a real program in C or C++. In our program node will be a data type that will have two fields.one to store the data and another to store the address. In C we can define such a datatype as structure, so lets say we define a structure named node with two fields. First field to store the data, the type of the data here is integer so this will be node for a linked list of integers. If we wanted a Linked List of say Double, this data type would be double. The second field will be pointer to node struct node*. We can name this Link or we can name this next or whatever This is C style of declaring node* or pointer to node.If this was C++ we could simply write Node*. I would write it this way the C++ way it looks better to me. In our Logical view here this variable A is of type Node* or pointer to node. Each of these three rectangles with two fields are of type node and this field in the node, the first field is of type integer and second field is of type pointer to node or Node*. It is important to note which one is what in the logical view. We should have this visualization before we go on to implement Linked List. OK so Let us now create this particular Linked List of Integer that we are showing here through our code.To be able to do so we will have to implement two operations one to insert a node into the Linked List. One operation to insert a node in to Linked List and another operation to traverse the Linked List. But before that the first thing that we want to do is that we want to declare a pointer to the head node, a variable that will store the address of the head node. For the sake of clarity i will write head node here.So I have declared a pointer to node named A. Initially When the list is empty, when there is no element in the list. This pointer should point no where. So we write a statement something like A is equal to Null to say this same.With these two statements what we have done is we have created a pointer to node named A and this pointer points No-where so the list is empty. Now Lets say we want to insert a node in this list so what we do is we first create a node.Creating a node is nothing but creating a memory block to store a node. In C we use the function malloc to create a memory block as argument we pass the number of bytes that we want in the block. So we say that give me a memory block that will be equal to the size of a node. So this call to malloc will create a memory block.This is dynamically allocated memory,memory allocated during runtime and the only way to work with this kind of memory is through reference to this memory location through pointers. Let us assume that this memory block assigned here is at address 200. Now malloc returns a void pointer that gives us the address of assigned memory block so we need to collect it in some variable. Lets say we create a variable named temp which is pointer to node so we can collect the return of malloc the address in this particular variable. We will need a type casting here because malloc returns void pointer and we are having temp as pointer to node So now we have created one node in the memory. Now what we need to do is fill in the data in this particular node and adjust the links which will mean writing the correct address in the variable A and the link field of this newly created node. To do so we will have to de-reference this particular pointer variable that we just created. As we know if we put a * sign in front of the pointer variable.We mean de-referencing it to modify the value at that particular address. Now in this case we have a node which has two fields,so once we de-reference if we want to access each of the fields we need to put something like a dot data here to access the data and a dot link to write to the link field. So we will write a statement like this to fill in value 2 here and we have this temp variable pointing to this right now and link part of this newly created node should be null because this is the first and the last node. And the final thing that we need to do is write the address of this newly created node in A. So we will write something like A is equal to temp. Ok temp was to temporarily store the address of the node till the time we have not fixed all the links properly. We can now use temp for some other purpose.Our linked list is intact now it has one node. These two lines that we have written here for de-referencing and writing the value into the new node.There is alternate syntax for this Instead of writing something like *temp bracketed dot data we could also write temp followed by this arrow and data.we will have two characters to make this arrow one hyphen and one this right angular brace. So we can write something like this.And same thing below we can write something like this.To create a memory block in C++ we can use malloc as well as we can use the new operator. So in C++ it gets very simple.We could simply write Node* temp = new Node like this and we would mean the same thing. this is a lot cleaner and new operator is always preferred over malloc. So if you are using C++ new is recommended. So far through our program we created an empty list by creating this pointer to the head node and assigning the value null to it initially then we created a node and we added first node in this linked list.When the list is empty and we want to insert a node the logic is pretty straight forward. When the list is not empty we may want to insert a node at the beginning of the list or we may want to insert a node at the end of the list or we may even want to insert a node somewhere in the middle of the list at a particular position. we will write separate functions and routines for these different kind of insertions and we will see running code in a compiler in our coming lessons. Lets just talk about the logic here in this whatever unstructured code i have right now here. So i want to write a code to insert two more nodes each time at the end of the list.we actually want to create the linked list with three nodes having values 2,4 and 6 that was our initial example in the beginning. Ok So let us add two more nodes with values 4 and 6 in to this linked list.At this stage in our code we already have a variable temp which is pointing to this particular node We will create a new node and use the same variable name to collect the address of this new node. So we will write a statement like this.So a new node is created and temp now stores the address of this new node which is located at address 100 here.Once again you can set the data.And then because this is going to be the last node we need to set the link as null. Now all we need to do is to build the link of this particular node,Write the address of this newly created node in to the address field of this last node.To do so we will have to traverse the list and we will have to go to the end of the list, to do so we will write something like this. We can create a new variable temp1 which will be pointer to node and initially we can point this variable to the head node by a statement like this. we can write a loop like this. Now this is generic logic to reach the end of the list. It will be not so clear if we see this logic with only one node as we have in this example. Lets draw a list with multiple nodes. So we are pointing temp1 to the first node here and if the link part of this node is null then we are at last node else we can move to the next node. So temp1 equal to temp1-> link will get us to the next node.And we will go on till we reach the last node. For the last node this particular condition temp1->link not equal to null will be false because the link part will be null and we will exit this while loop. So this is our code logic for traversal of the list all the way till end.If we want to print the element in the list we will write something like this, we will write print temp->data inside the while loop.But right now we want to insert at the end of the list and we are only traversing the list to reach the last node. There is one more thing that i want to point out, we are using this variable temp1 and initially storing the address in A we are not doing something like A equal A.link and using the variable A itself to traverse the list because if we modify A we will loose the address of the head node. So A is never modified, the address of the head node whatever variable stores the address of the head node is never modified.Only this temporary variables are modified to traverse the list.So finally after all this we will write a statement like this temp1 dot link is equal to temp. temp1 is now pointing here so this address part is updated and this link is built. So we have two nodes in the list Once again if we want to insert node with number 6 in this list we will have to create a new node by this logic and then we will have to traverse the list by this logic.So We will point temp1 here first.Then the loop will move the temp1 to the end. Lets say this new block is at address 300.So this Last line finally will adjust the link of the node at address 100.To insert the node at the end there is one logic in these four line if this list is empty and another logic in these remaining lines if list is not empty. Ideally, we will be writing all this logic in a function. we will do that in our coming lessons. We will implement a separate methods to print all the element in the list or insert a node at the end or we will implement a separate method to insert a node at beginning of the list and at a particular position in the list. This is all for this lesson. Thanks for watching.