Introduction to Linked List in Data Structures (With Notes)

with a very good example i will show what is linked list and why would you like to use it so the name of linked list, if you're listening for the very first time and it is possible that you've read it before and didn't understand that i will start with and example to explain this thing and the example will be of a hospital assume that i have a city over here it can be any city assume it is Delhi and in this city we have many hospitals and assume that we have a doctor over here and the doctor does a full body checkup which is FBC Full body check-up now assume that the hospital has beds bed no 1…2…3 and assume that here the bed number starts from 0 0…1…2…3 4…assume that they are checking different patients on different beds in the hospital will check up the body of them and will do the full body check-up they got 4 beds in the hospital this was the hospital H1 assume the hospital's name is H1 what happened here is something happened and hospital beds were insufficient what happened that all the people who wanted to do full body check ups, firstly here 100 beds were empty from bed 5-6 to bed 100 all were empty if 5 people wanted to go they used to occupy all the 5 beds at the start and did FBC then what happened demands of the hospital beds got increased and then all the beds got occupied what happened was that the doctor got troubled people who wanted to do FBC they got worried that how to do so the doctor told them that we in many hospitals have 1-2 beds empty like in h1 one bed is empty 1 bed empty at h2 have 2 beds empty assume 170-171 beds are free assume that bed no 280 of H3 free and 286 and in H4 another one free assume 381 so the doctor will ask the patient to whichever bed is free go and laydown there assume that the first patient of ours, now this system won't apply here these beds here are not empty all of them are occupied what did the doctor say to the patient do one thing if you find an empty bed go and lay down over there and along with that do the thing, the bed which is next to you write the address of it and keep it with yourself keep it with you and you should know which bed it is when the doctor will see this patient and then he will ask who is the next patient and then he'll get the answer and will check upon the next one this process will continue the same way for the time so after doing this what will happen is that we couldn't get all the beds empty together after doing so the place which was available here and there in other hospitals and while linking them we made a chain which means we'll go to the patient check up on him and then ask where is the other patient will go to the next one and then perform the same activates and then this chain will form the traverse what advantage we got here is that we couldn't get all the beds at the same place so what we did was in every hospital each single bed was utilized utilized them so this is linked list, now that you've heard the complete story forget this story cause this was an analogy i will tell you what is liked list and why would you want to use the linked list as the replacement of the array here when we used to have an array we directly am coming assume that we are creating an array in stack or heap this one is my memory this is my main memory assume that this is stack im not showing you other sections and this one is stack and a heap if I'm creating array something like this in C language int arr 30 i will get that in stack but if i do dynamic memory allocation int*ptr= int*malloc type cast in ints*mylog pointer and*size of int I've told you this, close this bracket I've told this to you how to do dynamic allocation when we do dynamic memory allocation you will get a memory in a heap and now you can point this pointer and use this the memory you've got can be used so like this you can reserve memory when we create and array what happens is 0 1…2…3…4 and assume that you've created 5 and 6 you can have a limited capacity of an array if you wanna enlarge this array you can increase the capacity to elements we have to create a new array and copy in it even if you want an extra element though we had seen that i should reserve a bit more elements will increase the capacity of 100 and will store only 50 elements and use that, we can do this thing but we have to use the memory more precisely only that much amount of memory the amount we want and along with that we want that the size of our array can be so large that we don't know2 today these are 7 tomorrow these may be 7 lakhs even then if we want to allocate memory if the array of 7 expands or if the capacity of array is low then it will be a problem to you so if here is an array of 6 to increase the capacity we have to create a new array but in linked list what advantage do you get in linked list what you do let m e give you an idea you say that i have a structure for now assume this as a node not a structure i have a node on linked list here i have two boxes one is for data and another one for pointer to next assume this is the data and this is 7 and this is the pointer which will point to the next node so the memory which holds 7 and this the pointer this can be anywhere in the heap and along with that i can create another node anywhere in the heap not mandatory to be centavos memory location here in the array if its address in array is 8 and 12 and and 20, 24, 28, 32, 36 and so on will work like this because the integer of 4-4 it will be in contiguous memory location and this is done because you should be able to access do you know this pointer and you for the 5th element here using pointer arithmetic, can access to constant time this is why we used to do like this, what happens in linked list it has a node which has a space for data one is for pointer to next what did i do to the pointer to next node i told that this is pointing to that and this too will run like this and point to the next node so here as you remember the example of the hospital how did I gave the analogy that i just gave an example to explain so what is happening here is i'm going to next nodes again and again finally i'm pointing it to null and now i will explain what is it why did we do like this we could have done it this way here i have a big luxury that i can increase this list at any time assume these are 1 lakh elements and the last element is null i will add one more element something like this and here create a data note and a pointer here i will add 80 in it and after that i will do another null and will extend this list so to extend this list is very easy to extend this is not easy and sometimes a bit impossible too when this grows big so you have to change this and copy into another array here the luxury which i get is that here this links are like a chain can understand a chain all these are joined in a chain if you wanna elongate the chain you will ad another hook in it as you add another hook this chain will enlarge if you wanna add red hook on the 3rd position so you will pull the hook up will insert the red one like this and will place the old hook so to your chain you can add and remove the hooks anytime so the insertion of which can be done easily in linked list if i wanted to insert here so i had to move all the elements from here we had seen insertion in the array if you haven't accessed the playlist do it, i have given the link in the description box if i have to maintain the order, i had moved the elements if here i wanna do the insertion and have to maintain the order too i will ask to break the link place the new element in the between point through this and point through this and then i joined it like a chain it is just like a chain it is a chain with hooks now if you want to insert an element do insert it now if you don't like this one hook i say i wanna keep a red hook over here i want to delete this and insert red i replaced it now assume that i don't like this blue hook and wanna remove it so i will remove it and will place the other hook here, so i just have to interconnect the links insertion and deletion in linked list is so easy as much as is to interconnect two links removed one hook and mixed it with two just like a chain just like how i showed you this is how i will break it , here i don't have achain i lost it actually i couldn't arrange the chain or i would have done the practical for you but i hope you have understood in the board so i just hope how i drew in the board you might have gotten the idea about what it is of LinkedList, if you would have created an array you don't get the luxury to remove this how will you remove this element this is contiguous memory location you have to move it only or else they wont be there in that in array array comes with a condition that the elements are stored in contiguous memory location elements of the array 8,12,16,20,24,28,32,36,40, 44 elements are stored in this way but if you are using linkedlist so it is your call because no constrain is there of contiguous memory location on you if this node of mine is on 100212 location so this element can be on 11810 location this can be on my 988 location at any memory any element it can be these are like the hospital beds which i told you on the start of the video, the beds of the hospital these are the beds in 1 hospitals arranges 1 by 1 and what are these they are beds from different hospitals advantage of linking is that i can insert in it can insert the element in the lost and can delete the ements can remove any element from it, assume that i wanna remove this will remove it and along with that i will put it in idea might sound cool to you this is good we used array for no use array has its own benefit and this has its own where this is advantageous there this one is not and where this is advantageous there this one is not so lets see where which to use and which one will give you advantage and when assume that if you want to access the elements like this 4 element 8th or 9th element so you can access in constant time do you have this pointer assume this pointer how much you have to join to get the access the ptr so how much you have to add and directly you will jump to the 5th element you can directly calculate the address of 5th element when you know address are in 4-4 distance if you know the 8 so you can put the formula and get to know so the first element of mind would be 8*0/4 the second element would be 8+1×4 and nth element would be 8+n*4 if i want to look for the address of the index 5 so will be 28 see o,1,2,3,4,5 my 5th element is on 28th address his is the advantage i can reach to any element very easily here won't happen that, here if i want 5th element so will have to go through all the 4 elements the advantage here is i can extend these paths if i have memory available only for four assume that it is not available, and assume that it is happening and if i have 4 blocks empty at other places so to them i can utilize here i praised array you can access it quickly and here you have to traverse the complete list if i had to disgrace it then i will say that in this deletion is so difficult that if you delete this element so you will have to move all these elements here or if you wanna do the insertion so you will have to move again to make the space and if there is the space then only insertion can happen or it won,t happen which means if the capacity is 100 and you store 50 elements over there then there is a chance of insertion and if the capacity is 100 and you have stored all the 100 then would you put more element there is no place what do you do here anytime any hooks can be broke and made the space and is linked this is the magic of linked list and now here insertion and deletion is difficult and here insertion deletion putting the element in between can be done easily can be seen, broken from here is so easy that we have to create a new node by creating a new node link it like that assume that i want to put 18 here this is a pointer which stores an address this stores the address when i create an arrow which means this pointer is storing the address of this, assume that the address is 280 so in this 280 is there and is pointing that point doesn't mean that it is done by a finger it means in this the address is kept stored i will do and show you by coding it and along with that i'll tell you that i have created notes for you all and saved do download the copy of your notes and the notes which i have created in that as much i have told you has been written in a systematic way that the drawbacks of array are the linklist shines over here have written the thing completely short crisp and to the point are not lengthy notes at all which means short crisp and to the point if you see video and notes together your work is 100% done now you all see here in linkedlist insertion and deletion is done good an tell you one more disadvantage about linked list one more i will tell you what does linked list do for every element this has do be taken extra, this 7 would have come here 11 here and 8 here 18 here and i was storing here what the problem is that every time i need extra memory for pointer to node one more element and i have to add this, my data is here, this is my main data but even tho i have to take this because i have to link in next node similarly as much elements i am adding i get an element extra with me of pointer type because i have to store the address of the element if i talk about the memory so the memory of it will increase linearly with no.

