Data structures: Linked List implementation of Queue

In our previous lesson, we saw how we can implement queue using arrays. Now, In this lesson we’ll see how.


In our previous lesson, we saw how we can
implement queue using arrays. Now, In this lesson we’ll
see how we can implement queue using linked list. Queue as we know from our
previous discussions is a structure in which whatever goes in first comes out
first. Queue data strucuture is a list or
collection with this restriction that insertion can be
performed at one end and deletion can be performed at other
end. These are typical operations that we
defined with Queue. An insertion is called enqueue
operation and a deletion is called dequeue. Front operation
front function should simply return the element at
front of list and isempty should check whether queue is empty or
not and all these operations must a constant
time. There time complexity should be O(1). When we were implementing
queue with arrays, we used the idea of
circular array to implement Queue. Then in this case we have a limitation.
The limitation is that arary will always have a fixed size and
once all the positions in the array are taken once study is exhausted, we have two
options we can either deny insertion so we can say that the queue is full and
we cannot insert anything now, or what we can do is we can create a new
larger array and copy elements from previous array
to the new larger array, which will be a costly process. We can
avoid this problem if people use linked list to implement Queue. Please note that this represantaion
of circular array that i’m showing here is only a logical way of looking at
array. We can show this array like this also. As i was saying in an array
implementation, we will have this question what if array gets filled and we need to
take care of this. We can either say queue is full, or we can
create a new larger array and copy elements from previous filled
array into new larger array. The time taken for this copy operation
will be proportional to number of elements in filled array, or in other words
we can say that the time complexity of this copy operation will be O(N). There is another problem the array
implementation. We can have a large enough array and Queue
may not be using most of it. Like right now, in this array
90% of memory is unused. Memory is an important
resource and we should always avoid blocking memory
unnecessarily. It’s not that some amount of unused memory will be real problem in a modern-day machine. It’s just that
while designing solutions and algorithms, we should analyze and understand these
implications. Let’s now see how good we will be with
are linked list implementation. I have drawn logical view of a linked
list of integers here. Coming back to basic definition of Queue.
As we know, a queue is list or collection with
this constraint with this property, that an element must always be inserted from one side of the queue that we
call the rear of queue and an element must always be
removed from the other side that we call the
front of Queue. It’s really easy to enforce this
property in a linked list. A linked list as we know is a
collection of entities that we call nodes, and this nodes
are stored at non-contiguous locations in memory. Each node contains two fields, one to
store data and another to store address of the next node or
reference to the next node. Let’s assume that nodes in this figure
are at addresses 100 200 300 respectively. I have also filled in the address fields.
The identity of linked list that we always keep with us, is address
of the head node. We often named a pointer or reference
variable at which store this address head. Okay so now we are saying that we
want to use linked list to implement queue. These are the typical
operations that we define with a Queue. We can use a linked list like a
queue. We can pick one side for insertion or
enqueue operation. So node in the linked list must
always be inserted from this side. The other side will then be used for dequeue.
So if we are picking head side for enqueue operation, a dequeue must always happen from Tail, if
they are picking tail for equeue operation then dequeue
must always happen from head. Whatever side we’re picking
for whatever operation we need to be taking care of one
requirement and then the requirement is that, these operations
must a constant time, or in other words that there time
complexity must be O(1). As we know from our
previous lessons the cost of insertion or removal from head side is O(1), but the cost of insertion or removal from tail side is O(N). So here’s the deal, In a normal
implementation of linked list if we will insert at one side and
remove from other side then one of these operations enqueue or dequeue , depending on how we are picking the
side, will cost us O(N),but the requirement that we
have this that both these operations must take constant
time. So we definitely need to do something. To make sure that both enqueue and dequeue
operations take constant time, let’s call the side front and this side rear. So I want to enqueue a node from
this side and I want a dequeue from this side. We a good for dequeue operation because removal from front will take constant
time, but insertion or enqueue operation will be O(N). Let’s first see why
insertion at tail will be costly and then maybe we can try to do
something. To insert at rear end what we will have to do is, first
we will have to create a node. We have a new node here. Let’s say I’ve
got this node at address 350 and integer that i want to enqueue is 7. The address part of this node
can be set as null. Now what we need to do is we
need to build this link. We need to set the address part of the
last node as address of this newly created node, and to do so
we first need to have a pointer pointing to this last node storing the
address of this last node. In a linked list the only identity that
we always keep with us is address of the head node. To get appointed to any other node, we need
to start at head. So we will first create a pointer Temp and
we will initially set it to head, and Now in one step we can move this pointer variable to the next of
whatever node it is pointing to its pointing to. We use a statement like temp=temp->next
to move to the next node. So from first node we will go to the
second node and then from second we will go to the third node. In this
example, third node is the rear node, and now using this pointer temp we can
write the address part of this node and build this link. This whole traversal that we are
having to get a pointer from head to tail is what’s taking all the
time. What we can do is we can avoid this whole
traversal. We can have pointer variable just like head that should all the store
the address of rear node. I can call this variable tail or the rear. Let’s call this rear and
let’s call this variable that is storing the address of head node Front. In any insertion or removal and we will have to update both front
and rear now. But now when we will enqueue. Let’s say I’ve
got node at address 450 and I
want to insert this node at rear end. Now using the rear pointer
we can update to address field here. So we are
building this link and now we can update rear. We will only
have to modify some address fields and time taken for
enqueue operation will not depend upon number of nodes in the
linked list. So now with this design, both to enqueue
and dequeue operations will be constant time operations. The time
complexity for both will be O(1). Let’s quickly
see how real code in C will look like for this design. I have
declared node as a structure with two fields, one to
store data and another to store address of next node and now instead of declaring a pointer
variable named head, a pointer to node named head I am declaring two pointers, a pointer to
node named front and another pointer to node
named rear and initially I’m setting them both as
null. Let’s say i’m defining these two variable in global scope, so they will be accessible to all
functions. My enqueue function will take an integer as argument. In this function, i’ll first
create a node. I’ll use malloc in C or a new operator in C++ to create a node in what we call dynamic
memory. I’m pointing to the newly created node using this variable which is pointed to node named temp.
Now we can have two cases in insertion or enqueue operation. If there is no element in the queue, if
the queue is empty in this case both front and rear be
null. We will simply set both front and rear as address of
this new node being pointed to by temp and we will return or exit else we already
have pointer to rear node, we will first set the address part of
current rear as the address of this newly created
node and then we will modify the address and rear variable to make it point to this newly created
node. While writing all of this I’m assuming that
you are ready know how to implement a linked list. If you want to refresh your concepts, you
can check earlier lessons in the series or you can check the description of
this video for a link to lesson on linked list implementation in C or C++.
This code will be further the clear if I’ll show things moving in
a simulation. Let’s say, initially we have an empty queue
so both front and rear will be null. Null is only a macro for address Zero. At this stage let’s say we are
making a call to enqueue function passing it number 2. Now let’s go through the
enqueue function and see what will happen. First we will create a node. Data part
of this node will be set as 2 and address part initially will be set
as null. Let’s say we got this node at address temp
at address 100, so a variable name temp is storing this address. This variable is pointing to the this node.
Right now front and rear are both null, so we will go inside is if condition and
simply set both front and rear as 100. When the
function will finish execution temp which is a local variable will be
cleared from the memory. After setting both front and rear as
address of this newly created node we are returning. So this is how the queue will look like
after first enqueue. Let’s say we’re making another call to
enqueue function at this stage passing number 4 as argument. Once again a
new node will be created. Let’s say I got the new node at
address 200. This time queue is not empty so in this function we will
first go to this statement rear->next=temp, so they
will set the next part of this node at address 100 as the address of
the newly created node which is 200 so we will build
this link, and now they will store the address of the new rear node in this variable named rear. So this is
how my queue will look like after the second enqueue Let’s do one more enqueue. Let’s enqueue 6. Let’s say we got our new node this time
at address 300. So this is how our queue will look
like Okay! Let’s now write dequeue function. In dequeue
function, I’ll first create a temporary pointer to
node in which i’ll store the address of the current head
or current front Let’s say for this example at this stage,
I’m making a call to dequeue function. We will have couple of cases in dequeue also. The queue could be empty so in this case we
can print an error message and return. In
case of empty queue front and rear will both be equal to null. We can check one of these and we will be good. In the
case when front and rear will be equal. We will simply set both front and
rear as null. In all other cases we can simply
make front point to the next node. So we will simply do a
front=front->next but why have the used this temporary
pointer to node why have I declare this temporary pointer
to node in this code. Well simply incrementing front will not
be good enough. In this example i am calling dequeue. I’m
first creating temp. let’s walk through whatever
code i have written so far so in the first line i am creating temp and
then because queue it’s not empty and there are more than
one element in the queue. I am setting front as address of the next
node so my queue is good now. All the links
are appropriately modified but this node which
was front previously is still in the memory.
Anything in dynamic memory has to be explicitly
freed. To free this node we will
use free function and to this free function we should be
passing address of the node, and that’s why we had created temp. With this free the
node will be wiped off from memory. These are enqueue and dequeue operations for you
and if you can see there are simple statements in these functions. There are no loops so these functions
will take constant time. The time complexity will be O(1).
In the beginning of this lesson we had also discussed some limitations with array implementation like what if array gets
filled and that of unused memory. We do not have
these limitations in a linked list implementation. We’re using some extra memory to store
address of next node but apart from that there is
know what a major disadvantage I’ll stop here now. You can write rest of the
functions like front function, to look at the element at
front or isempty function to check whether queue is empty or not yourself. If you
want to get my source code then you can check the
description of this video for link. So thanks for watching.

Leave a Reply

Your email address will not be published. Required fields are marked *