WHAT IS LINKED LIST? | Linked List Data Structures | DSA Course | GeeksforGeeks

Key Takeaways

hello everyone in this video we are going to be discussing about one of the very fundamental linear data structure Ling list so let's see what actually are ling lists so if we just read out this definition here it says a ling list is a linear data structure in which the elements are not stored at continuous memory location okay the elements in a link list are linked using pointers as shown in this diagram so I don't know what might you have concluded with this definition but this is basically comparing it to arrays and this video actually requires that you should already know what arrays are well in contrast to arrays as as we are going to see further don't worry what happens with arrays is the the every element inside an array is actually stored uh in continuous memory locations right that is that is one after the other in the memory right so first of all just observe this Ling list data structure try to you know like uh figure out some things that these boxes are there I'll give the name to it these boxes are called as nodes the first box is actually called head and then you have all of these series of boxes and if you notice carefully the last node the last node has this second part which is actually pointing towards one thing called as null right very high level observation of this diagram nothing else let's let's just you know like uh visit back to the arrays a little so if I'm saying that this is a memory just assume that this is your memory computer memory and an AR are stored right now as you can see every element is continuous so uh if I just give up give addresses here and considering that my characters are um like only taking one bite to uh to get it stored here well the let's say the first first one is standing at 0x01 right the second uh element would be standing at 0x 02 and the next one at 0x 03 and further on like this so if you see carefully what is happening here just like inside the memory if elements are kept one after the other that is called conation being kept in continuous way now actually in Ling List It differs a lot Ling list is somewhat like this you're going to have an element then it is going to be let's say it is stored at 0x 01 again B would be stored anywhere in the memory like anywhere in the memory scope that you are given so it could be 0x 09 or it could be the C next element could be 0x uh 0147 anything right the addresses are not in your control at what position you are going to put it uh it is not in your control anytime in Ling list every node is kept at VAR like different locations in the memory and those are actually connected together connected with links so that when we are standing at the first node we know where the second node is kept when we are standing on the second node we know where the third node is kept and this goes on till we reach the last node and you might uh remember the first diagram that I showed you this one the last one actually knows that it is last and how does it know that this like particular node is last because in the in the second like this field of this node one null is connected nuu okay this means that there is nothing further this was the last like this was the end of the Ling list coming back to this diagram I hope now you know how actually Ling list at high level looks like and you are clear with that uh Ling list is something composed of nodes conect connected with links correct uh okay coming back to this diagram just as you can like see this G is the last node that means its next should be pointing at null now let's come to what is a node we have been saying nodes what actually is a node well node basically has two parts the first part is there to store the actual data that we want to store so assume we have one array one integer array precisely so I was storing elements in that right uh integer elements in that so the note that I'm making could be of this type as well it could be designed for storing integer data it could be designed for storing character data or even strings or different uh structures that we want to make any sort of data that we want to store should be in this block of our node the data uh area of a block one thing that is compulsory is this next why it is compulsory because next is the field which actually maintains the reference to the next node wheresoever it is kept in the memory okay so the whole existent of uh existence of Link list is because of the links that it has and that is stored where at the next of every node right now let's see ways in which we can create our own nodes okay so firstly we can create our node using a structure uh in C C++ or in general we can use classes to create up our notes so if I go with the structure uh we actually specify the data field first so I can say int data whatsoever we want to store here uh if that is of integer type I'm going to say in data or I can use any other data type here whatsoever I want to store in my note okay now the next pointer now this is for you to tell me what is going to be the type of this next pointer we are clear with it that it is a pointer if we talk in terms of of C or C++ or in general we call this as reference that means reference to some other node right but uh if you're talking about C or C++ you must tell me that what should be the data type of this next let me give you a hint when whenever we had an integer like this int a and we wanted to use a pointer to it we used integer pointer right we we used to write it like this end pointer p so that we can say p equals % of a right that means p is storing the address where a uh where a is actually located now if we have to uh replicate the scenario here what are we actually doing I'm making up this structure I'm making up a node structure so I must say struct node right I'm making up this structure and I want to have a pointer which will be which will be actually pointing to this same structure like uh not this particular same but similar sort of structures right so that so what I'm going to write here is I'm going to I'm going to say node pointer next because this is now now the term is term for this thing is self referential structure now this structure has become self- referential structure we have seen how we can make this uh node using a structure but actually like in in Practical implementation you move most of the time You' be using class to implement the same thing and we'll be seeing further how we can use classes in python as well to create up our nodes okay and in general whether you are using any of the language Java C++ or python you will be using classes for implementing uh Ling lists let's now first see the other topic connecting nodes now you know what nodes are now we should we must know that how we can create a ling list out of this note out of these nodes so assume we have these two nodes A and B and I have made them as object of this class node I have said a equals node the name of the class and the data that I want to pass in let's say I said 10 so what will this line do what will this line do well this is actually specifically syntax of python but what I'm doing here is I'm creating an object of a class okay now what is happening here is I am creating one node let's say this node is created and the data field actually is 10 initially when we have not put anything in the reference it would be none or none then I've done the same thing I've said b equals node let's say this time I said five this node will be created and five will be kept in the data field and the next field will be empty but still it doesn't look like a lingl structure does it the lingl structure is actually like this which is composed by making up links this is the lingis structure so how we can connect these two nodes well for making a connection from uh here to here we need to actually say a do next that means I'm talking about a is next field and I need to fill some value in it okay only then this value will uh this space will be storing something and what should I what should it stored where B is and it will be done like this so once I write this line aext equals P that means I am actually making up this connection and if you want to understand what is happening here like even in depth then again you must take help of pointers see I am keeping it uh I'm keeping the syntax in Python so that it can be very simple for you to create a link list and start working on that but remember whenever you are working on the concept of Link list you must actually understand it with pointers as well so just just to you know know just so you know that this is how the links are formed but what is happening internally well you have this block a you have this Block B A does have some address let's say I said it is 0x 101 B also has one address it is 0x let's say 705 both of the nodes have next uh next Fields now I have to make this connection I have to make this connection how it how is it actually happening I am actually just putting up this address I'm putting up this address at A's next field so it is something like A's next equals address of B same thing written in two different languages this is to simplify stuff for you and this is to make you understand how actually addresses are working inside so this will be kept here so at this point it'll be actually 0 x705 so complete a node would be looking like this so whenever we say a is next we actually are referring to B whenever we say a is next we actually are referring to B now once I that I've said that once I've have said that so you must tell me what is a do next. data okay a do next. data if I print this value what will be printed now see if you have said five then you correct because I just now told you what is A's next A's next is 0 x705 so once A's next is actually B itself that means we are saying B do data so saying a. next. data is actually equivalent to saying b. data because a do next is nothing but B itself right so now I hope now you know how you can connect nodes right let's see how we can can compose a link list with it so you might remember that in our initial diagram there was one thing called as head right and head was actually pointing to one node and that node was having connection to the other ones and eventually in the final node it was having connection to null right that means that is the last node it is the ending node one point to notice here well none of of these nodes are actually being denoted by variables just like we did a b c and d you cannot individually say a equals something b equals something c equal something or D equal something and then connect each and every node with it because that will be too much manual work for us you don't have to do that we have to automate that some way right for that we build up some logic and that is actually Ling Ling Lista use for so to use their Dynamic nature we can extend Ling list as much as we want at least ically so now I will tell you how we going to create a ping list first of all head is crucial you must understand that just to even begin with Ling list we must know where head is okay the whole existence of of a ling list is because of head we know that there is a ling list once we have its head right so what we'll do first of all we'll make one head I'll say head equals node and I'll give some value to it let's say I have given 10 now this was the only manual work that we had to do now the next thing we'll be automating using Loops so that it can be kept on building to how many nodes that we want I'm emphasizing a lot on head and head shouldn't be moved right so you do not have to keep on moving your head but at least you need some value which you can uh denote your node with right so for that what I'll do is I'll just give a temporary name to it to head only I will also Al attach one more just like one more reference a pointer so that I can reference that node I can actually you know use that node so I'll say temp equals head now I can move my temp but I cannot move my head because head is going to be there at its position what I'll do is so how how so many nodes I want what I'll do I have my head here after writing this line right then this H is here and also this temp is here right both the things pointing to same thing same node now what I'll do I will create up a new node okay and what I what will I say let's say I'm saying it is uh it is new n n w n new node equals I'm creating one more node node and I'm giving it some value let's say I'll input it from user okay so I have created one new node and it name is new n the situation is with you how would you connect these two nodes you have seen it already right we can simply do temp. next equal new n right so what will happen this link will be there now I will do one thing I will move my temp how can I do that I can simply say temp equals temp. nextt do next and this is a very useful line this actually helps you to move in the forward Direction in Ling list okay you can say temp equals temp. that means now you're pointing now your temp is pointing to the next one and if you execute this line again that will again jump to the next note and it'll keep on going until the last one so what what what is happening here I have built this connection and then I have moved my temp from here to here now these three lines can be kept in any Loop for or while up to you and you can execute that as many times as you want as many noes as you want so in another iteration to what will happen again a new no will be created you know where temp is this temp. next equal new uh new n will be there this again this connection will be made and temp will be moved to this node if you're going to execute it once more then again a new node will be created and then again this connection temp. next equal new node will be done like this because the name is new and here new and here and then temp equal temp. next that means temp will be moved here right and this will keep on happening until we get out of this Loop this is how we actually create a link list so I hope now you are clearly able to understand what Ling lists are uh how it actually is working from inside how it is created and you very well uh you are very well aware of how nodes are created and being linked to each other right so your fundamentals are getting clear now uh so I'd be wrapping up this video here we are going to be having another video in this series and in that we'll be practicing Ling list handson and we'll be practicing a few questions in that thanks for watching the video and if you liked it do comment down below thanks