Of elements if we have 100 elements we need 100 pointers too if 10 more elements then 10 extra pointers here direct 17 more elements to store has that capacity so array and linked list is not like that where you abandon array and jump to linked list or use array and leave linked list we may think linked list is good and sometimes we will find array good so we will see that linked list also has types now this video is to only give you idea many people are beginners and i know that if you're a beginner and have learnt only c language to learn these things is so much difficult for you possible that some of you might know the idea which i have told you but definitely i can guarantee that you'll get to learn new things as you move forward and further i will increase the complexity and can assure you that you will understand all these things so i have created all the notes for you so will have a look at them , so guys this is the folder which i have created for you notes of linked list as i have told you that linked list is just like array in array the data is in contiguous location in linked list the node of yours is connected with other nodes and the last element the pointer of this is towards the null pointer as i have told you a while ago pointer to the null means linked list here has ended so if you want to print all the elements of the linked lists, so you can start from here and go on till you don't get the null till you don't get the null you will keep going on so in array and linked list we have seen that the memory and capacity are the same in linked list you can join the nodes remove nodes from the mid doesn't matter in array what happens if you take order and want to maintain it so you have to move the elements if you removed 11 here so to maintain the order you have to move 12 here left, 18 also left 22 also left so this is how you have to move the elements in case of the array if you want to insert and delete but in linked list this work will be very easy if we talk about drawbacks extra space is required for the pointer memory every node has apointer this pointer would not have been required in array but here it is required for linking the pointer in every node so here extra memory space is a big problem and again here we don't have allowance to random access if i know the address of 1st elements the even by calculating i cannot reach at 10th element because this is not into contiguous memory location it is not like if this is 4 then 8 and 12 these are not the contiguous addresses but in our array these are there contiguous address in linked list are not there here the 0 4,8,12 are there and the array is contiguous addresses are there as you change the addresses and move forward it goes on 0,4 8,12,16 like this they get increased what happens in linked lists in linked list elements are there in non contiguous memory location if it is 0 then it can be 2000, or 4000 and then the next node can be again 40 anywhere it gets space there it can link itself from the pointer this was out linked list we talked about drawback that the random access is not allowed memory space is required extra and as for advantages insertion and deletion are fast and along with that here and if you have less memory then contiguous memory is not an issue you can take memory anywhere and keep on expanding as much as you want and this cannot be increased you won't get as contiguous blocks in memory array has this limitation here assume that i have to implement LinkedList to implement we have one way through structures in c language create a structure named node and put the data here i have taken int as a data not mandatory it should be integer it can be any other too but for the learning purpose let it be integer and if i talk about complicated data types i wont be able to explain basic but here instead of data anything can be there but i am taking integer data here sop that its easy to understand after this struck nodes are next which means it stores a pointer of its type which means pointer of struck nodes see here this is our int data and this is pointer to next element it is in itself an element and this is inside pointer to next element which will point an element just like it then it will point again something like this this will point to the null which means nothing or else node like itself so here i have created struck nodes next named pointer already and this is called self referencing structure which references to itself in which such a pointer is there which references to itself that is called self referential structure and we'll see further how we can create things i will code and show you i hope you all have got the idea of linked list and in next video i will explain implementation so i hope you all have accessed the playlist of data structure algorithm and if you haven't done that yet do it now and along with it please do share very less people listen to me and ignore it i would request again please do share this playlist not just for saying please do it only two people shared this playlist and i've tagged both of them and if you share this i will tag to you people too tag and share this playlist i hope you like the videos for now this much only guys thank you so much for watching this video and i will see you next time