Linked List - Singly + Doubly + Circular (Theory + Code + Implementation)

hey everyone welcome back to another video today we are starting linked list very important topic for interviews being asked quite a lot linked list is extremely important uh also trees um also hash maps and stuff and heaps sometimes everything is important but uh linked list and trees are like the most important ones because maybe in your internships or whatever they may not ask you dynamic programming they may not they may ask you dynamic problems but they that they may not ask you let's say graph like big big graph algorithms or whatever they may ask you graphs in like new grad roles or whatever uh but linked list is something that's very very popular and in trees as well so trees has like vfs dfs or whatever which we'll learn more about later on so let's learn about linked list what is linked list and how we do it so this video is directed into two parts the part number one is theory link list and uh code of link list and various types of link list everything you need to know that is this part okay so we'll cover about uh singly linked list doubly linked list circular link list how to add and delete in it use the collection framework and also create it on our own so like internally how it works and the theory and time complexity of all these things and everything will will cover okay the second video that will be posted after this is going to be interview questions video that i've been asking like companies like facebook now meta microsoft amazon google uh all these other companies so we'll take questions like this from like the lead code or whatever and like the previous year questions basically and we try to solve those now anyone can solve questions like on youtube anyone can be like okay this is how you solve a question but what we'll actually look into is what is the approach to solve a problem what type of questions are asked in linked list and how do you know which particular question to solve in which particular way so there's like the two pointers method is like you know like the cycle detection stuff middle of linked list these are like some patterns very famous patterns so by the end of these two videos whenever you look at a linked list question you will be automatically like okay this is the pattern kunal told us about apply it you'll get the answer um so yeah things like that in place reversal of linked list uh applying merge sort and bubble sorting link list that's asked quite a lot so link is given to you and they're like hey apply merge sort or bubble sort or whatever so recursion with linked list uh reversal with recursion and iterations everything basically that can be asked to you will be covered in this video so without further let's get started make sure like share and subscribe and comment down below if you love the video but yeah let's move forward i'm going to bring up my whiteboard what is link is first of all so what happens is that uh before we look into linkedlist let's see what are like the limitations or whatever um arrays we already covered arrays so we know that internally in java array is not a continuous memory allocation okay we know that um if you don't know this if you're surprised by this check out the arrays video okay but in general we term arrays as um like a continuous memory allocation or or whatever okay and what happens is let's say you have a fixed size of array um if that gets full then you cannot really add new items in that make sense so if you create an area of like you can do it right now create an array of size five you try to add a sixth item it will not be able to do it it'll say index outer bound or array is full or whatever what is one of the ways to do it then something that rlist does so what what rls does is um something like this okay so for example you have an array like this and it contains like five items uh three four one eight nine or something like that okay so you contain five items and what happens is that you wanna insert a sixth item in arrow list what happens you will double it or whatever internal implementation it may have something so let's say it's doubling it okay it will copy all of these then it will add a new item over here okay so you can see so much not not really cool it's copying it or whatever even though it's efficient even though it's off one amortized or on an average constant time um but still like it's not really cool okay um it's limiting limiting us so what's happening is that um what we want to do is how link list works so linked list basically says that it's not going to be like continuous memory allocation okay this thing will not be like a continuous memory it will not be like fixed instead try to break these boxes down into separate boxes okay so instead a box three is uh you know in the in the heap or whatever box three is putting over here okay another box four is over here another box one is over here another box eight is over here another box nine is over here something like that okay let's say this is what you have internally three four one eight nine something like that cool okay um so how do we make this structure from this structure what does it work okay we're like okay no problem uh you are now not like having continuous memory for every block you are putting it in some random memory that's fine yeah if you want to add new items just put it on some random memory because it's not like close to each other as such then how are these connected with each other they are connected via like this okay using these arrows or whatever which we'll talk more about later something like this if i add a new item it's going to be like okay it's not really continuous memory allocation you can add a new item anywhere in the memory and then you can point this over here like this okay this is basically what a linked list is so now the items are not like continuous memory allocation it's not like index values index zero index one index two you know continuous memory no it's like in different places now three is somewhere else four is somewhere else here if one is somewhere else eight is somewhere line somewhere else seven is somewhere else and they're connected with each other using the pointer that we'll talk more about later it's not the c plus pointer it's uh something else reference variable for example okay that's basically how it goes so what we want to do over here is that um what do we want to do over here we want to um see how it works internally what is this thing so this particular box is known as a node some some terms i would like to share with you so these boxes are somewhat like this in memory 3 pointing to four pointing to five or eight or one random numbers okay 18 or whatever this is a normal representation of a linked list every single item knows about the next item it is a singly linked list okay single linked list okay for example three loves four okay four loves five uh five loves one one loves eighteen so there's this is like a one-sided relationship okay 4 has no idea that 3 has a crush on 4. 5 has no idea that 4 has a crush on 5. one has no idea that 5 has a crush on one okay cool one more thing in linked list that i'd like to mention is a reference variable that is known as head and tail what is head head is actually just a reference variable that points to the very first node okay so in stack you will be having something like this points to 3 okay that's it and tail tail will be pointing to the last one pretty self-explanatory okay so this individual box okay this individual box will have its own type right what all things do these box contains every single box what does it contain i'll talk more about head later okay it's just a reference variable that is pointing to this particular node okay this node itself is a type okay of type node let's say i say class node no problem we've already covered objective and grammar okay what all properties does this class have what what is the class name group of properties and functions what what does all the properties this every single box have a value a box has its own value like an integer value okay can be anything but let's say in this case it's a value okay and the next thing is what what is the next thing the next thing is to whom it is pointing to whom it loves okay the next pointer so it's going to be like it's pointing to some other node of type node only okay this is a type node value is three it's pointing to another node another another object of type node value is four four is pointing to another object of type of type node value is 5 okay so every single object is going to have this arrow that is pointing to and it's pointing to what a node type so node next is equal to what something like that this is what the representation is going to be of every single box over here and every single box is known as a what every single box is known as a node in linked list now if you want to create new new ones and by default this is going to point to none none or null or whatever do java or python whatever you want to do okay that's it this is a structure of linked list okay so one problem over here is what what is the problem over here problem is you cannot directly access the index you can't say list dot get 5 list dot get 4 or whatever no because this only has idea like about like this thing this will have connection with this this does not know when the list is ending list will only end when the when you reach at last obviously okay so this has no idea no one has any idea about how many total elements are there they have only idea about two things who is the person that i love and what is my integer value that's it what they know every node no only those these two things okay so head is pointing to the first node so if you want to go let's say to the third node you'll be like okay create a temporary node that is over here point it to head and run the for loop three times if i go to the fourth fourth node run the for loop four times something will do obviously okay sound good that's it so this is very simple just a class node it has two things now most of the theory and code part that we need to look at uh so right now we're working with single linked list head and tail it's important to know how to work with just the head in the in the linked list because uh tail value makes it easier for us so for example sometimes you want to say that hey add a new item at the last of the linked list okay something like that so you can just say okay i want to add something over here i'll create a new node i'll create a new node like 23 and then i'll say dot next is equal to the new node that i have created so to be like okay tail dot next is equal to the new node that i have created okay the next value is going to be equal to the new node that's true so now tail dot next is equal to new node and tail is going to be equal to new node inserted in the last in very simple steps okay but if tail was not provided how will you insert in last n you would have to first find the last element traverse till the end whenever you find an item that has a next equal to null it means you found the last item then just add add on to it it's going to take o of n time obviously insertion okay but in this way it's taking off one time only so taking a separate variable tail makes things easier for us okay in the implementation part i'll definitely teach you with the tail because uh it it's like one more variable or whatever and the theory part is almost same so uh when we do questions of lead code will actually do it how lead code wants us to do okay if lead code is providing tail will do tail but i'm pretty sure they only provide like the head part i think so then we'll just do we'll just use the head part and we'll do all the questions related to that okay i'll also provide the implementation of without using a tail as well but first we'll do a tail and then we'll do doubly linked list which is something else so doubly linked list is two side love like this you can also go backwards here you can only go frontwards okay hope you're able to understand what linked list is these boxes are just boxes in the memory okay they're pointing to one another using this particular variable every box has this variable and this variable points to the next box okay that's basically what we're doing over here cool so let's uh move forward let's try to code this thing we have to code a lot of things we have to code like um insertion deletion traversal then we have to do questions as well so let's get started okay so we are having a node class so i can just create a i can rename this as linked list so we are actually creating internal linked list okay if you want to see linked list in action like the one that is already provided by java we you can just check this one link list of type integer list is equal to new linked list you can create generic ones as well we have already learned about generics in previous section so like this you can use the internal link list as well this is fine okay but we want to actually see how this add function is add method is working and all these other things okay how is it actually working internally and things like that so i'm going to say custom link list or whatever um or i'm just going to say link list ll that looks good and i'm gonna remove this main one because i just want to have linked list here i'll make main separately okay nope nope nope public static void main and here we have link list okay so this link list is having a class that is node so i'll make it as a private class node it has what it has int value and uh node next no problem so i can say private int value and then i can say private node next i don't want it to like point to um no i don't want anyone to access these things directly that's why i put it as private okay now i'm just going to make a constructor so the constructor is basically going to contain let's say one constructor that only takes a simple value and another constructor and you know right by default what is the value of uh that the reference offer is pointing to when no object is provided done right but what if you actually provide a null as like a next as well that's it pretty much that's about it cool okay so that's my note what are the two things that i'm having inside the internal implementation of linked list so every linked list is having a head and a tail that is also something i want to make private because i don't want people to access it from outside node head private node tail for example okay let's say i take a size as well gonna maintain the size okay constructor when i create a construct i'm not going to select anything i'm just going to say this dot size is equal to 0 or whatever okay cool sound good that's it okay that is it so whenever you create a new linked list you can say link list list is equal to new link list now here you can see that what will be initialized size will be zero of this linked list a head will be there and a tail will be there okay that's it so very simple i hope you are able to understand what is this head and tail pointer this is just pointing to the nodes okay these are just pointing to the nodes these are the reference variables pointing to this node that's it okay every linked list is going to have this linked list is going to contain this entire thing it has multiple multiple nodes each node will be connected to each other using this this thing okay now let's see this in action like how it works one more one one question we may have is like uh okay uh what if you wanna like um let me just bring up my white so let's say you wanna do something like this other very simple stuff uh the very basic stuff is gonna right now i don't have anything okay head is not pointing to anything or whatever it's just null empty links list that is available over here and i want to insert the first item in my list i want to insert item at the very first index okay i'm saying index but i'm saying like the very first position what i would say okay so what do i have to do for that first of all you have to create a new node okay node is equal to new node that's it created a new node three okay sound good awesome that's it so now you're not not that it you created a new node one thing let me share with you is let's say you already have a linked list okay imagine you already have a link list like this okay head is pointing over here and uh you want to add a new node at the very first index you want to add something like 14 or whatever how do you do first of all you create 14. why do i get these lines you create 14. now what do you need to do in linked list what i'm going to tell you is that uh how to solve interpreter problems and such questions that i ask you like what to do what to do try to draw it on pen and paper and see what is required don't see how to do it see what is required so now i'm asking you if you're adding an element over here like before this you want to add an element how would it look like what is like the common sense and like not i'm not asking you how to do it i'm saying how would it look like this 14 internal if i expand this it will look something like this value is equal to 14 next is equal to right now null in reality what should it look like it should look something like this if you're inserting an element at the very first index okay so that's step number one when solving linked list questions c visualize what to do okay now we'll see how to do it so it's saying this should actually point to this variable this this particular node and what is this node head so can i not say that this particular node dot next is equal to head can i not say that isn't it true make sense okay so what is happening head is actually let's say pointing over here to 3 now what will happen is 14 dot next will also point to 3 like this okay this is linked now but there's a problem i told you that head obviously means that the first element of the linked list but now the head position is now second element so we have to update that as well what is the head going to be if this is equal to node this is the name is node let's say what is the head going to be equal to i can just say simple head is equal to node so now my head is going to be equal to node sound good make sense okay if the if there was no single um element provided okay if there was no single element provided if there was like an empty list so what would you do you create create a new one you create a new one let's say i create a node like 18 i create a node like this okay i create a node 18 and after that i do something like um what what is the next step head is equal to node so head was initially what null because i did not assign it to anything you can see uh in the you know when i just did i just said private node head that's it so i'll just say head is equal to node head will also be available over here but one thing remaining is tail let's say if you have tail also so if tail is equal to null then obviously in theory if there's only one item that means tail is equal to null initially and when you add the first item shouldn't head and tail be equal if there's only one item then head will be that only tail will be that only so i can say if tail is equal to equal to null or whatever what tail is equal to head cool sound good and since i have a size variable as well i'm just saying size plus plus that's it you can calculate the size as well whenever we wanted you can just start from the head and keep counting till you reach null okay you can do it as well but i i'm doing it in a simple way okay that's it hope that clears things up and it's gonna take how much amount of time are you running any for loop are you running anything like that no constant time just one single step okay let's try to code this okay so how can i insert i can just say i'll create a public method i'll say public void it's not returning anything insert at the first first particular like position i'm gonna give it a value okay oops wrong braces that's it what do i do i say create a new node first of all so create a new box is equal to new node and i'm gonna put the value over here now i have the new node over here i want to point this node the next of this node to head so i can say node.next is equal to head no problem now i'm going to point the head to the newly established node because head always points to the first node like this okay and then i can say if tail is equal to equal to null it means that this is the first item being added so i can say tail is actually equal to head both head and tail are pointing to same then i can just say size plus equal to 1 or whatever that's it as simple as that okay make sense how will you display how will you display let's see okay so how am i going to display this thing um i have only been given this head thing okay i've only been given this head thing so how am i going to display can you just say that hey canal um print whatever the head value is like while or i can just make it in a new line okay i can say something like while something let's say head is not equal to your null or whatever keep printing it okay so we'll just say print head dot value but there's a problem here there is a problem here what is the problem so if you print head dot value and then head is going to be updated let's say okay uh you have this three five nine eight or whatever and this this is like and then null this is head it's gonna be like hey his head equal to null no it's not okay print three then head is going to be moving forward so head is equal to head dot next let's say head moves over here now okay head is equal to head dot next this is actually wrong why i'll tell you later on this is wrong okay what happens is that when you have started printing it and in the end head will reach over here your null and you will be printing all the items cool sound good but now you run this function again the display function will be like okay while head is not equal to none print hell while head is not equal to null print head head dot value but it's going to be like hey head is already null so you're only able to print it once and you actually change the entire structure of linked list head always supposed is supposed to be at the first element but after you started printing it it became in the last that's why you never move head like this until unless you're changing the structure of the link list when i'm adding a new element i'm changing the structure when i'm removing a new element i'm changing the structure right so if you just wanna if you're basically if you're not changing the structure why would you want to move ahead because head actually changes the structure so what you're going to do is instead of this you're actually going to have a new node you're going to say a new node temporary node is actually equal to head so you know head is going to be pointing to this node and when you say temp is equal to head that is also going to point to same node so in the display function you will have a temp and that temp you are going to keep moving forward till it reaches end because if it's in the function its scope is only in the function it will be out of scope when the function finishes already covered in functions video and stuff okay so this is a very important concept of this temp node so when i say temp is equal to head it basically is pointing to the same object that head is pointing to so when you do temp dot next m dot next m dot next print print print what happens to what happens to temp we don't really care because temp is not a part of the structure of the linked list what is the part of the structure of the linked list head and tail okay so this is very simple take a temporary variable print deck do next print do next print do next while it no you won't be using a for loop because you don't know how many times the loop will run so use a while loop that's it this is very simple let's code this okay so i can say something like display it's obviously not going to return anything so public function not returning anything display and it's not taking anything either okay no problem i'm creating a new note temp that is pointing to head so changing temp will not change head because i'm not really like modifying the node i'm actually reassigning it to next next i'm not saying temp dot something like attempt just change the value of temp or whatever no it's actually just both are pointing to the same object we already covered like objects and references so when i do temp is equal to temp dot next it means the temp easy equal to means temp itself is changing to something else which is temp dot next then again temp dot next okay so i can say while temp is not equal to null what do i do again say print temp dot value plus something like this and then i say okay you have printing correct one move ahead so now temp is equal to the next value of temp temp dot next are you able to understand what this next represent this is nothing is just this particular next is just a pointer it's just a reference variable that is going to point to the object that i provided okay and whenever we are adding or whatever we are actually providing this as a next pointer next pointer so internally it is like this is what links each other you know using that diagram that i just showed you that's it in the end i can just say print end um no new line and let's try to see i can say list dot add sorry insert first three list dot add insert first three and i'm just going to say something like 3 2 8 and 17 so it's going to be 17 8 2 and 3 when we print it so i can say list dot display it should be 17 8 2 and 3 and end 17 eight two and three and end that's it of n where n is the number of nodes that's how much amount of time it's taking okay so initially temp will be pointed over here it'll be like hey it's a is temp currently that it's pointing to is that equal to null it's gonna be like uh no it's not okay print seventeen and print an arrow and temp is now equal to temp dot next what is the next value holding for this node eight so this is now going to be equal to temp okay so hey is temp equal to null no no print it temp is equal to temp dot next is temp equal to null no it's not okay print it temp is equal to temp dot next stamp is equal to not no okay print it temp is equal to temp dot next three is next is obviously null because by default value is null of every you know like nodes and uh of complex objects that you have you've already covered this like by default value is null so yeah it's null so it's not going to print anything it's not going to do anything like that this is this will not run and it's just going to print and that's it cool that's how we do it okay okay now let's look at one more example which is uh sort of like opposite to this so this basically means that what if you want to insert the element at the last last particular point okay so you have a list like this you have like 3 5 8 nine or whatever this is the head this is the tail all right cool so now you want to insert a new item you seven insert 17 or whatever first you would have to create it so node node is equal to new node 17 so this is a node okay now before actually looking at how do we solve this we have to see what do we need to do so in the end internally it should look something like this what does this mean now see what how to do it so what does it mean it means that tails next should be equal to the node that i have just created no problem tail dot next is going to be equal to the node that i have just created okay and obviously now the structure is structure is changed so tail obviously always lies on the left on the last side so here tail will lie over here so i can just say tail is going to be equal to node okay obviously when this function gets over the node will be removed like not the node will be removed but this node pointer that is over here that will be gone out of scope right pretty basic uh scoping stuff okay size plus plus that's it okay and one more thing we want to do is that what happens is that if tail is equal to null it means that nothing is over there then i can just call the previous method that i just said okay i can say insert first insert first value cool that's it let's code it okay so i'm just going to say that i need to insert it at the last index no problem public void insert at the last index so i can say in value so first of all what do we need to do create a node create a box node is equal to new node value now a box is created but this is not like really connecting with anything i want to connect it with what tail so i can say tail dot next is equal to note exactly what i did in the white board and then i can say tail is actually equal to node that's it size plus plus but if tail is empty if tail is equal to null means list is empty there is nothing over here so i can just say call insert first value and don't call the code sample below it return it from here or you can put it in an else condition if you want but this just looks much more cleaner okay so that's basically how you can insert an element at the last index what is the time complexity for this constant only you're not traversing or whatever so in case you are not maintaining the tail and someone asks you hey insert in the last what would you do like this you will go till till this is not equal to null till next is not equal to null and then you will just put it over there okay that will take off end time so if the interviewer asks you what is the benefit of taking this extra variable you can say if you want to insert at the last or whatever um you can definitely do it in constant time okay let's try it i can say list dot insert last 99 let's try to print this 99 should be at the last okay 99 is at the last no problem how it works i just covered it on whiteboard but what if i want to insert it at a particular point like a particular index if you will at a particular position like at the zeroth position or first position or sixth position nth position or whatever how do we do that let's see all right so now the next point is what if you want to insert it at a particular index or whatever so you have some random numbers like you know a linked list 3 5 9 8 12 18 something like this um all right now you want to insert it somewhere over here for example okay you want to insert an element over here how do we do that so first things first if the index given to you is 0 you can just call the insert first method that we just created if the index is equal to the size then you can just call the insert last method we created no problem okay but what if the index is like index number zero we have one two three four five if if it's let's say index number three you have to put it at index number three okay let's say index is equal to three in that case how do we do it you're going to start checking from here till the index before that okay so we're going to start from here hey from one till less than size so you're gonna go ahead go ahead go ahead go ahead and that one then what you're gonna do you're gonna say this particular one that i'm currently at at this at this node okay so first thing is just reach behind it this node i'm just going to say hey so basically what we're trying to do is something like this isn't this with what we want 7 like this isn't this what we want cool we want this now we actually see how to do it so you go like this you go like this and over here you you reach okay you reach over here then you say node that you're currently at the next is going to be what the next is going to be the new node that you have created okay and one more thing you have to do is you actually have to point this to the next of the previous one so when you update the next over here like this this path will be removed right so how will you do this dot next is equal to this thing are you able to understand so that's what we want to do we have to store this somewhere as well in temp or whatever then i can say new node is equal to temp that's it cool let's try to see okay so how do we code this thing first we need to go to the previous one like this but before that i just need to say that um oops not that i just need to say public void just insert a value at a particular index okay something like that and now i'm just going to say that if the index is 0 means it basically means what insert first so if index is equal to equal to 0 you can just say insert where is insert first insert first e value and then you just say return and then you can say otherwise if index is equal to equal to the size then you can say insert last value and return that's it otherwise what do we do otherwise we have to obviously like start checking from head node temp is equal to new sorry not new start checking from head and you have to go till here whatever the three is to have to go till two so if the index is three you have to go till two okay so i can say if the index is three you have to go till two so if i just put index over here not starting from zero going to start from 1 because 0 is this itself right and i'm just going to say temp is equal to temp dot next okay now it will be available over here it will stop when it reaches behind it now i'm just going to say this this dot next is equal to the new one that i have created no problem so i can say first create a new node node is equal to new node and here i can just pass my value and i can also pass what pass what is the next value of it okay so you can see this constructor over here pass the value and then pass the next okay so i can see over here um pass the value and then pass next what is next whenever you create this node value will be 7 next will be equal to what next will be equal to current dot next current dot next which is current temp temp dot next able to understand that that's it what do i need to do after this so basically this is what happened this was sort of like this you created a new 7 and you said 7 the value is 7 and the next value is automatically what this node actually switched the name over here so here this is actually temp so it's temp dot next obviously temp dot next now just remove this tap dot next okay sound good so temp dot next is going to be equal to the node that i have created okay size plus plus let's try to see i can say insert list dot insert let's say 100 at index number three let's try to print this so zero one two three other things like you know uh index is more than the size or whatever you say index number 200 or 300 over here that you can take look at yourself right because you can't really have that much you know you can throw an exception over there we already learned about exception right that's it very simple so always try to visualize it and then try to see okay cool that is it okay let's move forward okay now let's try to delete some items from this so let's say same thing we'll do delete first delete last and things like that and delete like from an index also so delete first is very simple uh this is a list given to you let's say there's a simple list given to you how do you delete first what do we mean by delete first delete first means that head should come over here this means delete first that is it that's it yeah is there anything else that you need to change no because whatever is connected with this head like previously or whatever are we really going to access that anytime after doing this this will still be attached to it like this but when you run insert first again wouldn't this be overwritten so what do you do to delete first just do head is equal to head dot next that's it just move ahead ahead by once okay that's it you store this value 3 and return it later on but just move head ahead by once okay that's it one thing i would like to share is let's say if you only have one item like this okay and head is also this tail is also this and you say head is equal to head dot next what is next next is null so head will now be equal to null means obviously there is it's empty so that makes sense but tail is still pointing to this tail should also be null right so if head becomes null put tail also null as well that's it yeah simple so delete first so i'm going to say public integer because it's going to delete the first element then it's going to be like value is going to be equal to head dot value okay and then i'm just going to move head ahead by once head dot next okay and then i'm going to say if head is equal to equal to null put tail is equal to null also that's it don't forget to reduce the size and just return the value that is removed okay i just say something like print list dot delete first run okay so 99 was at first and sorry not 99 uh what was that first inside first three let me just print it as well like before doing this let's print it as well then let's see what was removed okay so 17 was here and it says 17 was removed so yeah form first 17 was removed very awesome okay cool sound good all right now let's move forward let's say you want to delete the last item okay so you want to delete the last item you're like hey i want to delete tail so hey canal can you do tail is equal to this previous one how can you do that how can you do that every node only has one particular uh reference point which is next does it have a previous no can you really move backwards like this can you say tail is equal to tail dot previous or whatever in this you don't in doubly linear you can but here you can't so what is the problem here try to identify what we have to do like what should the entire structure look like and then try to see like how we can actually do that make sense okay so what do we need to do we need to actually say that if i am able to reach over here at the second last item okay at the size -2 item what can i do i can just make it till and point it's next to null isn't that what i can do make sense the real question is where do we get this thing how do we come to the size minus second item iterate over that times if you want to go to the size minus say let's say fourth item just move the for loop four times how difficult is that not at all difficult so you want to get the value of this node so we can get we can create a get function i can say give me the reference of that node okay so i'm going to say something like public what type is it returning node type get index value okay so you can say node node is equal to start from head move ahead index times okay node is equal to node dot return the node that's it now when you put any number over here it will actually return a reference pointer to that node okay so if you want to say that let's say we do something like this so let's say we do something right delete the last element okay public it's going to return an integer delete last element not gonna take anything and delete last that's it if the size is actually less than equal to one in that case what will happen it means that you're just returning only one item so you can say return delete first okay otherwise what do we need to do otherwise what do we need to do node second last is equal to get what is the node item that i want size -2 it will actually give me a pointer the second last will point to this thing now what will i do let's say this is pointing to second last what do we do now we take the value that is to be returned so i can say in value is equal to what tail is removed so tail dot value in the end i'll just say return value but i need to modify this as well actually need to remove this so here what do i need to do i need to say that tail is actually equal to second last okay tail is actually equal to second last and uh tail dot next is not equal to this now it's actually equal to what null tail dot next obviously tail obviously points to null that's it because initially it was pointing to this 17 we don't want it to point to 17 we actually want to remove this and make it point to null this will be removed by garbage collector later on that is it yeah so let me just print list dot delete last and then i'm just gonna say list dot display okay 99 oh sorry i spoke in hindi nevermind i said pika means okay okay so 99 is removed okay last is removed what is the problem here if you have to complexity is often you have to traverse the entire thing go to second last and remove it okay cool similarly there will be one like you want to remove it from a particular index how will you do that go to that index minus one how easy is it now so go to this index minus one okay and then just you can say that um the next of this is going to be actually equal to the next of this this thing makes sense so for example you want to remove eight let's do it step by step first of all you have to reach over here okay whatever thing you want to do with this so if you want to remove it or whatever you obviously have to go one step behind because that is the only way you will remove this link right that's the common sense behind it so i can say delete a particular index okay so i can say public integer delete hint index mean i can say if index is equal to 0 in that case what do i do just return the last one so return delete last okay no if index is zero uh delete first sorry my bad and if index is equal to what size minus one means last index you can just say delete last delete last okay that's it otherwise go to one minus if you wanna remove eight go to five so whatever index you wanna remove node previous is actually going to be equal to what get whatever index you want to remove minus 1 just the previous node so this node previous will actually be pointing over here this will be pointing over here now what i want to do is i want to say the removed one is going to be equal to what value is equal to what what is this going to be this value means previous dot next dot value no problem previous dot next dot value in the end i'm just going to return this return value okay that's it but we need to break this chain we need to break this chain how do we do that we can just say that previous dot next is equal to previous dot next dot next okay so i can say previous dot next is equal to previous dot next dot next is all objects and references internally if you're making a change by a previous original one will be modified it's a very basic object this is what will happen then like this okay i don't really need to care about this now even though it's pointing to this is there a way to access this now no we'll just go from here here here here like this that is it let's try to try to do it list dot delete index uh i can say index number two and then i can say list dot display so index number two is hundred hundred will be removed 100 is removed no worries complexity is what you are traversing yes i am traversing over fn go off and okay similarly you can find a value if you want to okay you want to say hey i'll give you a particular value return me the node for that if you want to find it okay so i can do something like this i can say similar to get here i'm not going to pass the index i'm actually going to pass the value and i'm going to say find the node that has this value as i'm going to start from here and i'm going to say while node is not equal to null try to search for it if the current nodes value dot equals or i can say no i'm taking an integer so is equal to equal to value then what do i do i just say return this node otherwise just keep moving forward okay so basically it's going to be like hey return me the pointer to that node that contains 12. okay start from here is this equal to 12 no it's not okay move forward it's not move forward is this equal to 12 no it's not is this equal to 12 no it's not is this equal to 12 no it's not is this equal to 12 no it's not is this equal to 12 yes it is return this pointer node will be pointing to this this pointer will be returned reference variable but if nothing is removed return means that you are not able to find it in that case you can just say not found return null that's it okay again complexity is what often where is the total number of nodes cool this is pretty much about it okay now one thing you'll recognize what if we're not using tail or size or whatever these two things are not required and all please teach us that also okay so that's about it in every video i tell you like um you know how to approach a problem okay so similarly um like we are solving these problems and whatever but how do we actually build the intuition for linked list problems obviously we will be doing a lot more linked list problems we'll be doing like interview problems and level one questions uh google facebook amazon microsoft level questions actual questions that was that were asked in these companies and not just that we'll see what are the patterns that are used to require to solve linked list problems okay so so far what we have done is when you're trying to learn linked lists and stuff so there are two approaches one when you're learning and second when you have already learned about the basics and medium questions and mastered it okay during that time you would have it on your grasp but many students who will be watching it right now are beginners they might not mind might not know about linked list so as i mentioned already to perform anything that has been asked like insert insert at a particular index insert before insert after or whatever things that have been asked first try to draw it like i did try to see what all arrows you need to connect okay and then code it exactly what it says i literally explained it like right now and i i did it on the whiteboard then i did the same thing in code just one or two lines only linked list is not difficult at all it's actually pretty simple okay and this thing that you see on the screen you'll be like canal um over here in your whiteboard let me just show you my whiteboard again um how are these things like actually this arrow how is it connecting we are not able to understand this thing how like why are you thinking so much like let me dive deep into it no problem so few doubts that very basic students know who may be having is you will be having two doubts okay what is head and stuff or what is head or tail how is it working why is it fixed or whatever and like house conduct how that is like not moving and dialing this is connected or whatever second out you may be having is how are these connected by themselves why can we only move forward why cannot we move backward why can't i directly jump to a particular node okay so that's the whole idea so let's see it's very simple when i'm talking about a particular node this node this particular circle is itself a data structure right i talked about it previously over here you can see this is a data structure of type node it has an integer value of its own box and to what it's pointing to so internally it will look something like this now you like you know we understand that this value that it has is an integer type but why is the next pointer or next to reference variable whatever this is of node type isn't it obvious because when we have something like this when we have a linked list like this this will have some things like integer value 5 and it will have a next pointer that is actually going to be pointing to when we say reference variable is equal to object does it not mean that it's actually a reference variable pointing to an object in heap so internally it will also be something like this this is a reference variable in this object it will be pointing to some other object in heap this object itself will have its identity 18 it will also have a next pointer next pointer pointing to some other reference variable to some other object this will pointing to some other object you can see these are not like someone's at my door you can see these are not like um index values that you can directly jump on it may be somewhere in the memory this will be at some other place in the memory some other place in the memory right that is the reason you cannot directly jump on to it cool so if you can't directly jump onto it and you can see that okay i'm saying if i want to go over here from 5 to 18 i can say this node name dot next can you go behind is there any single variable that will put you behind the node let's say you're at this node is there any single variable that you that will put you behind it no there isn't in this in this at least there isn't okay so this is a basic understanding of what this this thing represent next this is a reference variable of type node because it's pointing to something that is type node that's why it's a type node here that's why it's pointing to type node okay now the next thing kunal what is head so please try to think about it this is three this is five one nine null okay this is head whenever we traverse whenever we move forward we don't change the head we actually say node is equal to the temporary variable is equal to head and we try to move this thing now because this scope will be in the function only only and it will not change structure of linked list because head is a part of the structure of linked list this temporary nodes and stuff that i'm taking just for traversal is not so remember when we did display if you were just saying print head head is equal to head dot next what is dot next dot next itself is a note type so head will move over here now the entire structure of linked list is changed when you try to print it again it will not be able to print because head will be at null head should always be over here but if you are changing this node if you say node is equal to head then there will be another reference variable that is going to be pointing to the same node now when you do print node it will print three node is equal to node.next node is equal to node.next so obviously if you make any change via this node it will be represented in these nodes as well remember node dot something is equal to something this is actually saying making a change but are we doing this is there a single code sample where i did something like this no the only thing i did was node is equal to node dot next this is not changing the pointer head pointer please i'll explain it again i in the previous lectures i have said this many times if two or more reference variables are pointing to the same object changing making a change in that object via one reference variable will obviously lead to the change in other reference variable as well because they're pointing to the same object but taking these two examples saying node is equal to something and on the other hand saying node dot something like node dot value is equal to something so which of these is making a change in the object original like normal object obviously this one this is making a change this is reassigning so are you able to understand never never ever i did this i never did this i'm only doing this just reassigning that's how traversal is happening okay there's a basic understanding of how linked list works and functions you can think of it as a one-sided love three loves five but five has no idea three loves five okay for that we'll learn about doubly linked list double english is very simple what is doubly linked list you have just one single side love here you can just add one more point let's try to see that let's learn doubly linked list now it's actually very simple and we'll be following the same approach draw it code it that's it if in linked list and binary trees and dynamic programming graphs and stuff all that all these things that we'll be doing now if you are not drawing on pen and paper you cannot learn it okay visualize on pen and paper first then code now let's see doubly linked list because here i mentioned you can only go forward you cannot go backwards so let's see how we can now go backwards as well from one point let's say you're over here and you want to say what is the previous node there is not a single possible way to move directly backwards in this okay so we need doubly linkage for that let's see how okay now let's look into doubly linked list literally the same thing nothing new just one single additional reference variable is added how does it look internally pretty self-explanatory you have nodes like this random nodes this has a next that is pointing to 3 it has a previous pointing to this this has a next pointing to 2 it has a previous pointing to this obviously null and every single node has a next and a previous so the next for eight is three and previous for eight is null so obviously whenever you are at the for the head previous is null and for the tail next is null this is also this is like something we saw before as well like tails next is null in single linked list as well okay so now it makes our life a bit more easier you can move backwards very very easily how would the structure look like every single node every single box will have this structure integer value first thing node next just like previous example node previous is the new thing i did okay cool now for example you want to add a new item over here at the first first of the list front of the list insert first how do you do that first of all create a new node let me just let me just move this thing so when i add let's say 13 at the front of the linked list how do you do that okay i'll create 13 first no problem created a new node 13 okay no problem now we just need to connect so before connecting visualize this how will the pointers work how will the arrows work we want to have something like this isn't this what we want we want this now the answer is front of your eyes literally what i drew we can code this okay what did we do we said you created a new node okay let's see what we did revise first things first j cole all right so what did we do now we need to have this pointing it's next to this obviously so first step create a new node this is something you know we can say node.next is equal to what head no problem please draw the results otherwise you will not understand otherwise what what is the next thing node.previous is going to be equal to what null no problem node.previous is equal to null no problem no problem right head is going to be equal to what the new node okay so i can say oh but before that i need to say that uh head dot previous we need this one arrow as well right we forgot about this so you can say head dot previous is equal to node what else do we need now this is the first node the 13th one so this should be head so head should be equal to node okay here we need to check for null pointer exception okay if this is the first node you're inserting and you do head dot previous it will give you error because what is the previous of head uh by def uh like what if like head is null itself and you do null dot previous error null pointer check for null pointer how difficult was this constant time are am i running any for loop or anything nope this is it okay and how is it different than uh let's first code this and then we'll see like it's nothing different okay it's nothing different you're like what are the advantages of doubly linked list or whatever well if you're dealing with backward reversal then only it's beneficial okay how is it really any different in complexity or like the logic as compared to the previous one no but when you're dealing with like traversals and stuff and you want to move backward as well in that particular case doubly linked list helps in some questions for example this will make much more sense in questions not right now right now we'll be like no normal list single link is doubly linked the same thing this is an extra feature we are not utilizing this anywhere if we are not utilizing this anywhere then why are you teaching us this we will utilize it in the next videos we are going to focus on interview fan interview level questions okay actual questions that are asked and are still asked to this date okay so some people ask reverse a linked list level part reverse parts and things like that in that case this is really going to help out okay so let's try to code this thing okay so here i have my whiteboard and uh doubly linked list is actually very simple here you can see that um what can we see what do we need i don't memorize anything just uh just copy paste whatever is we have discussed if you memorize you will forget but if you understand and think the logic behind it that the way i'm teaching you how to think in an interview then you will never forget it okay so first things first uh we need this class node doubly linked list oops new class doubly linked list okay so what do we need private class node okay uh we need um is it recording yeah integer value node next node previous no problem integer value no type of next no type of previous this is the only new thing okay constructor another constructor okay no problem very cool stuff hide this don't need don't need that okay so now what do we do we need to say insert first where isn't insert first let's create insert first before that we need um we need a node like the head as well i'm not putting like a tail over here okay no worries cool by default it will be null every object the reference variable of an object points to null so i'm going to say public void insert first what are we inserting into value so first things first create this box okay no problem i'll say node node is equal to new node value box being created by default these will be null okay already explained in object oriented programming playlist so check it out the links are in the description okay so that's it and after this it's saying node.previous is equal to sorry node.next is equal to head so i can say node.next is equal to head and then i can say node.previous is equal to null node.previous is equal to null and then i'm saying dot previous is equal to node we need this particular line as well so i can say head dot previous is equal to the node i have created but head may be null if you're inserting it for the very first time hence this will give error so if head is not equal to null only then do this thing otherwise it will give error null pointer okay what is the last step head is equal to the new node okay that is it that's it cool sound good we can print it as well so i can say public void display okay something like that node node is equal to start from head you already know why i have taken node over here okay this is a temporary variable we will able to change node this thing that i just talked about node is equal to node dot next it's actually not changing the structure of the linked list we're just reassigning this variable to next node next node next node if you want to change some value then you would have to do node dot something and that would itself modify the linked list values we are not doing that we are just printing okay so while this node is not equal to null what do we need to do print node.value plus arrow so print the value move the node ahead okay print a new line cool i'll create a let's do it here only i'll hide this i'll say doubly link or i'll just do one thing one second i'll just say insert first something like this hide this and then i say doubly linked list doubly linked list um yeah that's it list dot dis display make this private so no one can access it from outside um and let's try to run this obviously it will just print 17 8 2 and 3. okay cool and this is the exact same code off so you can see insert first of this and insert first of like the previous linked list pretty similar stuff isn't it we're just adding a few more pointers if you talk about display this is literally the same thing the display part okay but one more thing is you can actually print in reverse as well because we have the previous pointer so let's try to print in reverse it's actually pretty simple click display reverse how difficult would that be if you want to display in reverse how would it work let's see so you want to display in reverse then what do we do first of all we need the last node so if you have tail you can just start backwards isn't that what you can do so one more thing i can do is i can just remove this thing and i can actually put a last node over here and say node last is equal to null okay i can just keep updating it as node so by the end of this while loop this will actually point to the last node okay over here we'll have last now i'm going to print backwards how do we do that this will have last last entail same thing we are not taking tail so i just had to do it like this okay you understand what i did by last right as you're moving node ahead i'm just saying last is equal to node first node will be this last will be equal to this as well it will print it and move forward the last will be equal to this print move forward last will be equal to this last will be equal to this then our last pointer will be over here so now i just want to say why last is not equal to null because you're moving backwards this will also become null at some point while last is not equal to null what can you do just print it last dot value plus like this so last is equal to move backwards last dot previous that's it print in reverse cool cool and new line over here that's it let's try to run this see what we get okay i got to i forgot to add like this is the start for example run okay 17 8 2 3 and 3 2 8 17 start cool pretty easy similarly what else did we do we did insert last where is insert last insert and delete and all these are things it's you know totally up to you you can do insert last we can do insert it's totally literally the same thing what is insert last you tell me if you want to insert a new node let's see let's draw it okay so i don't think i even have to teach you this one you can do it on your own it's very simple what are the steps first draw on pen and paper connect the lines code it link list is not difficult this is nothing main thing will come when we do questions this is nothing this is literally nothing this is just internal implementation how things work and time complexity and all these other things this is literally nothing okay in interview you won't even you won't even be creating your own linked list you can use the internal one by java or in like if you're using other languages like python they have there as well if you're using c plus plus you can use stl or whatever this is nothing it's just for understanding purpose okay this is very simple stuff actually google facebook apple all these coding round questions they are also very simple you just have to understand what the pattern is okay which we'll cover later on make sure like subscribe let's move forward so let me just uh move this thing out of the way undo meh i i so weird i'm not able to see an undo on this how is that possible like there's no undo here control oh control z for what i was screen sharing and not using ipad natively okay i can make a new one no problem so a oops sorry eight one five seven sleep pointing to null head here we are not taking the tail because i want to give you some challenge if there was still there this would not be a problem okay so how do we do it how do we add a new element in the linked list so you want to add 18 or 7 19 or something first of all create that node create that box no problem made it now as a second step see how how it will look it will look something like this right it will look something like this now i'm gonna remove it try to do it now step by step now step three is actually like coding part so i only have head i need to reach to this last element okay so so i'm going to start from here my temporary last variable or whatever i am going to stop when the nodes where is the last element last element is the one whose next is equal to null isn't it pretty obvious so i'll be like hey the node you are at currently right now is the next element null it's gonna be like no it's not okay move forward is the next element null no it's not is the next element null no it's not is the next element null yes it is stop you are now at the last node now this is the way to do it if tail is not provided even in the previous lecture like in the previous concept of single linked list if tail is not provided this is how you do it because obviously in our rough diagram we saw that we need to work with this and this obviously then we need a reference pointer to this and how can we get that we cannot directly jump on to it since we have we would have to traverse this is the way to do it okay cool so what do we need to do next of this is going to be equal to null obviously so node dot next is going to be equal to what null okay then find last we can find last once we have the last or whatever i'm going to say last dot next is going to be equal to what current node like this so equal to current node one more thing is remaining this particular line so just draw it and see i'm not even thinking twice node.previous is equal to last okay anything else required no will this last be permanent no this will actually be removed this will also be removed like this pointer the last pointer node pointer they will be removed when the function is over because they are created inside the function scope will be our function is over this is like created in the class it will stay always it's actually a part of the structure of the linked list what watch object transforming playlist is there anything required else no just think about the edge case what if the link list is empty what will you do in that case if the head is null in that case what will we do okay if head is equal to null what do we do because then if we start last from here and we just check last dot next is equal to null it will give an error so before finding last we have to check whether head even exists or not so there's only one item then what do we need to do so if there's no items then what do we need to do this itself is going to be head isn't that true so i'm going to say this itself is going to be head head is equal to the new node and this node the previous of this node node.previous what is the previous of head when we talk about it in doubly linked list previous of head previous of head is what null that is it is there any difficulty over here is this anything different than what we have already covered in linked list no you will see the use cases and stuff when we actually do questions this is actually nothing okay let's try to okay so we need uh so now obviously this is obviously like very simple because you already covered it over here so zoom in a little bit and code exactly what is on the screen um i'm just going to say public void insert last into value that's it okay what is the first thing create a new box so i'm going to say node node is equal to new node value this box is created not connected to anyone start the last from the head pointer i'm going to say node last is equal to head and then i'm just going to say that while last dot next is not equal to null keep moving last forward so whilst when this particular loop will be empty last will be actually pointing to the last node okay but this last dot next will give an error if head was null okay so i can say that if head is equal to equal to null that is what are we doing node.previous is equal to null node.previous is equal to null and uh what head is equal to node we don't need to move forward so just return one more thing we are doing over here is we're saying node.next should be also equal to null irrespectively just put it over here node dot next is equal to null respectively okay something like that now you have your last pointer and all these are things what do you need to do uh last dot next is equal to node and what else node.previous is equal to last is there anything else required in this no list dot insert last 99 let's try to print this see what we get okay 99 is at the last and when we when we're printing in reverse it's at front okay pretty straightforward stuff cool um where is it at a particular index this one it's exactly going to be the same thing here we don't even require previous one because if you want to insert at a particular index you would have to reverse reverse from front or traverse from back no change will be required so insert will exactly be the same like this okay but some new thing we can do is let's say you want to insert a node after a node that the node that has been given to you how do you do that okay let's try to see it on whiteboard first as obviously okay so if an index is given to you the code will exactly be like this same stuff previous is not going to be utilized there or whatever uh let's say you're given a linked list um like eight doubly linked list two five seven uh null and null you wanna insert after five okay you wanna insert after five okay so think about let's say you want to insert 18 after five okay so first of all without even putting any thoughts or whatever obviously try to see what it will look like in the end so it will look like something like this obvious obviously okay this is what it will look like cool now let's see how to do it once you have seen what it looks like then it's not a problem you just follow what you see on the screen of the pen and paper thing that you have drawn so what do we do here again in english you have to think about which ones are you connecting you have to think about that right so we need the val we need the pointer to this and to this okay this is what we need okay [Music] this is what we need cool so we need five we can just create a get pointer you know the find one that we did in the previous lecture sorry in the same lecture previous video this one find find find this and make a similar one it will actually give me a pointer to this right like a reference variable to this so that you have this node okay this is let's say we call it the previous node or whatever okay any name we can give it again give it a node name p or something first step obviously is create a new box okay and what do we do after that we can say that this box dot next it's going to be equal to previous dot next okay so node dot next is equal to this p dot next okay no problem okay and i can say p dot next is going to be equal to this so p dot next is going to be equal to node i'm not even thinking i'm just doing things step by step from what the diagram we do before two more lines are remaining how do we add those this nodes let let's add this line the nodes previous will be equal to p okay uh only thing remaining now is this thing the previous of the of seven so how do we get seven p dot next will not give us seven because it is now pointing to node but node dot next will give us seven so i can say node dot next which will be seven don't think if you think over here you will get confused idea with linked list implementations is don't think why because everything is given on pen and paper it's more on the implementation part is there any is there any thought process required here no they're asking for some implementations we will do this where's the thought process and stuff required in like coding interview questions of linked list for that i'll teach you the patterns in the next video make sure actually subscribe okay so node.next which is seven dot previous means seven's previous should be equal to this node okay but what if okay now one one more thing we need to check is if anything is going to give us null pointer exception is node dot next going to give null pointer no node is something we have created is p dot next going to give null pointer no p is also something we have found p dot next will not give null pointer is node.previous going to give null pointer no node is something we have created is node.next.previous going to give null pointer exception yes it may because it may be possible that this is the it may be possible that this is the last element that you're trying to insert in that case node.next will be equal to null this may be null so here we need to add a check okay so always see the dot pointers you're making which possible pointer will give null obviously if 7 was not present over here it was directly something like this then 18 would point to null and it will give null pointer exception like null dot previous null pointer exception for on null you cannot apply dot or whatever okay um this is it yeah time complexity is what traversing like at worse you are traversing n times to find this p often okay let's code this okay um so public insert at a particular index not an index after a particular value after a particular value okay so you can see if you insert after 5 or whatever and i can say in value of the current node oh it's already defined insert after maybe oh sorry i i added it in the wrong file should add it in doubly linked list that's what we're doing doubly linked list okay sound good we need to find this p node so i can say node p is equal to find the p node actually copy paste copy paste this this should be doubly linked list sorry sorry no dot val okay we have to copy paste with caution okay uh finding the node p okay no problem uh but what if this node does not exist no problem okay create a new box okay created a new box and now what node.next is equal to previous dot next okay already explained this node.next is equal to previous dot next which is p dot next actually okay and p dot next is then equal to the node i have just created p dot next is equal to node i have just created and after that node.previous is equal to p node dot previous is equal to p and this may cause null pointer so i can say node dot next dot previous is equal to the node i have just created but this may be null so i have to make a check over here if this is not equal to null then only do this okay um let's try to do it let's say list insert after or insert after 17 or 8 or whatever i need to insert 65 so after 8 it should insert 65. okay works normal order reverse order after it 65 is added if you say after 99 then it will add at the last index no problem works uh works completely fine okay that's simple uh deletion and everything is also pretty similar so i believe you can do it right it's actually exactly the same because you just only have to traverse like in forward and stuff it's no problem over here cool that was doubly linked list so you can see every single thing is just basic basic concept main problems will come when we do interview level questions but the implementation part the most simple thing in linked list okay now let's do something else known as a circular linked list a linked list in a chain okay let's learn about circular linked list it's very simple it's um it's it's just as the name suggests it's like it goes in circle okay so a single node you will have something like this let's say you can say surf color link list eight okay it will have a next well pointing to nine i have a next pointing to two this will have a next pointing to seven this will be pointing to head something like that so every single node has what class node has a has an integer value and it has a node next so node structure will not change it's similar to the one we had in single linked list so no confusion here okay no problem cool okay now one thing that i would like to share is here it's not null here things are not null okay so here's like it no one is pointing to null until unless the ellipse list is empty so let's say this is head for example this is tail and let me say i'll teach you about display and insertion and deletion okay so let's first look into insertion if i insert a value so obviously how would it look like let's say you want to insert a value after the tail how would that look like first of all it will look like something like this 17 like this and move tail over here that is what it will look like now code it okay so how do we do it how do we insert we have the tail pointer for example so we can create a new node first you can say 17 okay created a new node i can say tail dot next is equal to the new node that i have just created no thinking required new dot not next is equal to what head something like this okay cool tail is going to be equal to what node that's it cool what if the head and tail are null which they are in the case where no item is in the linked list so for that if head is equal to equal to null in that case what will you do head and tail are going to be both pointing to the same node that's it head is equal to node tail is equal to node this will look something like this this is head and tail itself that's it this is itself a circular linked list like this okay cool let's uh let's code this so here i can say circular linked list okay i can say private class node has an int value node next and i can create a constructor for my value okay cool and i can say oops private node head and private node tail no problem no problem at all okay let's create a constructor for this circular linked list constructor initially let's say we're not passing anything obviously so we're just going to say both are null at first if you want to do that public void insert the value create a new node first all right and after this what do we have if head is null so if head is equal to equal to null i can say head is equal to node head is sorry tail is also equal to node and just return right then here i can say tail dot next is equal to node l dot next is equal to node and node.next is equal to head node.next is equal to head and tail is equal to node tail is equal to node no problem that's it cool what if you want to display so i'm going to say public void display how do we do it so we're going to start from head okay while again node is not equal to head remember so we have to print this at least once and we'll keep on going till we don't reach this again which particular loop is there that exists at least once do while loop we learnt about it in the previous lectures when we are doing very basic stuff okay so i can say node node is going to start from head then i can say if head is not equal to null do this thing i'm going to say print the value of head by sorry not ahead the value of the node that you're currently at plus a circle like this node is equal to node dot next okay while do this how many times while node is again not equal to head but since it's going in circles it will at once reach over here you can also print from head till tail it's also pretty pretty stand for straight forward while node is not equal to tail keep printing it but then you have to add one more condition like you have to print 17 as well it's like hey node is equal to tail skip it and you have to print this again this looks much more cleaner let's try to try to do it circular linked list list is equal to new circular linked list list dot insert um what 23 i'm just gonna copy copy this thing four twenty three three 19 75 or something and you can see list dot display obviously i can't print circle in a command line so you can see what it will give 23 3 19 75 next again it will be 23 okay cool again it comes at head like this is the complexity for printing this is often because um printing in times n numbers and nodes basically all right that looks good um cool hmm that is it very simple w link uh circular linked list let's try to see if you want to delete something so i can say um public void delete particular value how do we do this thing how do we delete so we're going to start searching from head you're going to be like hey if you want to delete let's say nine okay so let's say you're gonna be like hey uh is this equal to nine it's gonna be like um no it's not then it's gonna be like okay let's move forward so we're gonna check for the next node try to do it in like a little bit more detail okay so let's see how we can delete something um how do we delete something eight nine one five head tail um let's say you wanna delete nine obviously i'm going to start from head so you're going to be like hey if head is equal to null first of all you just you know say return um but if this is the value to delete let's say you want to delete the value 8 so if this itself is the value to delete then what do you want to do what should it look like it should look something like this isn't that what it should look like okay let's see how to do it then you can say head is going to be equal to like this head dot next okay head is equal to head dot next and tail dot next is equal to head like this so even though this thing is pointing to it it does not really make like it you cannot ever reach it you cannot ever reach it like this so this linkage actually does not matter even though it presents so that looks good right okay that's it but what if it's it's not let's say you want to delete nine for example so if you want to delete nine or one for example let's say you want to delete one okay so if you want to delete one then what do we do what do we do i'm going to take a you're going to see where you are like lying so let's say if you're over here with node okay if you're over here this is your node the one that you're using to point out or whatever okay traverse basically so you're going to say this is let's say the next node okay this is let's say the next node which is just node.next then you just gotta check hey is this next node equal to the value that i want to delete it's gonna be like uh no it's not okay then uh then just move forward does that make sense it's just gonna move forward node over here now it's going to check the next value again but since i've already checked this i'm going to check the next value which is node.next over here so hey is this the value to delete it's going to be like um yeah it is then how would it work it's basically going to say node.next is equal to n dot next make sense it and you will keep checking this until unless you find something like this or you are back at head okay if your back at head it means that value does not exist that you want to delete how easy is this it's pretty straightforward because you are working with these two things like two pointers obviously you need two reference variables that's it complexity of n where o n is the um total number of nodes because that's in the worst case it will traverse all the nodes okay so let's try to code this uh where's my white board i'm going to start from this eight like head so i'm going to say node node is equal to head and i'm going to say if node is equal to equal to null just return don't need to do anything and then you're just going to say if this current one that i have if no dot value is the one that i need to delete is equal to the one that you need to delete in that case what are we going to do so if this was the one you need to delete then i'll just say tail dot next is equal to first of all head is going to shift forward tail will move to head already covered this head is going to move forward tail dot next will now be equal to head return okay otherwise what do we need to do we need to check the next item if the next item is the one then i just skip it and the current items will point to this for example here the next item is what we want to skip hence this node will actually skip it and actually point to this current n items next pretty straight forward no need to think over here just try to see there may be different ways to solve this problem you should experiment definitely with that okay so what are we gonna do do this thing do this thing what is this thing node n is equal to my current node dot next and i'm going to say a if uh n dot value is equal to equal to the one that i need to delete in that case what am i gonna do i'm gonna say this is the one i need to delete then node.next is actually going to be equal to n dot next node dot next is going to be equal to n dot next and i'm just going to say not return since it's a while loop so break do value otherwise just keep moving forward node is equal to node dot next you will keep doing this while your node is not equal to head till you circle back that's it let's try to see uh if we can delete something so i can say list dot delete 19 from it let's try to print it okay so here you can see 19 has been removed okay you can even print it before removing 19 so you can see before after stuff before after cool that was it about like the implementations this lecture was extremely important to understand the internal working and the thought process now after this lecture we are going to do tons of questions questions will be divided into two videos the first video will be um level one questions and the second video will be uh fang interview questions the ones that are actually asked in like google and facebook and amazon and microsoft and all these other big tech companies so we'll actually teach you the thought process link list is asked quite a lot and i will not just teach you how to solve the problem i'll actually teach you what sort of patterns and theories and tricks and tips and tricks should be applied so when you're given a linked list question you'll be like okana asked us to do this kunal asked us to take two pointers one flask and one slow kunal asked us to reverse a linked list kunal asked us to merge these two linked lists okay all these other things so and one more important thing that is asked quite a lot of times in interviews with linked list is recursion people often fear it like using recursion on a linked list like uh sorting a linked list using recursion like bubble sort merge sort or whatever cool we'll cover that as well so these three videos i think will uh i'll make now after this so um recursion link list link list level one questions and link list advanced interview level questions so that you can clear any interview of linked list just like the one i did for bind research video so make sure like share comment and subscribe and i'll see in the next one [Music]

Channel: Kunal Kushwaha

Views: 282,538

Keywords: linked list playlist java, linked list playlist, linked list interview questions java, linked list insertion at position, linked list in data structure, linked list in java, linked list in python, linked list implementation in java, linked list cycle, Introduction to Linked List in Data Structures (With Notes), Introduction to Linked List, linked list traversal, circular linked list, doubly linked list, linked list tutorial, linked list code, pointers in linked list, leetcode

Id: 58YbpRDc4yw

Length: 115min 57sec (6957 seconds)

Published: Tue Nov 16 2021