In: Computer Science
Show how circular linked list can be useful to implement Circular Queue (CQ) ADT (Abstract Data Type). Compare and contrast with array based implementation. Which one would you recommend to implement CQ and why
There are many differences in implementing CQ using either linked lists or arrays.
Firstly let us discuss the specific implementations and its advantages and disadvantages :
1. Implementation using circular linked lists
LinkedLists require connection of nodes to point to other
nodes.
Nodes contain a field to store data and one another field to store
the address of the next Node.
In this sense, implementation using it will require more space as
for every node the field to store next address is required.
Since, linked lists are dynamic , enuqueuing and dequeing
operations will be slow using this approach.
For enqueuing operation , a new node has to be created everytime
and assigned as rear node and linked to the front node.
The operation to create this node might slow down enqueuing
operation.
linked_Enqueuing()
{
if(front == null || rear == null)
{
create new node and assign front and rear node to them
}
else
{
create new node.
And make the last rear node point to this new node and reassign the
rear tag to the new node.
}
}
However, since linked lists are dynamic , we donot need to worry
about CQ becoming full in case of this approach.
We can always create a new node during enqueuing.
For dequeing operation , the node deletion might take sometime since memory has to be deallocated.
if(front != null)
{
assign the front tag to the next node of the front node.
delete the node which was previously first.(Deallocate memory in
this case)
}
2. Implementation using arrays
Arrays are predefined in size , hence , if the size that is
predefined is sufficient , using arrays will generally be faster in
the CQ for enqueuing and dequeuing operations since no memory
allocation/deallocation is required each time.
In case of arrays , we have to keep track of the front and rear
positions in the CQ.
arrays_enqueuing()
{
if(front == -1 and rear == -1)
{
front=rear = new_value;
}
else{
size_diff = positive difference of (rear - front)
if(size_diff+1 >= arrays_Size)
{
display("CQ is full")
or else , resize the CQ;
}
}
In case of arrays implementation , we need to take care if the
CQ has become full or not.
If the CQ has become full , then we cannot assign more elements to
the queue or we need to resize the whole array , which , in turn
will take more time.
So, arrays approach should be used where max CQ size is known/predictable so we can start with a sufficient size array , otherwise , frequent array resizing might slow down the CQ enqueuing operations.
In case of dequeuing, arrays approach works much faster , since
we just have to reassign the front to the next index.
There is no deallocation of memory in this approach , hence works
faster in this case.
All in all , it all depends on condition to
condition.
If CQ size is unpredictable and performance is not so much taken
care of , then CQ using linked lists is much better.
But, if CQ size is known or performance is of utmost, arrays should be used.