Not let's look at another list implementation which is a linked list or the linked list is based on 2
a doubly linked list. 3
If you're not aware of it it's a fundamental data structure and it also has a variant called as a single 4
Englis which is normally referred to as a linked list but jostling list is based on bubblin and blessed 5
. 6
And so you're going to look at double English and also look at singly linked list. 7
Now just note that linguists are pretty popular when it comes to of yours. 8
And when I say English here I mean the linguists implementation itself like the single English ordered 9
linguist but not the job or not you darling. 10
So here is the thing with English. 11
So as a nym linked list implies it has a list of elements the elements are linked. 12
So here we have a few elements and elements are linked and each element is called as a note undernote 13
has two components. 14
One is the data which is the real data. 15
On the other one is a pointer to the next note. 16
OK so it links to the next not saying Djala we can have this kind of a class called Nord which has two 17
variables. 18
One is for the data. 19
In this case it is just an integer. 20
They don't but it can be anything. 21
And the second one is a pointer to the next in order on hands that that type is normal. 22
Now the last note here is not linking to any other nor And hence the next reference would be s.m. 23
Now here the first note is called us had nor I need said Dummy. 24
Which means that it doesn't have any data and all it does is connect to the first in order mechanically 25
the function or ordered make on top of the last note. 26
But that is dependent on the implementation. 27
Now in addition to not we will also have this kind of a class call as a linguist. 28
Yes so this is the main class and will be interacting with this class. 29
So here you are first creating a hard note on that head Norwell point to all other notes. 30
And we also have this augmented Henri will also how other methods. 31
So the oddment that is taking an and data alecks see how it works. 32
So the first step would be to create a brand new note on initialize it with the data. 33
And the second step would be to point it to the previously I did not get to the most recently added 34
note. 35
So we are pointing head dot next to the next reference and newly created note. 36
So at this point the old dog which was recently added It has two point one from head and the other from 37
the newly created order on the next step is to assign the newly created not hug. 38
So that's it singly linked list on here is there and blessed are not as the name goblin Lingula suggest 39
. 40
Each element has two links. 41
OK it is linked to the next element. 42
Like in the case of single Englis. 43
But it is also linked with the previous achievement. 44
So that's why you'll see dewpoint girs here and once again we have had not. 45
And in this illustration we have three elements to 0 1 and 2. 46
And the main thing to note here as there are a couple of properties one is if you add a new element 47
it gets added right before the hack. 48
In this case it is the element to iron the head is also linked with the zero element. 49
OK which is the first element. 50
So those are the two things that are happening here in English. 51
Now one benefit of that is that what Migdal linked list also as it Deck on deck is a sub interface of 52
Q. 53
We discuss that earlier. 54
Our deck basically has operations that frequently manipulate the first element and the last element 55
. 56
And here the head of it allow us to do that. 57
So that's one of the benefits. 58
And the second is if we want to look for an element or a particular index then we would have to traverse 59
through only half of the list. 60
So for that we will see if the next that is specified is close to the first element of or disclose to 61
the last element. 62
But if it is close to the first element we just traversed from head to the zero to node on the first 63
north on so on otherwise which I was from. 64
OK so how does allowing us to traverse in both directions in this case on based on the index. 65
It makes a decision on which way it has to go. 66
So that's another benefit of it. 67
Now let's just see how this kind of a doubling can be built on for dark. 68
We will use an add operation. 69
So initially we will how only the head node on the head Norton next on previous point to itself because 70
there are no other elements. 71
So we are adding an element. 72
Because of that. 73
And you know it gets created just like in the case of a single English and the second step is to set 74
its own going lengths which is nothing but the next and previous references since this note will be 75
added right before hand. 76
Its next should point to hide and that's what we are doing here in the US. 77
It meant years previous has to point to the previously added element which is also linked from the previous 78
set of friends in Hegg and that's the second statement here. 79
So once the outgoing links are set we also have to send the incoming links. 80
So one of the incoming links is from the previous. 81
We need to connect to this new order. 82
And the second thing is from the previously added note. 83
When you do link its next node to this new unit. 84
So here we can see that the new node is being assigned to the previous link and also the next reference 85
. 86
So no doubt next is nothing what head and yet assigning its previous reference with the new not a new 87
no doc problem would be the previous day or not. 88
But in this case it is it would be head our next next reference is being assigned with noon or so maybe 89
a little bit confusing but if you add one more element I think it will be easier. 90
So lets do that. 91
So here is on your not on here are the outgoing links. 92
Since its being added right before not its next Providence is wandering too hard on its previous reference 93
is pointing to the previously created not. 94
OK so now lets say the incoming links are in. 95
Here it is. 96
Are all all ordinance God disappeared. 97
So the had not previous is pointing to this new Not I and the previously created nauts next is pointing 98
to the new order. 99
So this is the final structure that we have. 100
So thats how the operation works. 101
It also works in a constant time as we always have a reference to head on we just need to add the new 102
Not before that. 103
And here are some typical uses you would want be use a linked list. 104
If you are true reading and doing that duration If you how frequent are ordering more operations then 105
you will go forward it because when you do the Ardmore operation all you need as if you are just fingerlings 106
. 107
So there is no element sheriffs like in the case of the test. 108
So if you how frequent are more during iteration you should go with a linked list on and consequently 109
it is also better for remote all and retain all operations because both of these operations and remote 110
elements during iteration. 111
So you would go for this. 112
So just remember that if I were you have to do frequent hour or more during iterations then you might 113
want to pick a linked list or other implementations. 114
And here are some of the matters which how linear time complexity. 115
So these are get our remore index off our last mix off and the history. 116
Get out and remove our position specific Mateschitz here so you can see the next eye. 117
And that actually and by two oblations not even linear. 118
And thats because as mentioned earlier they either try hours from the beginning or end depending on 119
the index. 120
If it is close to the first element then you are two hours from the first element. 121
But if I was close to the last element which is the size of Dulles then you will traverse from the last 122
element and said that headword allow us to do that on here is the corresponding code fragment Robsart 123
on radar could try was from the beginning order. 124
OK so to speak and from that Jawa source on this go to Sean here just to show you that a more efficient 125
big shift operator is being used for performing division. 126
Also note that for the get method idlest would work in constant time as it is based on ID which gives 127
the benefit of fast random access. 128
So for that matter our list is better than the length list. 129
So finally the link list is basically a doubling list implementation off list on deck interfaces. 130
So we will discuss DECT later but it mortal's before in freefall and the linked list actually supports 131
all of the needed operations follie 454 and constant time. 132
However when it comes to deck it is recommended to use a deck as it is optimized for faster manipulation 133
of both first as well as last elements. 134
We know that other deck implements deck. 135
So I think we can restrict using linked list as a last on muddler use it when there would be frequent 136
additions or deletions while iterating iron like an hour or less. 137
It also allows duplicate iron not like us. 138
So thats a bottling list. 139
So as far as the demo goes we dont have to do any more because it is very similar Go Adela's all we 140
need to do is change the implementation off other list from there or in their demo program to length 141
list. 142
But lets actually go ahead and see that and then we can sign off after that. 143
OK. 144
Here is the Arliss moment on since here we are programming to an interface we can take advantage of 145
polymorphism which means that we can assign any object which implements this list interface. 146
Ok so here we have idlest. 147
So let's just go ahead and just change it to length list. 148
I mean put that control shift. 149
Oh and that's it. 150
And we don't have to make any other change if we execute it. 151
Everything executes as it was when we were using our list. 152
So that's about it. 153
Thank you. 154
And happy coding.