Implement queue using linked list

Implement Queue using linked list

In last Queue data structure , concept of queues and basic operations to be performed on it is explained. There we discussed queue implementation using array. Limitation in array based implementation is that allocation of array needs to be done before hand which restricts number of elements those can be accommodated. Other issue was to correctly gauge if queue is empty or full.  An extra counter is required for that. Today we will discuss how to implement queue using linked list. Advantage of linked list based approach is there is no pre-allocation of  size of queue. So queue is never full.

Queue using linked list

Check if queue is empty
Check head pointer of linked list, if head is NULL, queue is empty; if not, some elements are present in it.

Insertion in queue (enqueue)
Insertion into queue is done at the end or rear. Using singly linked list, traversal of entire list is required in order to add new node at end. This operation would be costly as O(N) and that is not desirable.Can we think of something else?

We can store tail pointer which points to last node of list. Or store last node pointer reference which points to next node of last node.  Initially, lastPtrPtr is set to head pointer which in turn is NULL to start with. To add node to list, directly go  to reference last pointer reference and add new node there. Update the last pointer reference. Implementation is shown below.

Deletion from queue (dequeue)
Deletion in queue is done at start. Remove the head node and then change head reference to point to next of head node. Done.


#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}
 
void enqueue(Node **lastPtrRef, Node *node){
	//Just add node at the end.
	(*lastPtrRef) = node;
}
 
Node *dequeue(Node **headRef){
 
	if(!(*headRef)) {
		printf("\n Queue is empty");
		return NULL;
	}
	Node *returnNode = *headRef;
	*headRef = (*headRef)->next;
 
	return returnNode;
 
}
void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
 
    printf("NULL");
    printf("\n");
}

/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        Node **lastPtrRef = &L1;
 
        enqueue(lastPtrRef, createNode(3));
        lastPtrRef = &((*lastPtrRef)->next);

        enqueue(lastPtrRef, createNode(2));
        lastPtrRef = &((*lastPtrRef)->next);

        enqueue(lastPtrRef, createNode(1));
        lastPtrRef = &((*lastPtrRef)->next);
 
        printList(L1);
 
        dequeue(&L1);
        printList(L1);
        return 0;
}

Array based implementation is good when we are sure that queue or stack will not increase continuously and would not cross maximum size at any given point of time. Also, array based implementation has all operations in constant time and memory usage is also low as compared to linked list base implementations. However, if queue/stack can increase beyond allocate size, dynamically increasing array size is quite an expensive operation.