Welcome back.
Now in this video, let's discuss what we have to do as part of the question and how we will do it.
And then we will also discuss the time and space complexity for these instance methods.
All right.
So let's get started.
Now the first thing which is mentioned in the question is that we should be able to create a singly
linked list object.
All right.
So let's see how we can do this.
Now we have seen that for this we will use a class right.
In a previous video we have discussed that a class is a blueprint to create objects.
So over here we will have a class singly linked list.
And you can see that in the question.
It was mentioned that the singly linked list should have a head and tail.
So when we have the constructor over here, we will just say this dot head is equal to null and this
dot tail is equal to null because initially it's just going to be empty.
And then we have an extra property over here.
Now it's good to have we can track the size of the linked list.
So initially as there is no node we will have this dot size is equal to zero.
And then we have the node class over here.
Now it's mentioned in the question that every node should have two properties.
One is val and the second property is next right.
So that's why we have two properties over here.
So when we create a node it will have a value which is the value which is passed to it when we create
the node.
And then next initially we'll just point to null.
So we have these two classes over here.
Now we will use this class over here class singly linked list to solve the first part of the question,
which is to create a singly linked list object.
Now for this let's say we want to call this SL.
So if we just want to call this SL then we can say const sl is equal to new singly linked list.
Now by calling this we will be creating an object.
And this is the object over here.
Now you can see that this is very much similar to having a new array.
Right.
You may have seen something like this const array.
Let's say r is equal to new.
And then we may have array.
And you can pass the size for example.
Right.
Let's say ten.
Now again this is very much similar right.
So you can see over here again singly linked list is not an inbuilt thing which we have in JavaScript.
So we have defined the class over here.
And using this class we will create the singly linked list object.
So that's the first part of the question.
And you can see it's pretty straightforward.
Now for the remaining part of the question we will add instance methods in the class over here.
We have seen previously that when you have a class you will have objects.
And objects can have properties.
So these are the properties.
And then it can have instance methods.
Right.
So we will have instance methods.
And that's going to be these five methods over here which is get index get add index added head and
then add a tail added index and delete at index.
So let's go ahead and see how we can implement these.
So the first one over here is already done.
Now let's proceed and go to get index.
All right, so we are over here at Getindex.
Now, let's say we already have a singly linked list and let it look like this.
So we have one node with value one.
And then we have a node with value two.
We have a node with value three etc..
And again over here when we want to create this node we will call the node class.
So we will just say for example if you want to call this one we can say const.
And then let's say the name of this is one.
So that's equal to new.
And then this is the node class that we have written.
And then we will just pass the value to it.
So this will call the constructor.
And it will create a node with value one.
And the next is initially going to point to null.
So this will be created.
And then we'll have to create the next node and we have to add it etc..
So we will see over here how we do that in the next functions.
All right.
Now for now let's say that we already have the singly linked list.
So we have a node with value one which is pointing to a node with value two.
And that is pointing to this node over here with value three which is pointing to null.
So the head is over here, which is this node over here.
And this is the tail.
So this is the head and this is the tail of the singly linked list.
Now let's say we want to get the node at index two.
So let's say index is equal to two.
And we are calling the get index function over here.
And the index is equal to two.
Now let's see what happens.
And again remember it's mentioned in the question that the singly linked list is zero indexed.
So that means that this node over here will be treated as index zero.
This one over here will be treated as being at index one.
And over here we will treat it as index two.
All right.
Now we will have to use a variable.
Let's say we call it current.
And this is going to point at the head initially.
And then we will just keep iterating through the singly linked list till we get the counter equal to
the index over here.
So we'll have a counter.
So let's say counter is equal to zero.
And you can see that currently this current over here is pointing at index zero.
And we have our counter is equal to zero.
Now we will keep moving the current over here towards the next in the next direction till the counter
becomes equal to the index which is given to us.
So over here zero and two are not equal.
So let's move the counter.
So the counter comes over the the current.
So let's move the current.
So current comes to the next node.
And we increment the counter.
So counter becomes equal to one.
Now still one is not equal to two.
Therefore we are again going to move the current pointer.
All right.
So it's going to move to the next node.
So we get it over here.
And we again increment the counter.
The counter becomes equal to two.
And now you can see that the counter is equal to the index.
Both are equal to two right now because the counter is equal to index.
We have found the node at the index.
And then we can just return current.
And current is pointing to this node.
So we will be returning three which is this node over here.
So this is how we will deal with the get index function.
All right.
Now remember if the index which is passed to us is less than zero or if the index is greater than equal
to the length of the singly linked list, then it's just invalid.
And in that case, as per the question, we will just return minus one.
Now, even if it's equal to the length.
Also it's invalid.
For example, over here you can see the indices are zero, one and two.
And the length over here is three.
So at index three you can see there is nothing.
So that's why if the index is greater than equal to the length or less than zero because the first one
is zero right.
In these in in these cases we will just return minus one.
So this is how we solve the get index function.
Now let's take a look at the complexity analysis of the get index um function which you have written.
Now if we want to get the node at index, then we can say that the time complexity is going to be of
the order of index, and the space complexity is constant space.
We are not using any extra space now.
The time complexity is of the order of index, because you can see we have to keep traversing the singly
linked list till we reach the index.
Now, in the worst case this is going to be time complexity of the order of n, right.
So for example, if you want to get this node or if it's a very big singly linked list, and let's say
we want to get something very close to the end.
So in that case we can say the time complexity is of the order of n and the space complexity is constant
space.
All right.
So we are done with this and we are done with this as well.
Now let's proceed and see how we can implement an instance method to add a node at the head of the singly
linked list.
All right.
Now for the added head function you can see over here the value is passed.
The value has to be passed.
So we will take this value.
And we will create a node which has the value which is the given value.
And then which is pointing to null.
So for this we will use the node class.
So we have seen that we have a class node right.
Now inside this there is a constructor, and in the constructor we are passing the value.
And then over here.
Remember inside this we are going to say this dot value is this value which is passed to it.
And this dot next is equal to null.
So that's how we will have a node.
And it has two properties which is value.
And the next and next is going to point to null initially.
And then the value of the node is going to be the value which is passed to it.
So this is what we will do.
Now let's proceed and see how we will insert it at the head of the given singly linked list.
Now there are two possibilities.
Let's say the head is null.
That is, the singly linked list is empty or there is no node at this in the singly linked list.
If this is the case, then we will just take this node which we just now created.
And then we will say that the head and tail of the singly linked list is this node itself.
All right.
So then this becomes our singly linked list.
And the head and the tail is both this node itself.
Now if this is not the case that is if the head is not null.
So let's say there are already some nodes and they have some values.
Let's say we have the value one, two, three, etc. over here.
So this is our singly linked list.
And then we have created this node.
Now what we have to do is at the moment this is pointing to NULL over here.
Right now this has to be changed.
And we have to make this point to the existing head.
So we will have the node with value over here.
And it's going to point to the existing head.
And then we will just change the head of the singly linked list to this node over here.
In this way.
You can see we have added this node at the head of the given singly linked list.
So this is how we will implement the added head value added head instance method.
All right.
Now let's take a look at the time and space complexity of this method.
Now over here you can see the time and space complexity is going to be O of one or constant time and
constant space.
Why is that so.
Because we don't need to traverse right.
We just need to have some checks.
This is going to be taking constant time.
Checking if the head is null or not is a constant time operation.
And then if it is null then over here we are just setting the head and tail to this node.
Again you can see these are just constant time operations.
They don't scale.
And even if you have a very big linked linked list, right.
If the singly linked list, let's say has hundreds of nodes, even then we know the head and we will
just take this node and we will make it point to the existing head and make this the head.
So you can see we it's, it's, it's, it's taking place in constant time operations.
It's not that there are operations.
The number of operations will scale with the inputs size scaling.
So that's why we can see that this is going to happen in constant time and constant space.
All right.
So we are done with these three.
Now let's proceed to the next one which is add at tail.
Now over here also the value is passed to us.
So we take this value and we make a node out of it.
And initially it's going to point to null.
Now let's check if the head is null.
If the head is null.
Again we take this node and we are going to make the head and tail point to this particular node over
here.
So that's similar to what we have seen in the previous function.
Now if this is not the case, let's say there is already a linked list.
Let's say it looks it's looking something like this.
So there are values over here.
Now what we need to do is we take the node which we created.
So we have the node over here.
Now we will take the existing tail.
This is the existing tail.
And you can see that the singly linked list has the head and tail property.
So we can access the tail.
So we access the tail.
And then we will make the existing tail point to the new node.
So we will make it point to the new node.
So we will say tail this dot tail dot.
Next is equal to the particular node which we created.
And then we will reassign the tail.
We will change this and we will make this particular node over here the tail.
So this is how we will add at the tail.
All right.
Now let's take a look at the time and space space complexity of this instance method.
Now again because we know the tail, even if this is a very big singly linked list, we don't need to
traverse the singly linked list to reach the tail.
Again, that's because we have the tail property.
If we were not tracking the tail of the singly linked list, then it would be an O of N operation.
But because we already know the tail, we will just say tail dot.
Next is a node and then we will make this the tail.
So you can see this is also a constant time operation and constant space operation.
It's constant space because we are not using any extra space or any auxiliary space.
All right.
Now let's proceed to the next instance method, which is to add at a particular index and the index
and the value is given to us.
Now again the index and the value has to be given to us.
So we have index comma value over here.
Now we take the value which is given to us.
And we make a node out of it.
All right.
And then we will check if the index is null.
So if the index is invalid.
So if the index is less than zero or greater than the length then it's an invalid index.
Right.
So we won't be able to insert it anywhere.
So maybe we'll just return a message saying the index is invalid.
Now if the index is equal to the length then we will just add it at the tail.
Right.
So for example if this is our singly linked list.
This is pointing to null.
So you can see this is zero one and two.
The length over here is three.
So if the index is three then that means that we have just have to add the new node over here.
Right.
So that's this is index three.
So you can see this is nothing but adding at the tail.
So if the index is equal to the length of the singly linked list we will just add at the tail.
And for this we already have the function right.
We have the added tail function.
So we will just call this function and pass this value.
So we are doing this so that we can minimize the code that we have to write the number of lines of code
that we have to write.
And we are trying to reuse what we have already written.
Now if the index is equal to zero, we will just add at the head.
And again we already have a function for that.
Right.
So if the index is equal to zero we will just call the added head function which we have written the
instance method.
And we will pass this value to it.
Now if this is not the case then let's see how we go ahead.
Now again, only if these things are not true, then only we need to go ahead and make a note of with
the value that we have, because otherwise we are anyway calling these functions and inside the functions.
We are already doing this part.
Now, if this is not the case, that is index is not invalid, index is not equal to length, and index
is not equal to zero.
In that case, we will go ahead and make a note with the value.
And then it's going to point to null.
Now then let's say this is the singly linked list which we have.
And let's write the indices over here.
And let's say the index which is passed to this function over here is equal to one.
So that means that we have to insert this node over here before the node which is currently at index
one.
Right.
So that is what we have to do.
So for this first we have to identify the previous node.
All right.
So we'll have to identify the previous node.
And for this we can use the get function over here.
Now we will just pass index minus one over here as a parameter.
And that will return the previous node.
So first we will get the previous node.
And then over here we have the node which we created.
And we have to insert it over here right before this node.
So what we will do is we will we identified the previous node and we will make this point to the node
which we created.
So we severe this connection and we make it point to the node which we just now created.
And then we will make this node over here point to this node over here.
Right.
Which is the which which is previous dot.
Next.
Initially before we remove this this can be said this is previous dot next.
So we store it somewhere.
And then we are going to make this node over here which is the node that we created.
Point to this node.
So we make this connection over here and that's it.
Right.
So you can see we have inserted this node before this.
And at this moment you can see if we again write the indices.
This is zero.
This is one.
This is two and this is three.
So you can see the node was inserted at index one.
And currently at index one we have the node that we inserted.
So that's interesting.
All right.
Now let's go ahead and take a look at the time and space complexity.
Now remember in the worst case again when we talk about big O we are talking about the worst possible
case.
So in the worst case getting the previous node can be an O of n operation.
Right.
Because let's say the know the position is somewhere very close to the end of the singly linked list.
And then we would have to traverse the singly linked list starting from the head till two till that
index minus one.
So this is going to be an O of n operation.
Just think about it like let's say the singly linked list has a hundred nodes.
And let's say we want to insert at position 90.
So then the previous would be 89.
So we would have to traverse all the 89 nodes to identify this.
Right.
So that's why this is going to be an O of n operation in the worst case.
So we can say the time complexity is O of n worst case.
And the space complexity is going to be O of one.
Again, the space complexity is O of one, because we are not using any extra space or any auxiliary
space.
All right.
So we are done with these for now.
Let's take a look at the last instance method which is delete at index.
So the index has to be passed to this function.
All right.
So we start by checking whether the index is valid.
So if the index is less than zero or greater than the length then it's an invalid index.
And again over here it should be greater than equal to right.
Because again for example this is our linked list.
And let's say we have zero, one and two over here.
Now you can see that the length of this linked list is equal to three.
Now if you want to delete the node at index three you can see there is nothing right.
That's why this should be greater than or equal to the length.
So if the index is greater than or equal to the length of the singly linked list, then it's an invalid
index.
And maybe we can just return a message that says the index is invalid.
Then we check if the head is null.
So if the head is null, we will just return null.
Again, we don't need to make this check because that's going to be already considered over here.
Right?
So if the head is going to be null, then the size or the length of the singly linked list is going
to be equal to zero.
And then whatever index we pass, it's either going to be less than zero or it's going to be greater
than equal to zero.
Right.
So again over here itself it's going to identify it as invalid.
So we don't need to make a separate check for this.
All right.
So this is already taken care over here.
Now let's proceed.
Now what are the valid cases.
So if if the index is not invalid we proceed and check the valid cases.
So the valid cases is that maybe we want to delete the head which is index is equal to zero.
Or the index may be length minus one.
In which case we want to delete the tail node.
Or it may be another index which is not the head and not the tail.
So let's take a look at these possibilities.
So for this let's say this is the singly linked list which we have.
Now if we want to delete the node at index equal to zero then we are going to identify the next node.
So this was initially the head.
So we are identifying the next node which is this one over here.
And then we will just make this node over here the head right.
So this is going to be made the head.
All right.
So that's it.
So that would remove this because we are going to have the linked list starting from the head.
And this is now the head.
So this is no longer the head that would be removing the head.
And if you want to remove the tail then what would we have to do.
We have to identify the previous node.
This is the previous node right.
This is the current tail.
This is the previous node.
And then we will just make this the tail.
We'll make this the tail.
And then we will make the tail point to null.
So we'll make it point to null.
And then we just have removed this which was the tail.
So that's how we will remove the node at index is equal to length minus one.
All right.
And again to identify the previous node we can use the get function which we have written over here.
So we will just use get at index minus one.
So over here we will pass index minus one because we know the index is equal to length minus one which
is this over here.
So for example over here 012 and three the index is equal to three.
So we are going to pass three minus one which is two which is this two.
Over here to get the previous node.
All right.
So this is how we take care of these two scenarios.
Now what if we want to delete another node which is not the head and not the tail.
Again let's take a simple singly linked list which is this one over here.
Now let's say we want to delete the node at index is equal to one.
So that would be the second node over here right.
So this is one.
So we want to remove this one.
So again what we have to do is we have to identify the previous node.
For this we will again make use of the get function over here.
And we will pass the index minus one.
So index is one.
So we'll pass index minus one which is one minus one which is equal to zero.
So we are going to get the node at index zero which is this one over here.
So after identifying the previous node all we need to do is we will make this point to this one over
here.
Right.
So again when this is the uh, let's say the current node, we will just store this.
So this is going to be current dot next.
And then we'll just say previous dot next is going to be equal to current dot next.
So we are making this connection over here.
All right.
And again let's take a look at the time and space complexity of this solution.
The space again is going to be constant space.
You can see in all of these functions it was constant space.
We are not using any auxiliary space.
Now.
What about the time complexity to delete a node?
Now when it comes to the time complexity, let's take a look at these three scenarios.
If we are deleting at index zero then it's going to be a constant time operation, right?
Because we already know what is there at the head.
We just have to move once to the next one and then set this to the head.
So even if the singly linked list has hundreds of nodes, it's still going to be the same number of
operations.
So we can say that the time complexity is constant if we are deleting at the head.
Now, if we are deleting at the tail, even though we track the tail, still it's going to be an O of
N operation because we have to do almost n operations to identify the previous node.
Right?
That's why this is going to be an O of N operation.
All right.
Now if we are trying to delete another node which is not the head and the tail, in the worst case it
is going to be of the order of n.
All right.
Again that's because we have to identify the previous node.
So for example let's say the singly linked list has 100 nodes.
And we want to delete the node at index equal to 95.
So we would have to identify the node at index equal to 94.
And for that we have to do almost n operations.
Right.
Almost n which is in the in this specific example we have to do 94 operations which is 100 minus six.
And in that case the n is equal to 100.
If the singly linked list has 100 nodes.
So we can see that in the worst case, deleting a node from another index is going to be of the order
of n.
All right.
So we have seen all these instance methods.
All right.
Now let's take a quick look at the time complexity.
Again.
Let's summarize it.
We have seen that the space complexity in all these instances is O of one which is constant.
All right.
Now what about the time complexity to get at an index the node at a particular index?
It's going to be at the time.
Complexity is going to be of the order of the index.
All right.
Again in the worst case it's going to be O of n.
All right.
And the worst case is if you want to get the last index or if you are giving an index which is greater
than the size.
Again, if you track the size, then we immediately know that it's not possible.
So if you are not tracking the size, that would be an O of N operation.
But then if we are tracking the size, then if you want to get the node at the tail or very close to
the tail, that's going to be an O of N operation.
All right.
Now let's take a look at the next one.
Over here we have added head and the value is past.
So over here this function over here is going to be a constant time operation.
Because we have seen we just need to add it.
Make the next pointer of the new node point to the head.
And then we'll make the new node the head.
So that's going to be a constant time operation.
Now adding at the tail.
That is also a constant time operation because we already are tracking the tail.
And then we will make the existing tail point to the new node which we just now which we create.
Right.
So that's again a constant time operation.
Now adding at an index.
What about adding at an index.
That's going to be in the worst case an O of N operation.
Right.
If you're adding at the head that's a constant time operation.
But if you are adding at the tail and we don't know that we are adding at the tail, right?
For example, in this case, if we directly call added a tail function, it's a constant time operation.
But then if we are if we have this linked list over here.
All right.
It's pointing to null.
And then let's say we are passing the index as three.
So this is zero.
This is one this is two.
And we are passing index as three.
And the value is some value let's say 4 or 5 something.
Then we don't know that we want to add at the tail.
Right.
So we would have to keep traversing.
And then that takes O of n time.
And then we have to identify the node at the previous index which is two over here.
So that's why this is going to be an O of N operation in the worst case.
And again even if we are trying to add at an index close to the tail, that's also going to be an operation
of the order of N, because it may be n minus two or n minus ten, etc., depending on how far from
the tail it is, but then it's going to be off the order of n, so this is going to be of O of N because
we have to find the previous node.
All right.
So now let's go to the next one.
So what about deleting at an index.
If you are deleting at the head we have seen that's a constant time operation.
All right.
Now if you are deleting at the tail that's going to be an O of N operation because we have to find the
previous node.
Right.
So even though we are tracking the tail, still deleting at the tail is going to be o of n because we
have to go, we have to traverse the singly linked list to identify the node which is just before the
tail.
And if you are trying to delete another index, then in the worst case that's going to be an O of n
operation.
So again what's the reason for that.
That's because we have to identify the previous node.
So this is a summary.
So we have successfully discussed how to implement these instance methods.
And in our singly linked list class.
Now in the next video let's go ahead and implement the code of this.