OK.
So welcome back again.
The first data structure that we are going to talk about is the linked list, and we are going to go
over two types of link lists.
The first one being a singly linked list and the second one being a list.
So let's get right into it.
So looking at singly linked lists, they are basically just made up of these things that we're going
to call nodes, which we will be implementing as a class or struct.
And they have data associated with them.
You data members, as well as a another member of the class that is a pointer to the next node.
And so we will have this node class as well as a class for the entire list.
And basically the next point her, which will be a node pointer, enables us to get from each node to
the next node and we can traverse it in a sequential fashion like this.
And at the end here, you see, it's pointing to no will be initialized in these pointers to know,
and that's a good way to know if you're going off the end of the list.
So we do not try and reference a null part of memory and get a segfault like you might have encountered
in the previous parts of the course.
So, yeah, there also is a head and tail that we can label, so we might have a.
Had, I guess, part of the last class we would have like a head pointer, they would point to the first
node in the list and a tail pointer that would point to the last and we'd be updating those as we add
things to the list.
OK, so let's move on to the next one, which is doubly linked lists pretty much the same thing, except
now we have a way to access the previous node.
So you can see it's kind of bi directional here.
We can traverse it to the right this way going forward to the next node, as well as going backwards
this way to the previous node.
So we have that next pointer, but we also have a member that is pointing to the previous node as well,
and we will need to update those as we move along and add new things to our list.
And you also see here that this previous pointer is pointing to null at the beginning of the list here.
So why even talk about linguists?
What are they for?
Why should we use them anything special about them?
Well, the first thing to really look about or the main thing, the main thing to look at is why would
you use it over something else?
So one of the main comparisons of this made is using it over an array or vector.
And the advantage that the linguist has over the vector is that if you are inserting a new element into
a vector or an array and mind you, this is not at the end, so it's not a pending an item, but you're
inserting it, let's say, somewhere in the middle, which is anywhere besides the end, you know,
or it can be the beginning.
But it's much more efficient when you have a link list because you don't need to push everything back.
If you add something in an array or vector, just by their nature, being able to index those things
since they're subscript able.
It means that if you're going to put something in some place, you need to move everything out of the
way.
So if you think about it, it's kind of like if you had a bunch of things lined up in a row, they could
be anything like a bunch of cards or something, but they were all pressed right against each other.
If you're going to put something in the middle, you're going to have to move the cards next to it over
to make space for it.
You have to move the card to the right of that card or.
The laughter, you know, let's just say that you were.
Choosing to insert it in like the second position, you'd have to move the car to the left out of the
way and then the cars to the right, I believe the each time you moved, when you have to move the next
one to its right and so on.
So that kind of operation turns into linear time because if you have any items in the vector or array,
you're going to have to move those in items, shift them over to accommodate for the thing that you're
inserting.
So you think back to when we had just talked about at the time complexity and previous lecture, you
remember how we were counting those operations.
And that's basically what's happening in this vector is that we're having to go through all those items
and perform an operation where we're moving it over.
So in a leaf list, you can just insert something and change some pointers around and put the next pointer
pointing to the new thing.
Put the.
The thing to the right pointing back to it, if you have a creative pointer, we'll get into the implementation
details in the next video, but it's a lot easier and more efficient than inserting something into a
vector.
And I don't know if I would say easier because you are you going to have to move around some pointers
kind of change the things they're pointing at.
But in terms of efficiency, it is a lot better.
So that is a reason to use a linguist and inserting that can be done in constant time.
Since you remember back to that previous lecture about time complexity, you know that that's one of
the best begos that that we could see there if you were looking at that graph.
So that is all we have on link list.
Let's get to the implementation details about these things.