CEG's Linux User Group

Article Index
LINEAR QUEUE IMPLEMENTATION USING LINKED LIST
Introduction
Source Code
Documentation
All Pages

Introduction :
The linear queue is a data structure characterised by the fact that additions are made at the end, or tail, of the queue while removals are made from the front, or head, of the queue. For this reason, a queue is referred to as a FIFO structure (First-In First-Out).
The efficient and quick way for implementing queue is through Linked List.

Linked List :
Linked list is one of the fundamental data structures which can be used to implement other data structures. Each node consists of two fields. The first field, known as the data field holds the value or data and the second field, known as the address field holds the reference to the next node or is assigned NULL(if the linked list is empty).The elements in the linked list are not stored continuously in the memory.



The simplest way of accessing the linked is through header(as through it is not necessary). The header node will be the first node contains NULL in the data part and hold the address of the first element in the address field.


Technical Terms In Queue :
1.Enqueue - Inserting an item in the queue.
2.Dequeue - Deleting an item in the queue.



Main Features of Linked List :

Structure :

The structure is the user defined data type. This can have different data type together. The structure definition will not occupy any bytes in the memory. But the structure variable will occupy the space in the memory. The structure member cannot be accessed independently. It can be accessed only through the structure variable.

• If the structure variable is not a pointer then we have to access the

members through dot operator.

• If the structure variable is a pointer then we have to access the members through arrow operator.

Typedef :
The typedef is the predefined function in c language. The function of typedef is to make the user defined data types. Even we can give different name for the primitive data types like integer, float and character. The syntax is as follows


So after declaring like this we can replace int by rollnumber.


malloc :
The malloc is the also predefined function in c. This function is used to allocate the memory in runtime. Some information will be available only during the runtime. In those cases this malloc function will be very useful.The return type of the malloc function is a pointer. We have to pass only one parameter(size) to this function. The syntax of this function is as follows.


Queue Using Linked List :
In Linked List everything is node. So memory will be allocated in runtime for those nodes. So during inserting(Enqueue) and deleting(Dequeue) new node will be created in the memory . In queue the insertion of node has to be taken place at the end while the deletion has to be done in the front (i.e. after header node) .We can remember the queue concept simply , the enqueue and dequeue should be taken place in the opposite end of the list (i.e. Enqueue in the end and dequeue in the front ). The main advantage of the implementing queue in the linked list is it never satisfies the overflow condition ( although we can restrict the enqueue by getting the maximum size of the array and pass that to enqueue function).

Model Of Queue(Linked List) :

Initially The Appearance Of Queue In Linked List :
Initially the list will contain header with NULL in the data and address field.



Enqueue :
Enqueue is nothing but inserting a node at the end of the List. The node is always going to be inserted at the end so in the inserting node the address part will always contains NULL.

Before Inserting a node :



After inserting a node :



Dequeue :
Deleting a node at the front of the list is called dequeue. Header in the list will contain the address of the first node. In that address part of the header node we have to delete the address of the first node and replace it with the address of the second node. This will result in the deletion of first node in the list

Before deleting the node :




After deleting the node :



Underflow:

Delete(dequeue) all elements in the queue will result in underflow condition. If the address field in the header contains NULL. Then the list is said to be empty .

 

< Prev		Next >