Advanced C Features: Linked List

Hello everyone, my name is Atharva and we are continuing this C programming course…. In the last video we had discussed about macros, we had seen how we can represent a big logic or big value in a small term. And we call this term as macros, we saw how we can make our own macros as well as the macros which are predefined in C programming, how we can use. All these things we have discussed in the last video. In this video, we will be discussing one very efficient topic which is called linked list in C. This is such a topic which comes in data structure and data structure is basically that concept where we can efficiently store the data and data structure is such a practice which we can use in any programming language. So, linked list is also part of it. And here we will be seeing the introduction of linked list, exactly why the concept of linked list came, what does it mean and why do we have to use it. Why is it efficient than other concepts? All these things we'll be seeing in this video. So, without any delay, we will start and see what exactly is this linked list. Now, if we talk about our arrays, we had read in arrays that when we are using our single dimensional array, at that time that array is represented in linear form and each and every block in it where we store the values, how that block is basically connected with each other. Since that block is the part of continuous memory allocation. So, the address of our 1^st block, its address, similar to its size the next address will come. That will be basically our second block. In the same way as and when our size will keep on moving, address will keep on changing. Simultaniously our block will keep moving on adhead. So, in arrays a continuous memory allocation used to happen. Which means the first block and second block would be stored together in different location but in continuous and consistent location. If we talk about the concept and create such a scenario that there is not enough storage that is left in our computer. Which means if we visualize it, we would say in our computer so much storage is not left. Somewhere some storage is left, somewhere some storage is left. But all together…since the storage are stored together. It stores all the elements together. One after the other, right? So, if we want such a location of storage and we don’t have space in the CPU. So, how we will make the array. We cannot make the array at that time because we don't have that sufficient storage in a continuous form. To counter that situation we have got a new concept which is called linked list. Linked list is the same type of linear structure in which we are storing the values in the linear form one after the other but how this linked list is better than array that we will be understanding over here. Since in arrays one after the other address location the values are stored on in our computer, but if I talk about linked list, in linked list one value is stored somewhere here in the computer and the second value is stored somewhere else, third somewhere here, fourth somewhere there, which means the values are not stored together, some are stored here where they're finding the space, there the linked list blocks go and get stored. So, what is our benefit from this concept, when we don't have such a storage, where we will get the continuous storage. So, what we will do is we use linked list and with linked list the benefit that we get is wherever we have the empty space, we can go there and store our element over there easily. So, this is the basic concept of linked list and because of this sometimes in place of array we have to make use the linked list. If we talk about linked lists structure, we had said that this is linear itself. So, you can see that in front of us there is a structure made which looks linear, but each and every block in it is basically divided into two parts. Why is it divided into parts that we will understand here? So, like our array, linked list is linear but the difference in this is, the elements that used to be in an array one after the other which means they were getting stored at the next address location compared to the last one. But how is it here? Whoever finds the space wherever, it gets stored over there. How will we know that after this particular block where is the value that has got stored? For that we have divided the blocks into two parts. So, our first part of linked list in that we store the value like we used to store in the array which means in the first part of the block we store our data. So, here you can see this three is the data that is getting stored, 10, 2, 1, all these values are our data and they are getting stored in this way in the first part of the block. If we see in the second part of the block, the second part is empty, but there is one arrow that is made there. So, the second part which we have kept empty, this basically is used why? Because we know that the linked list blocks that we are making, some are here and some there. So, to connect them to each other, in the second part of the block, we store a pointer what does this pointer do? The address location of next block, it points towards the next block’s address location. When we want the next block of this block. So, we asked this pointer, the next block, the next part that you can see of this block in that one pointer is made and it is asked to the pointer to tell us the address location of the next block. Since, it has the information, it tells us that on this particular location on this address, our second block is stored. Then they come in this block, from here the data that we want or the data that we wanted to input, we do it from here and then we ask again to this pointer, tells us that the third block where has it stored. So, it points and tells that it is on this address location. Then we go on that address location. After doing this our data gets stored in different locations. And when we want to access them one by one, we are able to access them easily because in the second part of our block, there is a pointer and this pointer tells us that our next block is stored on which address. So, this is the basic concept of linked list. Now we will not deep dive into it. For now, this information is enough that linked list is a linear design, it's a linear structure and how is it better than array. It is better than array because we don't have to do contiguous memory allocation here. Which means their address would be different. Some might be stored here, some might be stored somewhere else. But when we want that we should acess them in each line then we can acess them with the help of the pointer that is stored in the second part of the block. So, in this way our linked list concept goes on. So, the head that we have written. This head is basically the start of linked list. We get this start once. With the help of start we can acess the entire linked list. So, once we get the first block, after getting the first block, we can ask the address of the other blocks. But if we have to preserve the first part so that we can use it. That’s why we put one more pointer over which we call as the head pointer. About this we will deep dive in the data structure topic. For now, we understand in linked list that it is a linear representation for data. Now, here we will talk about few advantages of linked list. So, there is no need of contiguous memory allocations. We just talked about it that we don't need memory continuously to store any linked list and there is no need to declare the size beforehand, it is dynamic. So, if we talk about our arrays, when we are making the arrays, we are creating them, at that time we also had to give the size of the array, if we are not giving the size, we had to define how many elements are coming in the array, then we used to make the equal to sign and then write it in curly brackets, that there are all these elements in the array. What used to happen because of this? We had to make the array beforehand of that particular size. But if we talk about the linked list, in linked list there is no such scenario. If you want to keep two elements, you can keep it. If you want to keep100, in the same linked list you can keep 100 as well. So, here there is no boundation that you have to keep only this size of the linked list you can increase its size as much as you want and you can reduce it. So, this is one advantage of our arrays on our linked list. Along with that the insertion and deletion process, in linked lists that is very efficient. We won't be discussing about it for now. But let's understand that if we compare with the arrays the part of insertion and deletion in linked list it happens very easily. So, these were few advantages about our linked list, we will explore these concepts in detail in data structures, where we will discuss different types of such data structures which are very efficient and which don't use a lot of memory or a lot of storage. If you think that there is any part of this video or this topic, you might have not understood then you can ask us any query or question related to that topic without any inhibition.

You just have to go on forums.learnvern.com,

you have to type your query there in your own language and we will

come up with the solution or the answer as soon as possible in your own language.

Apart from this if you wish to have a discussion on any topic.

Even that you will be able to do on forums.learnvern.com.

We will meet you in the next video, we will be discussing our practicals, till now whatever topics we have covered in C programming, it can be arrays, pointers or some other topics. We will be discussing practicals related to all these topics in our next video. Till that time, thank you so much.