Hello all and welcome back.
So in this video let us continue our discussion on linked list.
And now let us try to implement our own linked list as well.
So let's get started.
Now if you remember in the last class we saw that how each element of my linked list will be having
two things.
The first one was the data.
What exactly is the data of that particular element?
And the second one was the address of next element in line.
Right now this particular structure right.
This structure where we say that it is having a data and the address, it is known by a name called
node.
So what I effectively say is that my linked list is a collection of nodes where each node, each and
every node is having some data and address of the next element or next node in that particular structure.
Now, if you actually remember, we have not studied any data type where we have a structure like this.
Right.
So where we can say that.
Okay.
Hey, one data is there and an address is there.
So no data types.
As such.
We have shredded which is inbuilt in Python or throughout the course.
As of now we have not done that right.
But we have learned about oops or classes.
And one very common name of classes used to be user defined data type.
User defined data type.
Now, if you are not remembering what exactly classes were or concept of oops were, will highly suggest
to see the class after this video once to revise the same because we are going to use that a lot going
forward.
Okay, cool.
Now what I can do now is using this knowledge.
Equipped with this knowledge, I can create my own class, my own data type, which I can say that will
be node okay.
And like this will be the most fundamental unit of my linked list In this note, I can say that hey,
you are going to have one data.
And of course constructor will be there.
So we can say that init.
Okay.
And you are going to have a next.
So I am saying the address as next.
Now initially we can of course ask that hey what value you want to use.
So maybe we can have some value through which we use to save.
So value for the next.
I can say that initially my next is none.
Now why exactly is this?
None?
Let us understand.
See.
So this is my node, right?
This is one node which I will be creating.
Whatever value I pass you are going to say that your value is going to get stored here.
Okay.
Let's say I pass one now.
As of now this node is not pointing to any other node.
Right?
We will have to still make that connection first.
Your node will get created somewhere in the memory.
Okay.
It will be having some address.
Let's say zero x ten is the address.
Okay, so now what I will be doing is I have to still connect it.
But as of now there is nothing.
There is nothing.
This node is remembering as the address of next node.
So that's why I say that this is null.
Okay.
So that's the most basic structure because of which we can through which we can create a node.
Now let's move and actually implement the same in our code as well.
But just one more thing.
Before we move forward, I want to showcase you some examples through which you can better understand
and always remember what linked list are.
The very first one is that of a playlist.
So we all must have used YouTube playlist or Spotify, right?
In that we can actually create a playlist.
Now if you understand there used to be the next button in that and what this next button signifies,
it is taking you to the next song.
Right?
So don't you think the structure is something like this only again, the node structure where this is
the structure, this is a song and this is pointing to the next song.
Now there is no requirement that all the songs should be kept one after the other in a continuous place.
For example, this flower song by Miley Cyrus.
Maybe it is kept somewhere else.
And this kill Bill song is maybe kept somewhere else in the memory.
But again, using the same mindset of linked list, I can actually create the structure right where
you can ask or help your user to create a playlist.
You just have to make sure that each and every song which gets added, you are maintaining your playlist
structure.
Great.
Second, a very relatable example is Treasure Hunt.
So in Treasure Hunt, what we do is we start with some particular position and we just know the clue
to the next position.
And normally it is said that hey, when you will go to the next position, the using your clue there
you will get where next you have to do.
All right, so this is exactly how your treasure hunt gets played right.
So you have the first index or sorry first clue.
It is having the information about next clue.
Let me draw this only.
So this is your first clue.
Let's say this is having all the information about your next clue.
So this is having the next clue information.
Now your next clue can be, let's say somewhere here.
Okay.
This will be joined in this way, right?
Somewhere like this.
This will be joined and then keep on like using the same principle.
Now what you can do is you can reach out to the finish line or the last overall node in your in your
treasure hunt.
Right.
So that's another example.
The last example is the browsing history.
So in browsing history if you see we go forward and we can go backward.
So using some special linked list which we are going to cover later in this module.
We can actually implement the browsing history feature as well where we remember that okay, what was
the last page you visited and what is the forward page?
Let's say you visited which you have just came back.
So again this is all required so that you understand that yes, it might seem a lot trivial initially,
but they are used in lots of places.
So tomorrow, if you are making any particular, say, this treasure hunt game in your software or something.
Linked list is something which you can fall back to.
Okay cool then everyone, I hope these intuitive examples are clear.
So now let us go and code our own linked list.
Okay, great.
So the very first thing we have to create a class.
So let me just write create a node of L.
So we are going to create a class.
And I want to say that it is a node class.
Right now in this I have to first create a constructor.
The constructor has self and I am saying that I will get a value.
Now, if any one of you is having problem in remembering that this particular structure, please make
sure that you see the class after this video because you are going to use this a lot going forward.
Now here I have just created a node class okay.
This is having a self okay.
And in this constructor it is having a value.
Now what I can say is in my data in my data please put the value and please make one next as well which
is none initially right.
So this is how we create a class.
Now when this class will be invoked, the data will be having the value which you provide.
And the next okay will be having none.
So let me show you that as well.
So let us create a first node.
First is equals to node of one.
Right now if I will run this again nothing is going to happen here.
But what I can do you or what I can help you to do is visualize this particular thing.
So pay attention.
Yeah.
See, when I create this node class it gets created.
So in the global frame we have this node class.
It is having a constructor.
When I call this first what is going to happen is that this first will call this constructor right.
This constructor gets called in the self dot data.
I am passing the value as one.
So it is going to use that value and one node instance is going to get created.
Again this is all just basic classes stuff, but I want to make sure that you are able to understand
very much properly on what exactly goes behind the scene in a linked list.
So a node instance is going to get created with data is equals to one.
And because we are saying the next is going to be none, next is none here.
Right.
So this exactly is your node.
Now first data one next node.
You can see that how it is very analogous to something which we were drawing right.
Okay.
Now moving forward I can again create a second node.
and I can create a third node as well.
Nice.
So as of now, these nodes are not connected to each other.
As of now, just the random allocation in the memory have been done where each and every of these nodes,
right.
Each and every of these nodes, they are just created.
Each and every one is having some data and the next is exactly none.
So something like this will be created in the memory.
Now to connect them, to connect them.
What I can do is if you remember we used to have an ID function, right.
So this ID function used to return us a unique identity of an object.
Okay.
So this is something actually which kind of we can use to say that hey can you please remember first
can you please remember the ID of second?
Okay.
So what we can do is pay attention first.
Now let me first show you the IDs.
Print ID of first ID of second.
And ID of third.
Right.
Let me run this particular thing and you will see that we are getting some IDs.
Right.
Now, what I have to do is if I say that first dot next is equals to second.
Okay, then this is something which I am doing where I am creating the linkage.
So at this point all I'm doing is I am just saying that I have this first created in the memory, I
have this first created in the memory, and I have this second as well in the memory.
Right?
I have this second as well in the memory.
All I have done here is just created this linkage.
So I have asked my first that hey, in your next please keep second.
How can we see that?
Just let me print the first dot.
Next.
Okay, so let us run this.
We are seeing this particular address right?
We are seeing this particular address.
Maybe I can copy this.
I can copy this.
And just remember.
Let me copy these as well.
Because in the next run this is going to get changed.
See.
So these were the output I am getting now.
This is the address right.
If I just try to print ID of this we will see that sorry not id int.
So this is the hexadecimal representation.
And I will also be drawing the address like this zero x ten zero x 20.
To showcase we can actually see that okay this will be equal to this particular address because we saw
that how in first dot.
Next we kept second right.
So I have just saved this because in the next one they will again get randomly allocated.
So let me just do one thing.
Let me just as of now, for the time being, just comment everything and not just show you right.
See this is coming out to be 43739344.
See three for four.
So what does that effectively means is that in my first.next I am storing the ID of my second.
Okay.
Again, this is very important to understand as well that how you're storing the ID that is the unique
identifier right.
So let me uncomment everything.
Now the problem is if I will run this again.
So let me just remove this because these addresses are going to be changed.
Right.
If I run this again see now there are some different addresses.
But anyways let me just remove this.
I hope you understand this perfectly everyone that how what exactly is happening here?
Now in a similar manner, what I can do is I can see that.
Hey, second, can you just remember what third is?
And now I can create my head and say that okay, head is equals to first.
Okay.
This will actually have created a linked list in the back end to understand and show you the same.
Let me just run this whole in Python tutor again.
So pay attention everyone.
Now you will be able to understand exactly so how the things are happening.
See, first we have created a node class node.
It's going to create a global in the global frame.
It's going to create a node class.
Now moving forward we are creating the first node okay.
First node is going to have a value which is one and address the next which is none.
So next is none data one.
Let's go forward.
Similarly second and third can be created.
So you will see the second and the third now getting created right see first, second and third.
Now I'm just printing their IDs.
Should be fine.
We can see their IDs okay.
They are little.
They are of course different here.
Okay.
Good.
Now when I say first dot next is equal to second you will see how this particular node will keep will.
Now point here.
See.
So this none this is now pointing here.
Similarly when I say second dot next is equal to third we will see how it is pointing here.
And finally, I can create a head.
Finally, I can create a head.
Right?
So it's a little bit tangled as of now.
But let me show you.
The head is kind of pointing here.
And from this I can access my whole list to make it a little bit more clear.
Let me just write one more line.
That's going to make it all a lot more clear.
So actually now we can delete my first, delete my second and delete my third.
Again this is some delete operation which we have already seen as well.
The second I run this and let's say if I just go to the end see first, second and third are getting
deleted.
And finally we have a linked list kind of a structure, the one which I showed you right.
So I hope this is very much helpful in visualizing.
Again, if you're able to visualize linked list, 90% of the work is done.
Okay.
So see this is my head.
This is my head.
Let me just zoom in as well.
This is my overall head, everyone.
Now, in this head.
In this particular head, what?
All I am having.
Here is pointing to the first node.
Okay.
This first node is pointing to the second node.
See that where the pointer is ending it is pointing to the second node.
And second node is finally pointing to the third node.
Third node saying that hey, I am not pointing anywhere.
Now if we actually want if we want in this particular thing, what we can do is let me showcase that
to you as well.
We can do one more thing, right.
So see if I do print first dot next.
Now when I do first dot next I am on second dot data.
Okay.
So what I'm doing is I am saying hey first dot next.
So I am pointing here now dot data.
If I run this whole code, if I just run this full code, you will see how I will get two.
I'm getting two here and I hope you are able to make sense of it.
Right?
Because I went to first ask it for it.
Next using it next.
Next I attempted to just get the data.
The same thing is of course a lot.
Expandable.
First dot next dot next.
And if I run this, I hope all of you are able to understand what the answer is going to be.
It's going to be three because I went to first, next and then next of this particular as well.
So I went to three.
And now I ask what your data is.
So in a way you will be able to see that just by using first.
And I can of course make it head as well because first and head are the same thing.
And if I run this it's same.
So just using head I am able to access each and every of my node.
Right.
So I hope now the whole flow is a lot clearer.
So see, I'm able to access each and every of my node one, two, three.
So I just created this head and I can access all my elements using this.
Again we can add keep on adding any elements we want.
We can delete elements as we want as well.
Okay cool.
Then everyone I hope with this overall implementation you have a good idea on what exactly how exactly
can we go about making our own linked list.
So we have created a node and then we have just joined them to create our own linked list.
Right now, as we move forward, we are going to write many functions which will be helping us to take
input, do different operations on our linked list.
Okay.
And then finally see that how we can just join all of them together into one class or one big linked
list class.
Okay, cool.
Then everyone, I hope this understanding was clear.
Uh, please make sure that you revise the concept of loops once again, because you will be using that
a lot going forward.
Okay?
Thank you.