Question

In: Computer Science

Show how circular linked list can be useful to implement Circular Queue (CQ) ADT (Abstract Data...

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

Solutions

Expert Solution

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.


Related Solutions

In C++, Implement the queue ADT with a singly linked list
In C++, Implement the queue ADT with a singly linked list
One way to implement a queue is to use a circular linked list. In a circular...
One way to implement a queue is to use a circular linked list. In a circular linked list, the last node’s next pointer points at the first node. Assume the list does not contain a header and that we can maintain, at most, one iterator corresponding to a node in the list. For which of the following representations can all basic queue operations be performed in constant worst time? Justify your answers. Maintain an iterator that corresponds to the first...
Using the linked list abstract data type “Queue ADT”, write a menu dirven user interfece to...
Using the linked list abstract data type “Queue ADT”, write a menu dirven user interfece to teach each of the operations in the ADT. Any errors discovered during the processing should be printed as a part of the test result. Please Use C++ language.
JAVA: Implement a Queue ADT using a circular array with 5 string elements. Create a Queue...
JAVA: Implement a Queue ADT using a circular array with 5 string elements. Create a Queue object and try various operations below. Queue myQueue = new Queue(); myQueue.enqueue(“CPS 123”); myQueue.enqueue(“CPS 223”); myQueue.enqueue(“CPS 323”); myQueue.dequeue(); myQueue.enqueue(“CPS 113”); myQueue.enqueue(“CPS 153”); string course = myQueue.front(); // course should be CPS 223 size = myQueue.size(); // size should be 4 // output course and size
Task 3: Implement a queue through circular linked list. Develop enqueue, dequeue, status, isempty and isfull...
Task 3: Implement a queue through circular linked list. Develop enqueue, dequeue, status, isempty and isfull functions. Test your code in main function with 10 elements Note: for each task, you are supposed to create three files as specified in task1, i.e., implementation file, interface file and file containing point of entry. in C++
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you will implement the functionality of a stack and a queue using a linked list. Your program must use of the declaration of the Stack and Queue class in Stack.h and Queue.h You have to implement the functionalities of queue (enq, deq, displayQueue) in a file called Queue.cpp. All the functions in Queue.cpp should follow the prototypes declared in Queue.h. Your code should make use...
implement the Queue ADT using the linked list approach #include "QueueLinked.h" template QueueLinked::QueueNode::QueueNode(const DataType& nodeData, QueueNode*...
implement the Queue ADT using the linked list approach #include "QueueLinked.h" template QueueLinked::QueueNode::QueueNode(const DataType& nodeData, QueueNode* nextPtr) { } template QueueLinked::QueueLinked(int maxNumber = Queue::MAX_QUEUE_SIZE) { } template QueueLinked::QueueLinked(const QueueLinked& other) { } template QueueLinked& QueueLinked::operator=(const QueueLinked& other) { } template QueueLinked::~QueueLinked() { } template void QueueLinked::enqueue(const DataType& newDataItem) throw (logic_error) { } template DataType QueueLinked::dequeue() throw (logic_error) {    DataType temp;    return temp; } template void QueueLinked::clear() { } template bool QueueLinked::isEmpty() const {    return false; } template...
can someone explain to me circular, double, linked list? can someone show a program on how...
can someone explain to me circular, double, linked list? can someone show a program on how you would go about using recursive with proper functions and one not using recursive but somethibg simikar! bibary search tree, preorder, post order? good explanation of linked list sorted.
Write a C program to implement a queue (FIFO) of characters in a one-way, circular, linked...
Write a C program to implement a queue (FIFO) of characters in a one-way, circular, linked list. One way means that each node has only one pointer, Q, (not both a rear and a front pointer), so the program must use pointers-to-pointers. Include functions to insert(), remove(), for use in main() where the user is prompted "Enter "i" to insert a new element, "r" to remove an element, "q" to quit:"
26.5 Project 3: List & Queue ADT Overview For this project, you are to implement two...
26.5 Project 3: List & Queue ADT Overview For this project, you are to implement two abstract data types (ADTs). You will write a doubly linked list (Dll) and a queue class. The queue will use the dll internally. The class interfaces are downloadable below. You must follow the interface exactly. While you can define other public and private methods and fields, the class names and methods given must appear as provided, or you will not pass the unit tests....
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT