CEG's Linux User Group

IMPLEMENTATION OF A CIRCULAR QUEUE USING

LINKED LIST

INTRODUCTION:

We know that a linear queue is a “first in first out “ data structure,i.e., insertion can be made only at the end and deletion can be made only at the front. In a linear queue, the traversal through the queue is possible only once,i.e.,once an element is deleted,we cannot insert another element in its position.

This disadvantage of a linear queue is overcome by a circular queue, thus saving memory. In a circular queue, after rear reaches the end of the queue, it can be reset to zero. This helps in refilling the empty spaces in between.

A linked list is a data structure that consists of a sequence of nodes. Each node consists of two fields-information and address. The information part contains the value that the node holds. The address part contains the address of the next node. The last node contains NULL in the address part.

NODE 1                                        NODE 2                                         NODE 3

In a linked list, the nodes are logically connected but they may not be physically adjacent. This makes lists more advantageous than arrays where the data must be physically adjacent and at the same time logically connected. Here, nodes can be inserted and deleted at any point in the list unlike stacks, queues. But it is possible to implement a circular queue using a linked list.