Hello and welcome back.
So in this video let us continue our discussion about data structures.
And now let's learn about Linked List.
So let's get started.
Now linked list is actually a linear data structure.
Structure just like arrays or list right.
What does that effectively mean is that wherever we are using arrays or list we can actually use linked
list as well.
So now before we move forward and I explain you what exactly linked list are, let us first see what
the problem is in arrays.
Right.
Because of which we have to, uh, like come up with a new data structure that is linked list.
So if you remember right, the very basic array definition, the one which we discussed in the initial
module and the one which is there in Java or C plus plus, whenever we define an array, it asks us
for a size as well.
Right.
So it asks us for a size.
And let us say that size can be three.
Now, once you do this, what effectively happens is that in the memory, a space for three elements
will be created, right?
We have already seen this particular working.
We have of course also used the same for creating our own dynamic list as well.
Right.
So the one question which we did where we created a dynamic list.
Now it's all fine and good till you want to just add three elements.
The problem occurs when you want to add more than three elements.
Right.
Because this particular space right.
This particular space, this might not be mine.
This might not be free.
Not be free.
Now what used to happen because of this is that if let's say you need to add another element, then
of course we will have to create a completely new array with greater capacity.
Okay.
And then make sure that we copy all the elements there.
Right.
The very similar thing actually happens inside a list which we have already seen to define an array
in Python okay.
The numpy arrays, which is normally taught as a part of data science stack that is also on the similar
principle.
Right.
So if you that is also a fixed size.
Okay.
So you cannot add any more elements in that the size which has been already been uh assigned.
Now if that problem will persist, if let us say you create an array of ten elements tomorrow, then
maybe it can happen that I can create.
I can add 11 elements for 20.
Again, I can add 25 elements.
So that's not going to cut it right.
If we just make sure that we are increasing the size based on the increased capacity, that is going
to be a problem.
The second thing which many of you might be thinking which we can do is something like this.
So let's say I create an array and this time I'm creating it for 10,000 size okay.
So no worries.
You can store as many elements as you like if you are not using it.
All good right?
But there is also one more problem.
And that problem is that let us say you have created a very big array okay.
Now what if I am not using the space which you have given me, I'm just using maybe let's say the first
three elements.
Again, I thought that, okay, I might be using 50 or 100 at least, but I'm not using it.
Right.
So all this space here is actually just getting wasted, right?
All this is a wasted space.
So these are the two major challenges with your array or these list kind of data structures.
So we have already seen about them.
So the first one is insert and the second one is memory wastage right.
Now if you try to understand the basic problem due to which this occurs is that in array your elements
are stored continuously.
Right.
So we know that in array elements are continuously stored.
And the same of course the understanding will be exactly the same for list as well.
Okay.
Continuously stored.
So because of this, this problem is happening.
And linked list is actually now created to tackle this particular problem only.
Okay so linked list help us to tackle this particular problem.
The way linked lists do that is to by making sure that we can add elements add elements.
As per our requirement.
Okay.
So we are not going to make any continuous space.
We are not going to save any space or something based on our requirement.
We are just going to add our elements in the memory.
Okay then any requirements?
Basic idea of linked list right?
Now if that is clear let us see that.
How linked list does that?
What exactly happens is let us say if you say that you want to add an element okay, what I'm going
to do is I'm going to create an element in the memory.
Right now you say that hey I want to add another element.
Okay, since I am not stored or saved any space, what I'm going to do here is I'm just going to add
another element, but that will not be contiguous.
It will be stored somewhere else in the memory.
Okay, great.
If you want to add two more, the third element can do that will be randomly allocated, not one after
the other.
Okay.
Similarly for fourth element as well right.
Just one thing to note that all of them are randomly.
Allocated space in memory.
Okay so random allocation happen.
They are not one after the other.
Now the next big problem, which all of you might be able to think in this particular approach, is
that how would I know that?
Okay, where my second element is, where my third element is, it's fine that linked lists have created
them as per my requirement.
It's a good thing that yes, now memory is not getting waste, but how will I access them?
Right?
How do I know that?
Where is my second element?
Where is my third element?
So maybe the one of the approach for that is maybe we can create a array or list to store our addresses.
Okay.
To store addresses.
Now this of course is a very bad way to handle this.
The reason is that we were running away from array and list.
Okay.
But unfortunately, we have finally gone full circle and just encountered them again.
Right?
So this is not something which we should do because again, the same problem is going to occur, right?
You are going to take an array or list.
The second you add more things into that, it's going to create a new copy of itself or something.
Uh, if you are just keeping very small elements, okay, small number of elements, then of course
a lot of memory will get waste.
Okay.
So with respect to that, with respect to that, what happens is that second approach which I can do
is ask my elements.
To store.
The address of.
Element after it.
So here effectively what I am doing is I am asking my element that hey, can you store the address of
next element which is after you.
Okay.
Then the second one I will ask, hey, can you store the address of third element which is after you?
So in this way I am just asking my these elements that along with the data which you have, please make
sure that you are also storing the address.
Now many of you might be thinking that how will that be possible?
The idea might be seeming a little bit vague.
So let me give you an intuitive example through which it will be clear.
Let's assume that, say we are in a class, okay.
And the class has gone to picnic.
Okay.
A new teacher comes in and he has having no idea.
Okay.
He is having no idea that who all students are.
And again, there are number of children who are playing of the same class.
Okay.
Let's say this is your class.
Now, you being the first person, what you say is that.
Hey, I can help you.
Like you just remember me, okay?
And I remember who comes after me.
Okay.
So what you can do is you say that, hey, I am.
You can just remember me.
I am the first one.
I know who comes after me, okay?
This person will have an idea that.
Okay, I will ask this person to remember who comes after this person.
This person will remember who comes after this and the last person he will just remember nothing, okay?
Now, if you do this thing, if you do this thing, don't you feel that now you can actually go to each
and every student as well?
So let's say if you want to go to the third student, what you can do is you start with the first one,
then you go to the second, then you go to the third.
Right.
One more advantage of this is that tomorrow let's say if you want to add another student, maybe let's
say it's from another class, right?
What you can do is you can just add him to the end.
So you can just ask your last student that, hey, can you please remember this orange person who is
from other class?
He is going to be after you, right?
So in this way, in this way, what happens is that you can add or remove student based on your convenience.
They are all randomly allocated so they are not continuous like they are playing in this big round.
So you don't have to worry.
You can still get all the students as long as you remember the first one.
Okay, so this first one is actually known as head.
And if you will see the way these students are now linked to each other.
Right.
That's the whole idea behind Linked List as well.
And that is why they are known as linked list.
So let me just draw and explain you how it will happen in your overall linked list.
So the very first thing to notice this is my bad.
Yeah this is going to be your each element okay.
So your each element will look something like this.
It will have two things.
The first is going to be the data which you want to store in it.
The second is going to be the address of next.
So in computer terms address is the thing right.
Which we have to remember for the next element.
Now if that's the case what we can do is we can create a single element.
Okay.
Divide it, have it, ask it to have two properties.
And now let's say if I add four elements here, let's say if I'm adding four elements here all I have
to do is say again yeah.
So let's say these are the four elements.
Now all I have to do is I have to ask my first element to, hey, can you please remember this element.
And he will be good to remember this.
I have to ask my second.
Hey, can you remember the third one?
He will be good to remember.
This.
Third one can again easily remember the fourth one.
And this one can just remember that no one is after this.
So it is none, right?
And I myself can just remember that this is the head pointer or the first pointer.
Now you will see that all these elements are linked together with each other.
That is why again the name is linked list.
And using any of them like using sorry using the head one.
Okay.
If you just remember the head you can actually go to any of these elements, right?
You can ask head, hey, can you tell me who is next after you and you will reach him.
Then again, you can just reach to the second or third one and fourth one.
Now the good part.
You can actually add even thousand of elements.
No space is getting saved.
So as per your requirement, you can keep on adding or even removing the elements which are as you wish.
Right.
So that's the overall benefit, which was the shortcoming in my infrastructure.
I am able to actually counter that just by making sure that I am remembering one, and I am able to
link my all the elements.
So even if they are not contiguous, I know that there is a sequence to them, right?
There is a sequence to them and that is why they are still linear in nature, just that they are not
stored in a continuous format.
Okay, cool everyone.
So I hope with this overall video you have gotten a great idea on what linked lists are.
Please make sure that you also remember this intuitive example of students.
I am going to use that in solving lots of questions as well.
In the next video we are going to go and implement our own this particular linked list and see that
how they are connected.
Okay.
Thank you.