Hi everyone.
Welcome to this Data Structures Crash course where we are going to discuss linked lists.
Now in this video these are the three things that we will discuss.
First let's try to understand singly linked lists and doubly linked lists.
Then we will see how these are stored in memory.
And then we will analyze the Big-O of common linked list operations.
So let's get started with point number one.
First we are going to try to understand singly linked lists.
Now these are data structures that look like this.
So you can see that over here you have nodes.
All right.
So this is an example of a node.
And every node has a value.
So for example this node has the value seven.
And then it also has a pointer to the next node over here.
Now the value in a node can be anything.
It can be an integer a string or an array or anything.
All right.
So you have nodes over here.
And every node has a value and a pointer to the next node.
So this is how a singly linked list looks like.
And then in the case of a singly linked list the first node is called the head.
And the last node is called the tail.
All right.
Now let's say you want to come to this node over here which has the value nine for a singly linked list.
All right.
Now if you want to access this node or this value you cannot come directly over here as was the case
in the case of an array.
Right.
So if you know the index then you can come directly to the value at a particular index in an array.
But in the case of a singly linked list, you can't do that because we are only tracking the head and
the tail and there are no indices over here.
So what you would have to do is you would have to first access the head.
And then from the head, you have to keep traversing the nodes till you reach the node that you want
to access.
So you come over here, then over here.
Now that's what we call a singly linked list.
All right.
So this is an introduction to singly linked lists.
So we have seen that these are data structures that have a head and a tail.
So these are properties for this data structure.
And then we also can track the length of the singly linked list.
Now we have seen that when we implement singly linked lists or anything any data structure as a class
it can have properties and methods.
Right.
So these are going to be the properties of any singly linked list.
And then methods is what we will discuss over here, which is things like adding to the linked list
or removing from the linked list etc..
All right.
Now let's proceed.
And let's take a look at what is a doubly linked list.
Now, a doubly linked list is pretty similar to a singly linked list.
The only difference is that you can see over here there is an extra pointer.
So there is an extra pointer which points to the previous node as well.
All right.
So that's the only difference.
All right.
And again the first node is called the head.
And the last node is called the tail.
For a doubly linked list as well.
All right.
So that's a singly linked list and a doubly linked list.
Now let's take a look at how linked lists are stored in memory.
Now that's something that differentiates a linked list from an array.
All right.
Now we have seen that previously.
In the case of an array we need memory slots back to back to store an array.
But in the case of a linked list we don't need back to back memory slots.
We just can store them anywhere.
All right.
Now for every node, memory slots will be used up to store the value of that particular node and to
store the pointers.
Now I have pointers over here because in the case of a singly linked list, we only have the next pointer.
But in the case of a doubly linked list we also have the previous pointer.
So again we will take we will make use of this when we discuss the big O of common linked list operations.
So let's proceed and take a look at point number three.
First we take a look at big O of common singly linked list operations.
So this deals with singly linked lists.
Now if you want to insert into a singly linked list.
So let's take a look at that over here.
Now for this let's take an example.
So I have this singly linked list over here 753.
And then it's pointing to null.
Now let's say you want to insert at the beginning.
So for this you just need to create a new node with the value.
So let's say you want to insert a node with value eight.
So you have that node over here.
So you have to create this node.
And you need to make this node point to the previous head.
And then you have to make this node over here the new head.
So that's it.
So you can see this is a constant space and time operation.
And no indexing is involved over here.
Right.
If you remember we have discussed that we don't need back to back memory slots.
So making this the head does not involve shifting these nodes over here in memory.
So that's why this is a constant time and space operation.
Again we don't use any extra or auxiliary space.
So that's why this is constant space as well.
Now let's take a look at inserting a new value at the end.
Now if you want to do this, all that you need to do is you need to create a new node with the value.
Let's say you want to insert a node with value four.
So you have to create a new node with that particular value.
And then you need to make the previous tail which is this node over here point to the new node.
And then you have to make the new node the tail.
All right.
So this also you can see is a constant space and time operation.
Again note this will be constant time only if you're storing the tail.
Now you can store the tail as one of the properties of the singly linked list.
And it will depend on how you write your class.
Now, if you are not storing the tail, then you would have to traverse from the head till the tail.
So in that case it would be a o of n time operation.
Again, it's constant space because we are not using any auxiliary or extra space.
Now if you want to insert in between somewhere in between the head and the tail, then you would have
to create a new node with that particular value.
And then you have to identify the previous node and the next node.
Right.
So let's say you want to insert between these two.
So this is the previous node and this is the next node.
Now you have to make this node over here point to the new node.
And then the new node has to point to the next node.
All right.
So this is how you would insert in between.
And in this case it's going to be an O of X operation with respect to time and a constant space operation.
Now it's O of X over here because you have to traverse to the previous node.
Right.
Let's say you want to insert over here.
So you have to start from the head.
And then you have to traverse to seven.
And you have to identify the previous node.
So there is some traversing involved over here.
So that's why this is a O of X time operation.
And then we are not using any extra or auxiliary space because of which this is going to be constant
space.
Now let's go ahead and take a look at removing from the singly linked list.
Now let me just clean this up a little bit.
All right.
Now, first we take a look at removing from the beginning.
If you want to remove from the beginning, right.
All you have to do is you have to make the next node, which is this one over here, the head.
Right.
So if you make this the head then we are losing this.
And in that way you have removed from the beginning.
So you can see this is a constant time operation.
Because no matter how big the singly linked list is, it's just going to be the same number of operations.
Right.
So it's constant number of operations.
We don't need to traverse the singly linked list.
And hence removing from the beginning is constant time and constant space.
It's constant space because we are not using any auxiliary space.
Now if you want to remove from the end, you can see that it's O of n time and constant space.
Now, even though we track the tail right, we are tracking the tail as a property.
Even then it's o of n time complexity because we have to identify the previous node, right?
For example, if you want to remove this, we have to traverse from the head till the previous node
to identify the previous node.
And then we can make the previous node point to null.
And in that way remove the last node.
So traversing to the previous node is going to be an O of n operation.
Right.
So and then we just have to set this to the tail.
So that's why this is an O of N operation.
All right.
So this is something which is different when we compare singly linked lists and doubly linked lists,
which is something that we will soon see.
All right.
Now let's proceed.
And if you want to remove in between again it's going to be an O of X time operation because you have
to traverse the node right.
So you have to traverse the singly linked list.
For example if you want to remove this node over here you have to reach till this node.
And then you have to disconnect this connections, these two connections.
And you have to make this node point to this one over here.
So you have to establish this connection.
So so the point is that you have to traverse the singly linked list.
So you have to start from the head.
Let's say this is the head.
So you have to start traversing from the head and come to the previous node.
So identify it.
And then you have to identify the next node.
And you have to make the previous node point to the next node.
In this way you're actually deleting this node over here.
So again it involves traversing the singly linked list.
And that's why this is an O of X time operation.
All right.
Now let's proceed.
Now if you want to access the X node again this is just an index.
So in this case again you have to keep traversing the singly linked list from the head till the x node.
So that's why this is an O of x time operation.
And we are not using any auxiliary space because of which this is an O of one or a constant space operation.
Now similarly, if you want to set the value of the x node, you have to access that node first, and
then it's a constant time operation to change the value.
So that's why this is again O of X time complexity and constant space complexity.
Now if you want to copy a singly linked list and create a new singly linked list, that's O of n time
and space again, it's taking O of n space because you are creating a new copy of the singly linked
list, right.
Which has n elements.
And then to copy the elements you have to traverse the given singly linked list as well.
So that's why the time complexity over here is O of N.
Now to traverse and search for an element in a singly linked list.
In the worst case is going to be O of n, so the time complexity is O of n and the space complexity
is O of one.
Because we are not using any extra space.
Now, the time complexity is O of n, because the value for which you are searching in the worst case
can be the last node, right?
And then this is pointing to let's say null.
And again it could be the second last also.
So let's say you're saying that we are already tracking the tail.
Yes.
If you build in that check you can check the head and you can check the tail.
And if the value is not equal to the value of these two, then let's say it's over here.
The value is over here for which you are searching.
You would have to traverse the singly linked list starting from here till here.
So that's going to be almost N operations because of which this is an O of n time complexity operation.
All right.
So we are done with common operations for a singly linked list.
Now let's take a look at common operations for a doubly linked list.
Now if you compare the operations for singly linked list and doubly linked list, you will see that
it's almost the same.
So when it comes to inserting, it's the same in all the three cases, which is inserting at the beginning,
at the end and in between.
Now when it comes to removing, you will see that it's different when you remove from the end.
So let's say you have a doubly linked list over here.
And if you want to remove the tail, if this was a singly linked list we have already seen this is an
O of N time operation because we have to traverse the array to identify the previous node.
But in the case of a doubly linked list you we have this connection, right.
So we have this connection.
So we can just start at the tail and then move one back.
So that's why this is going to be a constant time operation for a doubly linked list.
And then all the other operations are just the same as the case was for a singly linked list.