Hello, my name is Typhoon.
Welcome to another lecture of our oxalic course.
In this lecture of our oxide course, you will learn about the removing an item from the linked list
a d t.
So let's get started.
So similar to the inserting operation.
The removing operation also has several cases, and there are three cases here.
So firstly, let's actually make this here the first case.
Here, the second case and the third case here.
So similarly here, the removed in the first case, the removed item is in the head.
So in the head.
So which is index is equals to zero.
So index.
Equals to zero.
And the second case is the removed items is in the tail.
So it's in the tail.
Tail and linked list.
So index is our index is going to be index.
Is going to be an.
And minus one.
In case of it's our removed item, it's going to be in the tail here.
So the removed item here in the third case we have a remove item is in the other position of the linked
list.
So in this case, it's going to we're going to write it other here and let's actually use a different
color for other.
Other.
And here then.
It's going to be index.
Index.
Is going to be one.
From one to index N minus two here.
So here, actually, let's write it in the different color.
So from.
From index one.
The first index.
To hear from.
To.
Here.
So from it's going to be in the other.
In the third scenario, our index is index.
From index first index and then from that from the first index until the N minus one index here.
So which is the last index, but minus one here.
So now.
The first case here.
Let's develop the first case and then we're going to create our another cases here.
So first, actually, let's move this here.
Yes.
Here.
Now.
Let's implement the first.
Search here.
So we're going to create a new tree here, which is going to be here.
So we're going to have we have here the remove heat, remove tail and just remove, which is this is
the third case here.
This is third case.
Remove tail is second case.
And remove heat is first case here.
So now let's create our application.
Firstly, we're going to create the case one here.
So the implementation is straightforward here.
So we're going to create we just need to point the heat pointer to the node, which is pointed by the
next pointer of the current heat.
In other words, the second element and delete the first element of the linked list.
So here template the type name T and after that void linked list, we're going to create the.
Remove heat here.
So remove heat.
And after that we can create a condition which is going to be do nothing if the if the list is empty.
Since we don't have anything to remove in this list here.
So my count, if our list count is zero, then just return and do nothing but.
After that, we're going to save the current hit to new node.
So in this case node here.
Node and hit.
And we will point the hit pointer to the element next to the current hit.
So in this case it's going to be the hit equals hit and next year initialize hit to hit next here and
after that now it's safe to remove the first element so delete node.
Here.
After that, we will.
Decrement our count here, which is going to be minus one.
So here.
Decrease the one element from my count since we removed one from the heat.
So as we can see in this code, regardless of the number of the length list element, the complexity
of operation is zero and one, which is the best case scenario here.
Zero one.
So.
For the removed tail operation.
We have to traverse all list elements so that we have two less nodes.
So which are indexes in minus one and N minus two.
And then we set the next pointer to the next pointer of the end to, to the point of null.
So after that we can safely remove the last node since the operation must traverse all list elements.
So the complexity will be here zero here in the if we're going to write it here.
So the complexity is going to be zero multiply by N.
So here we're going to template template type.
Typename t void the linked list we're going to hear t and after that we will remove tail.
So after that, as we're going to as we did in this here, if my if count my count equals to zero,
then return just do nothing.
And after that, if list element is only one, just simply call the remove hit here.
If my count is equal to one, then just simply call the return or remove hit here.
So remove hit and after that we will return here.
Since we removed and completed our operation here.
And after that we need to start a start.
Yeah.
Start to find previous note from the heat.
So in this case, we're going to create the here.
Not.
Not here to.
And previous note.
Hit here.
And after that, we're going to create a candidate of items, candidate of removed items, which is
the element next to the preview node.
Here in this case, we're going to create the node t pointer here and hit points to next.
After that, we will traverse elements until the last until the last elements here.
So in this case, while while the node next here is not equal to null.
Null.
Then we're going to print node three.
Previous node next here.
Next.
And after that node equals node.
Next.
So the then the pre note here previous note now became a tail so that the next pointer of the pre note
points to null.
So in order to do that we're going to create the pre note pre note here next and null here.
So the tail is going to be pre note here so now it's safe to remove the last element delete delete note
and after that we will.
Decrease the decrement the size of our my count since the element is removed here.
So the last operation is the remove operation.
And here this is the complexity of this operation is going to be.
Yeah, the complexity of this operation is going to be.
Yeah, it is.
Uh, it is the same with the heat.
So it's going to be.
Zero and one.
So the best case scenario here and we can also develop our review operation.
This is the last operation which we will remove the least element between the first and last element.
So in this operation, we need to traverse the least element until the selected item is index.
Selected indexes reached so similar to the index of insert operation, we need to find the element before
and after selecting index.
So after we find them we can link them together and then we can safely remove the element in the selected
index here.
So let's create our delete or remove operation here.
So now template Typename here T and after that void the linked list t here and remove remove here just
to remove which is going to get the index parameter here.
And after that, if our list is empty, my count is empty zero.
Then return and do nothing since we don't have anything to return.
And after that let me actually check the lecture time.
Yeah.
So after that return here.
So if our.
And also we're going to also do the.
If here if index is less than zero or index is greater than equal, index is greater than or equal to
my count, then return.
So awesome.
And yeah, in this case, we're going to just return and do nothing.
So if our.
So in this case, it's going to be out of bounds.
So if our index is less than zero or index is equal to or greater than zero, then this is the out of
bounds.
And here then return and do nothing.
So if our, uh, if we don't have anything in our list, then also return signs.
We don't have anything to remove here, so.
Here, we will develop our.
If our index is zero.
Signs if our index is zero.
So this means we are going to delete the first element since we already developed our the remove heat.
Then we're just going to remove the heat here.
So we will execute, remove heat and successfully executed here and removed item.
So if the here after that if our removing or remove if our removing the current tail we're going to
also add the else if here.
Index and my count.
Minus one.
And remove tail.
After that, we can also return here.
So this is also successfully executed and we removed item from the list.
Now let's get started with the our real remove method here.
So now we're going to traverse the list here from the heat.
So note to previous note, please note here and heat here.
Not like this here heat.
And we will find the element before the selected index.
So we're going to create a for loop integer.
Integer is zero here.
E while e less than index minus one, then increment E plus e by one here, increment e by one.
After that we will print here equals previous note pre note.
Next.
And here.
We will the removal remove the element is after the preview node here.
So we will.
Oops.
Here.
Yeah.
So here node t here and not the previous node and the next.
Next year.
After that, the node will be the neighborhood of the previous node.
So if the node is removed.
So in this case, we're going to do the node to the next node.
Node.
Yeah, the next node to the next node is going to be node here.
Next.
And after that we will link the previous node to the next node.
So previous node to.
Next and next node.
And after that, now it's safe to remove the selected index element.
Now we're going to go delete Node.
And after that we.
Need to decrement the decrement count of our list since the one element is removed here.
So as you can see in this code, we will invoke the remove heat operation if the index is equal to zero
and will invoke the remove tail operation here.
Remove tail operation.
If the index equals my count minus one.
So it's not clear that in the best case here, which is remove heat and remove tail is invoked, the
complexity is zero one.
And in the worst case, when the remove tail actual remove tail is invoked, the complex is zero.
And here.