Definition of Linked List, conception of Node, and understanding basic terminologies

Hey, dear. Let us now try to have an idea about the structure of linked list, how it looks like. Obviously in an abstract sense and how we could build such a list. As I have already told you, that linked list is a dynamic data structure where the elements are created and added as and when required basis. That means you do not need to specify the size at the beginning when you need to build a link list as you do so while creating an array in link list, everything is just explicit. That means we as a programmer need to build it from the scratch by ourselves. It's not like an array where you provide a declaration and create it. Let's try to understand this concept of building link list dynamically. Obviously with an example in this example, I'll show you how a linked list could be built to hold some integer data. Say your program requires to store one integer data at this moment. Then your program will use any of the available dynamic memory allocation technique from the library, like the malloc function call to get the required space allocated in the heap. Let us consider that 300 is the address of this allocated space that is returned by the malloc function and now it puts the integer there. Say the program wants to put ten there in this space. So here it is. Sometime later on, if your program needs another space, it can do the same thing again. Just calling the malloc and get the dynamic space for another integer and put the integer there. So this time the address of the block is 500 and the program keeps 20 there. And if required again, it will do the same thing again for allocating space and assigning the required value there in the allocated space. Let us call the malloc once more say this time the address is 800 and the program keeps 30 there. All these numbers that I'm using their as addresses are actually abstract. The real addresses could be something different. I'm just using them to make you understand the fundamental of link list. I hope you understand this sense. Okay, let's now move ahead. If your program allocates these spaces dynamically, then it will lose all of them. If they are not preserved and it will not be possible to access these elements later on in the program. Hence, somehow we need to keep these addresses of each of these elements stored somewhere in array. As you must know, the name of the array contains the base address, and since the array allocation is contiguous, hence the address of any element can be calculated just by a simple arithmetic that is typically called the address arithmetic. But that is unlikely to happen here as the elements are not contiguous, they are discrete. Rather, in order to keep the track of elements in a link list, we typically use two terminal pointers and known as head and tail. The head pointer is used to hold the address of the first element and the tail is used to hold the address of the last element. As you can see in the figure 300 is the address of the first element, and that is there in the head pointer. And 800 is the address of the last element and that is kept there in the tail pointer. If the program needs to access the first element, it is easy get the address of it from the head and access it. But what about the second and subsequent elements? Now like array, we are unable to calculate the address of the second element as the elements are discrete here, as I have already told you, adding one with the base is not going to get us the second elements at risk, right? If you add one with 300, you are not going to get 500. That's the address of the second element here is the term link in the linked list gets the importance. We keep the address of each subsequent element into its immediate previous element. That means the address 500 of the second element is kept explicitly in a pointer field of the first element and also the address 800 of the third element is kept in a pointer field of the second. These explicit pointers they are at each element is typically called the next pointer. Each element of a linked list therefore consists of two things. First is data. Here it is an integer like ten, 20, 30 and so on. The second is a pointer field that holds the address of the immediate next element. Each such element in a linked list is called a node. The next pointer of last node contains Null. In order to mark the end of the list. I hope you have understood clearly about the structure of linked list. Now, for creating a list, we would require a head pointer to hold the address of the first node, a tail pointer to hold the address of the last node, and a structure node that consists of a data part and a pointer to hold the address of immediate next node. And finally, the next of the last node will always contain Null to mark the end of the list. With this, we come to the end of this lecture. In the next lecture I will start implementing the linked list and we'll. The functions that we need to create and maintain a link list. Thank you for watching.