Hey what's up guys Anuj here and welcome to the DSA course And in today's video we gonna talk about liked list Before this we have seen multiple data structures in this course And today we gonna see a new topic which is one of the favorite topics of interviewer in an interview Multiple type of questions are asked on it. We will see all those in coming videos Today we gonna see basics of link list Because in link list if you have a good hold on basic knowledge , then questions are solved very intuitively inside it So today we gonna study very basics that how you implement linked list, what is linked list How you insert inside it, how you traverse inside it, how to do delete operations inside it So we gonna see all these things in one video And in coming videos we will be solving questions So firstly what is linked list lets talk about this So linked list is also a data structure that stores data in linear form So array also does the same work.
Array also stores data in linear form So what is the difference between array and linked list? So lets talk about what is the difference between array and linked list After that we will dive deep more inside linked list So can you see here also in liked list eighteen, sixteen ten, like this you are storing data linearly How the data is stored non linearly? So non linear like if you go inside tree, you see inside tree non linear One node two children This node two children like that Similarly graph is non linear But here your data is stored non linearly So what is the difference between array and linked list. Lets talk about this So how implementation is done inside array? That you first tell the array what is its size going to be When you initialize the array you tell what is its size going to be So that memory can be preallocated Suppose I want to make an array So you will tell Like what is the size of this array four plus four eight So you will first tell it that initialize an array of size eight and pre allocate memory for that So in this way an array of name a will be created Now in what way this array of name a will be created? A will get a location inside memory Suppose a get location twenty forty inside the array.
After that we will see which type of array is creating The array is of int type In inside integer it will be seen Eight , eight So what is the size of an integer The size of one integer is four bites So four multiply by eight The memory of thirty two bites will be pre allocated And your elements will be stored in such a way First element will be at twenty forty position Then next one will be here after leaving four bites Next one will be here after leaving four bites Next one will be here after leaving four bites In this way they are stored in continuous manner inside the memory But in linked list you do not tell in starting that what is the size of linked list going to be. You do not need to tell You can store elements dynamically inside the array You can dynamically add as many elements as you want inside it later. You cannot do this work here Here if you want to add more elements you will have to make a new array You will have to give that array anew size and copy the elements of this array inside the new array After that you will have to put more elements from behind There it will work in this way But in linked list you do not need to do anything like this Because in starting you do not tell what is the size going to be You come and put a new element You put that element anywhere inside the memory Suppose you had to put element eighteen What you did you made a node.
This whole thing inside it is a node Three nodes are here So this is a node In this concept of node is there Node carries two things inside it one is data part and other is reference of next node This requires the reference of next node so that it can traverse further inside the linked list So suppose we created a node And we had to store data eighteen We made a node and said the data of of this node would be eighteen And next reference of this node will be null for now So a node is created inside memory at this four two six location So this us our head Now if you want to add a new element inside it, new data inside it So you will say that okay I have to put sixteen So in what way you will move inside it First you will go to last You will come to this two four two six location And after that you will check if an element is added or not after this.
Yes no element is there after it because its next is null So you will create a new node This time a new node will be created in which data will be sixteen And the address of this new node will come to the next pointer of this current node So you gave any location to new node You put the new node at this two four two six location So in this node we will say the next of this node will be two six two four So in this way a link is created inside memory Even if they are not stored together They are stored at different different places inside memory. You will also be seeing many holes inside the array Where some other thing may be storing But it does not matter Even now we can access elements in continuous manner one by one How can we do this? Because this element has reference of next node as well See here it has data eighteen But of I ask which is the next node after you.
It knows that it is two six two four So I can jump directly to two six two four So this becomes two six two four And the data inside this two six two four is sixteen Which next node does it have? Which is at next of it? So two inside two thousand thirty So if we wanted to insert ten Suppose ten was here So if node were present before also Even then it would not be affected Node can be anywhere So we put this node The dat part inside this node is ten The address of this node is two thousand thirty So we did two thousand thirty to its next And we put null in its next Because no element is there inside its next S in this way can you see you have a link so that you can reference the next node And you need not to tell in the starting That what is the size going to be So if you want to add a new node, new data after ten Then make a new node after ten And put the reference of that node inside the next of ten That where that node is present inside the memory It can be anywhere inside the memory .
It doe not matter In this ay you can traverse inside the element So this is the funda of implementation inside the linked list What is the benefit of this? What is the need of this? Why we cannot make the array? We will tell in starting what order is going to be Yes you can do But array has one disadvantage What is that? That if you want to insert a new element inside the array in middle, how will you do it? Suppose I want to insert element twenty after sixteen I want to insert twenty here so how can I insert twenty I cannot directly put twenty here because if I do this, our ten will be lost from here So I will have to right shift ten first Then If I right shift ten , then twenty will lost. So I will have to right shift twenty also I will have to right shift sixteen also That means you will have to right shift all the elements one by one after the element that you want to insert inside the array So here the operation becomes O of n Similarly If I want to delete any element inside this array Suppose I want to delete fifteen I want to delete this element So how will I delete? I cannot directly delete fifteen Because I want to store elements in continuous fashion so holes cannot be there inside the array So what will happen All the elements will left shift one by one Eighteen will come in place of fifteen Sixteen will come here, ten will come here, twenty will come here So again n operation are taking place here So can you understand that it has a disadvantage that if you want to insert or delete in middle you have to do shifting Here you need not to do this Suppose you want to insert an element in middle Suppose I want to insert a new element after sixteen And suppose a big linked list is there after this.
Lets insert hundred after sixteen in middle So what will I do I will make a new node inside the memory In that I will put data hundred Now I don't mind where this new nod is present. Suppose this is present at memory allocation five thousand forty It is at this place No problem. What will I do I will put reference of this new node inside the next of sixteen So next of sixteen will be five zero four zero So I will say five zero four zero will be here So it means this link will break from here automatically And this node will be connected with this And ten was at its next And I know ten was at two thousand thirty So I will say next of hundred will be two thousand thirty And then in this way this link will be created Because I put its reference here This put this node's reference In this way this link is created So can you see how easily the element is inserted in middle Similarly if you want to delete any element from middle Then you just have to change the next reference Your element will be deleted easily So no need to do any shifting In case of linked list it is very easy to insert and delete any element in middle.
So this is the benefit of making a linked list over an array You must have seen two benefits First benefit is you need not to tell in starting the size of data structure and linked list You need not to tell in advance You can dynamically insert elements inside it when you want And second benefit is you can insert and delete elements inside it without any shifting So we have two benefits for which we choose linked lists sometimes over arrays Now lets move further and see how can you implement linked lists We will be seeing in Java how linked list is implemented And how can you do multiple things inside it programmatically Lets see that.
So lets discuss the basic building block node of linked list That how node works Because you connect multiple nodes that make a list That we call linked list So basically everything is hidden inside this node Node has two parts. One part is data and second part is next You can data type make of any type . You can store any type of data inside it Either you store integers or characters or strings or any other type of data Like in array you can store any type of data But in next you tell the reference of next node So lets see how you implement this So we have created class named node This structure remains saved always You just change here that at some time int, then at some time character or string or anything If you want you can make it generic How will you make it generic So lets see it first it is like this Int data, node next, next node will be here because you have to store the reference of next node here.
So that next will be of next type And when you will have to make a new node, you will be making in this way You will be calling this constructor And in that constructor you will tell what data you want to add at this time And when you will call a new constructor , a new node will be created at some place inside the memory So this is that node And the data inside it is equal to this data for now The data that you are telling here If you do not want to keep it as int type, you want to do it of any other type in future Or you want to make it generic Like we saw in collection framework you tell the array list of integers. Like that In this way your generic works Here you tell that it is your integer type array list If you want to do the same thing inside your node also It is very easy While making the node you will tell that this class supports the generic So here you will put a type t You can put anything here.
I just put t After that you can remove int from here and say this a T type data And similarly you will also remove from here That it is T type data Now you will not initialize this node in this way Now you will initialize the node in this way that Node of type suppose it is integer You will tell node of type integer like this Now you will pass int inside this because here T has been of integer type If you want to make it of string type so you will do node of type string Then you will pass string here because now this T has type string So in this way node class is created And in this way multiple elements run Lets see that So this is my main function I have tried building a linked list here. Lets see how I did this So first I created tree nodes I had to put three nodes inside linked list I have created three nodes. This is n1, this is n2, this is n3 I have created n1 as new node ten I have created n2 as new node twenty I have created n3 as new node thirty Now what will happen after doing this That inside big memory, at some place n1 will be there, then at sone place n2 will be there, then in between at some place n3 will be there For now they are not connected in any way For now these are three nodes present inside the memory We want to make a chain, linked list of these three So how will we make it? So we say it is an convention inside linked list That we call first node as head We call first node of linked list as head So we created a head We created a reference named head.
We have made a node of name head That we call this is equal to n1 What will happen after doing this That I will call this n1 node as this is our head So basically head will be pointing this node Either you can say point or reference That head is referencing this node After that I want to connect n2 with this node So what I will do n1 dot next Because in n1 , a field named next is also there n1 dot next I can say n1 dot next is equal to n2 After doing this , it will connect with this n1 and n2 will be connected Because I said the next of n1 is n2 So if I want to jump from n1 to ne, I can easily do that If I know n1 I will just do n1 dot next and I will directly jump to m2 Similarly I will do n2 dot next equal to n3 What will happen? The next of n2 will be n3 Now they are connected.
N2 is connected to n1 and n2 is connected to n3 Even though they are present at any place inside the memory In this way these three nodes have been connected Head and n1 are pointing to this node n2 is pointing this even now, n3 is pointing this even now But it does not matter If n1, n2, n3 are lost inside the memory And you have only reference of head only Even then you can go to n3 By iterating Suppose the references of n1, n2, n3 are lost at any time We do not know where they are And you want to find out which element was there at n3 position. Which element was present at third position Come to head and traverse three times Come here, then here, then here Traverse two times. First time here, second time here So you will reach at third. Because these are not different now inside the memory A link has made between these That is why we call them linked list So in this way linked list is implemented And inside memory , the work goes on like this So this is your creation Now lets see how you traverse inside a link list So now lets see how can we traverse inside our linked list Howe can we access every element one by one So I made a new function In which I have called the function named traverse In this traverse function I am accepting a node Which is head Because I just nee a pointer of linked list Even If I get a head pointer for linked list, I will be able to travel inside complete linked list Suppose this is my linked list ten, five, fifteen In this first node which is head I have its pointer So I can travel inside complete linked list Lets see how we can For that I have created a temporary node which is current And I have assigned that equal to head So for now I have made it named current So for now current is pointing this.
Node current is equals to head means current node is pointing ten Current is pointing this node And I ran a while loop. While current is not null Until When current is not equal to null, till then print the data of current So data of current is ten So I will print ten Suppose my output is coming here So I printed ten After that current equals to current dot next Si what is current dot next. Current is this. Current's next is this node So I am saying current is not current now . It is equal to current dot next Current dot next is this node. So now current will not point this instead it will point this node So current is pointing this now Now we will again come inside the while loop So if the current is equal to null. So no current is not equal to null for now Current is pointing this node at this time So print the data of current Current's data is five So we printed five After that what we did current equals to current dot next So for now current is at this node The next of current is this node So now current is pointing its next So now current will not point this Now current will come here Before current was at this position .
Now we wrote current equals to current dot next So current's next is this so the next of current will become this now. After that we will again go in while loop Is current equals to null? So current is not equal to null . Current is pointing this node So okay! Come inside the while loop Print data of current So current is fifteen.
So we printed fifteen It is not necessary that you want to print. It can happen that you want to perform an operation It can happen that you want to find if any element is present or not So for that you will have to traverse the elements one by one So in this way you can traverse there After that we printed. After that current equals to current dot next So the next of current is null So current will start pointing null So now current will come here And now current is pointing null Now we will come here again and check if the current is equals to null or not Yes so we will see current is equal to null So this condition will become false Because we will go into it only when the current is not null But now current has been null We have found that we have travelled the complete list And we will come out of this while loop and we have traversed completely Can you see ten, five, fifteen has printed Ten, five and fifteen has been like this now So in this way if you are given a linked list and you have to traverse in it So if you got the pointer of head, you can traverse the complete list So we have seen how traverse works Now lets see if you want to insert any element inside linked list, how do you do that So now lets see how can you insert an element inside a linked list Suppose you are given a linked list like this Five, ten, fifteen, twenty four, forty And you have to insert the element in somewhere between So you have told which element do you want to insert You have told linked list.
Because you gave head, so you have got the complete linked list And you have told on which position do you want to insert that element So you want to insert it at third position We are taking zero based indexing So third position means you have to insert the element at this place You have to insert an element in between at this place So twenty four and forty will move further a little bit And in between a new element thirty will be inserted A new element will be inserted in between In which data is thirty So lets see how can you achieve this If you were inside an array what would you do .
You would go to this position and right shift all the elements after this And put thirty at this position Our work would be done But you had to do shift operations many times there Here you will have to do nothing like this But here you will have to first reach at that position You will have to first reach at that position where you want to insert this element Because it does not have a direct pointer To reach at that place Because all the elements inside array remains in continuous fashion, so you apply a formula and you can easily jump at that position easily Because you know all the elements are inside And all of them are taking some specific number of bytes So if you want to reach at this place Multiply the position with the size of this byte Then you can reach at this place.
You can access the reference of this place Same case is not in linked list because in linked list elements are not stored at same place If one is stored here, other is stored here, other one is stored at some different place So you cannot reach at that place by directly applying the formula But you have reference Its reference is here, its reference is here So if you want to reach here, you can reach here by traversing So first we will do the same First we will reach at this place We will reach at this middle link How can we reach there? So firstly this dat. Because we want to insert this data, so this data will not be inserted directly First a node of this will be created So I have made a node. Node to add For simplicity I have taken the data of integer type here And I am not typing integer inside node If you want you can achieve the same thing by using generic Node of type integer Equals to new node and in that I passed the data So what will happen with it.
A new node will be created In this way a new node will be created It will present inside memory randomly at any place For now it is a orphan node Now lets see how are we inserting So here we will have to handle a special case That if the position is zero, then we will have to upgrade the head We will have to upgrade the pointer of head So for now its head is pointing here If you are told that insert thirty at zero position only So how will you do that? This is your thirty You will say the next of this thirty is null at this time I make its next as head So its next will be head So its next will start pointing head And then I will say head will start pointing this So now instead of pointing this zero, head is pointing this So in this way it has become a linked list Thirty has come before it Thirty, then five, then ten, then fifteen like this So in this way thirty has come to zeroth index So in this way if the position is zero then you have to do this work Then return because you have inserted thirty at zeroth position But if you do not have to insert at zeroth position So how will you work Now lets see that So if you want to insert any element, then you will have to find the reference of node just before it Why you will you have yo find Because you will be doing all the changes at the node which is before it Suppose we are inserting the element at this third position So I will have to find which node is present at second position So I will need the reference of this node Why will I need? Because what will I do Let me remove this from here What will I do That I will bring a thirty node And the next of this thirty will start pointing this And the node of this, instead of pointing this, will start pointing this In this way your insert will work So basically I need reference of this node I need reference of this node as well as this node Lets see how can we get it The important thing is I should get the reference of the position at this node which is just before the position where I have to insert.
Lets see how can we achieve that So I have made a pointer named previous That we will be moving further For now I have initialized this with head So previous will be pointing this Because head will also be pointing this For now previous will also pointing this And I have to take this previous further till here I have to deliver this previous node to this node So I will have to see how many times I have to run this loop How many times I have to iterate this previous to deliver it here So if I have to insert my element at this third place So how many times I will have to do previous equals to previous dot next Means how many times I will have to take this previous further So I will take the previous further once Then again I will take this further So you must be seeing this that if I want to insert my element at any position, then I will have to iterate this previous loop position minus one times I have done the same here.
I ran a loop that is running position minus one times This is running from zero to position minus one times And what does it doing , previous equals to previous dot next So because here position is three So it will run for zero and one This will run for i equals to zero and one When i will equals to zero, it will be previous Previous dot next so previous will happen here And in next iteration previous will happen here So now previous is pointing this It is pointing this and we will come out of this loop So we got the reference of this loop that we required also Now what will we do This is our two add node That we created in starting The next of two add will be this node Twenty four And next of previous will be two add So the next of two add will be this node And next of previous will be two add And in this way the link, which was in middle will break , and a new node will be inserted in between You will need not to right shift the further elements because they are nit affected by the change that which element came and which went So now at third position, this element will come This will be at fourth position and this will be at fifth position So in this way insert is working One more thing .
There is one more caviart that we need to understand That you cannot alternate these two lines That you cannot do the next of previous this And then next of to add previous dot next Because if you do this Like lets travel these two lines in opposite order Because we have to do this Its next this, its next this So lets first do its next this and then we will try doing its next this If you do this, you will lost that link and pointer of this node If you reverse these two So if you do previous dot next as to add So the next of previous will be to add This link has been made Buy you lost this node now Now you cannot access this node Now you will do to dot next equals to previous dot next So previous is this, next of previous is this To add is this , so to add dot next Means the next of it will start pointing it only Now this link will no longer available This link will lost That is why you will have to be careful.
You do not have to loose the pointer of node inside the linked list Even though if you want, store them at some place Move with a temporary Create a new reference Store there But you do not have to loose the references of your node We have to keep this in mind because we stuck many times here So whenever you are adding a new link or you are doing reference anywhere, keep this in mind that you do not miss any reference while adding a new link You do not loose anything So in this way our insert works You can run it at any other example You see if I have to insert in last Means if I have to insert element at sixth position So how will that work Try checking if the code is blasting or not This code will work But lets suppose you said that insert the element at tenth position position equals to ten Your list is of size five But you said insert the element at tenth position So that is not possible. Here you will do So you will not get the reference here Here null contraception will come We have to see those things That if we are not going beyond the linked list See these types of things So this is our insert working Now lets see if we want to delete an element from middle.
How that code works So I have written the delete code as well And it is similar to insert code Here also you will be required the pointer of previous node You will require the pointer of the node that is just before the node that you want to delete Lets see how the logic is working So I have made function named delete in which first you pass a linked list So to pass linked list, only head is required And also tell the position of element that you want to delete So suppose you passed head here and you want to delete third element This is your linked list. Suppose you want to remove this twelve from here So if you remove twelve , so this will be the next of fifteen fourteen Basically we want that next of fifteen should be fourteen So as soon as next of fifteen will be fourteen will happen So the next of fifteen will not be twelve So this reference will be removed Now if this reference will be removed So then when you will travel, traverse inside linked list, you will come to fifteen From fifteen's next go to fourteen From fourteen's next you will keep moving ahead So in this way twelve will be removed from here So how will it work.
Lets see So can you see we will be required the reference of the element that is just before the element that you want to remove Because we can say its next that the next of this element will be equal to the next of this element's next Are you understanding That its next will be equal to the next of its next That is what I have written that previous dot next equals to previous dot next dot next How is it working . Lets see So firstly if our position is zero Means if we want to remove head We want to remove head element so how can we remove You cannot remove head If you will say head equals to null Then the linked list will end You cannot do like this So here you will write head equals to head dot next So we handled this separately That suppose this is head And we have to remove zeroth position.
So how can we remove We will say head equals to head dot next So head dot next is this element So now instead of pointing this, head will start pointing this So head will point this. So if you will traverse inside the linked list , then you will start traversing from here five will go by itself There exist a garbage collector inside java What is its work That if any position, any variable does not have an active reference So that keep removing from memory by itself So this five has no active reference now , so this will automatically be removed from the memory You need not to worry about this where, what will it work So this node will stay here but this node will be removed from memory after sometime because no one is referencing this node So in this way garbage collector works in Java So if the position will be zero then we can move further like this and return Our work will end there But if we do not want to delete zeroth position Suppose we have to delete third position .
So how will that work So we need pointer of second position How are we finding Again same manner. I didn't changed this code See previous is equal to head Then we are iterating position minus one inside it And we are doing previous dot next So suppose we wanted to remove third element Our previous was here Suppose our head was here And we created previous equals to head So from here we will travel two times Because the position is third so we will travel two times First time we will come here and in second time we will come here So our previous will start pointing this This will be previous Now we just have to write only one line That the next of previous will be previous dot next dot next So this is previous dot next dot next So now it will start pointing this And this link will be removed from here And now this twelve node will be automatically removed because it will present randomly inside the memory and it does not have an active reference Nothing is pointing twelve so twelve will be automatically removed from memory So in this way you can delete any element Here if you want to check Suppose I wanted to delete third element instead of three So how will you delete that? You have to delete fourth element, so first you will come to this position So your previous will be this This will be your previous What we are doing previous dot next equals to previous dot next dot next So previous dot next dot next is null So next of previous will start pointing null So this fourteen will go from the memory automatically Its next will now point this null instead of pointing fourteen So in this way you can delete any element from this In this way your delete works So these were your operations that are always present inside any data structure To insert, To delete, To find , to traverse So we have seen all these How you build them We have seen all these things.
This is your basics of linked list If this is solid clear to you, then after that all the multiple questions that will be coming You will play in pointers only If you have understood the approach of pointers, after that no question is hard inside it You will play all in pointer That we will also be seeing in coming videos how multiple questions of pointers work We will be doing a lot of questions. Other than that if you need questions for practice, you will get them in the link in description With that I am going. If you liked this video, then do like and subscribe the channel .
I will meet you in next video. Bye bye..