Hello, my name is Stephanie.
Welcome to another lecture of our Oxford course.
In this lecture we are cplusplus course we will insert an item in the linked list class.
So let's get started.
So let's move to on the insert operation for the Linkedlist class.
So there are four cases for this operation and they are those are the first case is the new item is
inserted at the beginning of the linked list, which is index index of sexual.
Let's do that here.
So which is index.
Equals.
Here equals zero, which index is zero so that it becomes the head here.
So in this case, it's becomes the head.
We also have in the at the second here.
At the second.
We would also have this is the second case.
So the new item is added to an empty linked list.
So if the linked list has only one element, so it's going to be both here in this case of empty list,
the it's going to be hit.
And a tale.
Tail, which in this case it's going to be head and tail.
And we'll point to the only element.
So they are going to be point to the same element, Same element.
And also let's make this like that.
Here.
Also, let's take this here and make it up here.
So.
And the third year.
Here.
The third case is that the new item inserted into the last of the linked list, which is is going to
be the index.
Index is going to be an.
Here.
So the it becomes the new tail here.
So it will become the new tail.
So new.
Tail.
And last here we will talk about is the fourth.
And they also have the fourth, which is the new item is inserted in the other position of linked list
where the index is going to be here index.
Is going to be one.
From one.
To n minus one.
So in this is going to be one to index from one to from one to n minus one.
So let's actually hide this and let's see how to create our insertion.
Process here.
So now here.
Oops.
Let's create the implement.
We will also create an implementation for inserting an operation for cases one and two so we can solve
these problems by creating insert hid operation that in previous lecture we did it here, insert hit,
insert tail and insert here just an insert.
So the implementation of this operation here, after that, we're going to after get here, as you can
see, we defined here get.
And after that we're going to add the insert head here.
So with length list.
And we also need to add the template here.
The template is going to be type name.
Template typing t here.
And after that void the Linkedlist.
As you can see here, our insertions are our returns.
Nothing here.
So that's why we created a void here.
So now it's going to be t and insert insert heat.
So it's going to we don't need val, we don't need index if we know where we are adding.
So in, in insert we have to, we have to here but in insert.
Hit.
We don't have we just have the value that we're going to insert at the head of our list.
So let's quickly clear this and come here.
So now we're going to add the insert hit.
And as you can see here, we just need one as a parameter.
So after that.
Uh, actually here.
So after that, we're going to inside the inserted function, we're going to create a new node.
So node to note here.
So the new node is going to be.
Template.
Not.
It's going to be a template and value here after that.
So the current node or the current heat will no longer become a heat.
So the next pointer of the new node will point to the current heat here.
So the node next is going to be point to the current heat.
After that, let's actually create the new node to become the heat.
So here we're going to create heat equals node.
Sign the heat to node here.
So let's actually create another condition here.
So another condition.
So if the link list is empty, the tail is also the heat as we discussed in third case here.
So if the if the my count is equals zero, then our tail is also heat.
And after that we will add the after outside the if.
Here we will add one element, which is going to be a increment, the one element here.
So we inserted heat and after insertion here, we will add one element here.
And as you can see here, the element is going to be plus one.
And we will add this element inside our list.
Here.
So as you can see here, the insert hit operation will create a new node that assigns it to a new hit.
So if the linked list is empty before applying this operation, the new node also become the tail.
So, um.
For this.
The complexity of this operation is going to be zero.
And one.
So regardless of the number of the for the linked list is limited.
So it's actually not that complex here for case three.
As I as we learned earlier of this lecture, in the inserting operation, we can implement the insert
tail operation.
So the operation is simple and efficient.
So we just need to create a new node and then assign it to the new tail.
So the next pointer to previous tail will point to the new tail here.
So let's actually delete this and come here.
We create our insert hit.
Insert is developed insert tail here.
We're going to add now and here let's go to our coding process.
So now we're going to also create a type name after the insert head.
So the template type name.
Name is going to be T And after that void, the length list is going to be T here.
Also the insert tail.
Insert tail.
Oops.
Insert tail here.
Insert tail.
And now we will pass that value here.
So let's create another condition here.
So if the linked list is empty, just simply invoke the insert.
So here we're going to make it the if my count is empty or yeah is equal to zero, then it's going to
be insert hit and just end the function here.
So we will return function.
So insert hit and we will pass that value to our insert hit which this will pass to our insert hit here.
So.
In this case is going to give.
It's going to be well here.
After that, we will return.
Return.
So if this condition is not.
True, then we will create a new node.
So not here, not t, not here.
So new node is going to be T and we will pass value here and here we will create this code and I will
explain now here.
So we will write this code.
So in case of that, the current tail will no longer become a tail.
So the next pointer of the current tail will point to the new node here.
So and we will also then a new node B, it's going to be become the tail, so tail equals node.
And after that we will add one element as we did in the add in the ADD heat method here.
So we will add one element plus one here.
So in this case it's going to be.
My count of sexual.
Let's delete this.
Here.
So the my count is going to be plus plus.
That's it.
Also, please keep in mind that we might run the insert tail operation.
Insert tail operation when the linked list has no elements.
So if this occurs, the case two as we discussed in previous lecture and in the beginning of this lecture,
the case two will happen and we can simply invoke the insert hit method.
So the complexity of the insert tail method is same as our insert head method.
So in this case it's going to be zero multiply by one here.
So regardless of the number of the linked is list elements here, so the complexity is going to be same.
So it will even invoke the insert head operation.
Since the insert operation complexity is also zero one here.
So now let's actually create the case for here which we need to traverse the elements for the linked
list to find two elements where we want to insert the new element between them.
So we will call them previous node and next node.
So after we find them, we then create a new node point to the next pointer of previous node, so to
new node and then point to the next pointer of the new node to the next node.
So the implementation of the insert operation.
So it might be complex here, but after we writing our code you will understand all of this.
So after our.
Insert tail method, we will create the again, the template here.
So template.
Template is going to be type name T.
Here and we will create an insert method.
So in this insert method here, we will add.
The index and value.
Except as you can see, we just had the value here because we are inserting.
We know where we inserting, right.
In this case, we're going to insert the heat.
In this case, we're going to insert a tail.
But in this case, we're going to need the index here.
So that's why we're going to create two parameters.
And here it's going to be void length list T here insert.
Insert just an insert here.
So first we have index and Val.
And first we need to check if the index is out of bounds.
So if our if our index is less than zero or our index is greater than my count, then just return here.
If this not happen, let's run our function here.
So if the.
Let's actually insert a new hit.
So if index is equal to zero, then insert hit.
And we will pass our value.
And as you can see, we are again using the insert hit because if our index is zero, then we can also
insert hit here.
So that's why we executed this, created this.
If and after that then we didn't miss the our insert is completed and just return here.
After that, uh, if if we are inserting a new tail.
So.
Else if.
If our else if in our index is my count equals to my count, then we will insert a new tail.
So in this case, I will explain all of things now.
Insert insert tail is going to be val and return.
So in this case.
Uh, it will run if our node has zero elements.
But if here, if, for example, if our in this case we have five elements and we we want to add in
the fifth index, then we can also use the insert method for this.
So we don't need to write separate method for this.
So that's why we created this conditions for more efficient programming here.
So now.
We will start to find previous note from the Heat.
In order to do that, we will create.
Note here.
Previous note here.
Note it's going to be previous, not pre note here.
It's going to be hit here.
Hit And after that we'll need to traverse the elements until the selected item is found.
So we will add four here.
Integer is zero and while our e is less than index, then our index minus one then plus plus E here.
And we will.
Some previous node.
Previous node equal Previous node.
And next.
Okay, So after that, we need to create the next node, which is the element after the previous node
here.
So note here the next node and assign it to previous node previous node and we will make it next here.
Oops.
Next.
And also delete.
Because.
Here.
So we will also make.
Uh, also create a new node.
Firstly here.
So note here the oops node to node.
The new node is going to be T, which is we will pass value here and after that we will insert, insert
this, insert this new node here.
So we will insert this new node between the previous node and the next node.
So.
Not here.
Next.
And next not.
And previous note we will insert previous node to our next and it's going to be node here.
And we ask after that signs we are executing the insert after insert operation.
We're going to add one element as we did in the insert tail and insert heat method.
So my count.
Plus, plus.
So since we need to traverse the list element, the complexity of this insert operation is n here.
So, however, in the best case, the complexity is going to be here less best case, the complexity
is going to be zero one, as in insert it and insert tile.
So that's because since we might insert a hit, so here our tail or after the operation.
So complexity of this code here.
Complexity of this code is actually let me write this and make it right here.
So.
The complexity of this code is zero one.
Signs are inserted.
Complexity is zero one.
That's because we know where we're inserting our value and insert is the same like the insert here.
We know where we ending our.
A value.
But in this case, we don't know where our index is or where our values.
That's why we have the o n here.
So n is the index here.
So.
If that's why we added this here.
So to reduce the complexity and a bit more code efficiency for our C plus plus.