Linked-List-Based Queues in C

Introduction

Queues are usually implemented using one of two structures: arrays or linked lists. This guide will focus on the latter.

If you haven't read my post on array-based queues, you might consider giving that a read before jumping into the linked-list variation!

Linked-List-Based Queues

As a reminder:

• enqueuing deals with tacking on a new node at the end of the queue

• dequeuing deals with removing the node at the front of the queue

Below is the implementation for two structs.

The first defines each node in the queue and the second stores the head and tail of each queue (each of which are made up of nodes).

// struct for each node in queue
typedef struct Node
{
	// basically a doubly linked list
	// TYPE data;
	int data;
	struct Node* next;
	struct Node* prev;
} node;

// struct for storing the first and last nodes in queue
// made up of nodes
typedef struct Queue
{
	node* head;
	node* tail;
} queue;

To help visualize this, here's an example of what a linked-list queue could look like... pretty similar to a doubly linked list!

With the basic structure out of the way, we can start writing functions that will perform operations on our queue.

Enqueuing

For enqueuing a new node...

// assume q is initialized with head and tail fields as NULL
void enqueue(queue* q, int val)
{
	// malloc space for a new node
	node* newNode = (node*) malloc(sizeof(node));
	if (newNode == NULL)
		return;
	
	// fill with value, next field to NULL, 
	// newNode prev field points to former tail
	newNode->data = val;
	newNode->next = NULL;
	newNode->prev = q->tail;
	
	// if queue has at least one element, set the previous tail's
	// next field to newNode
	if (queue->tail != NULL)
		queue->tail->next = newNode;
	
	// sets former tail to new tail
	q->tail = newNode;
	
	// if newNode is the first and last element, set head to newNode too
	if (q->head == NULL)
		queue->head = newNode;
}

Dequeuing

Now, for dequeuing the head node...

// assumes queue is not already empty
int dequeue(queue* q)
{
	// create a temp pointer to point to head of list
	// store data to return
	// move head to next field of head
	queue* temp = q->head;
	int data = temp->data;
	q->head = q->head->next;
	
	// if queue has more than 1 node, set prev field of head to NULL
	// if queue is empty, set tail to NULL
	if (q->head != NULL)
		q->head->prev = NULL;
	else
		q->tail = NULL;
	
	// free memory of the old head of the list
	free(temp);
	return data;
}

Final Thoughts

Hopefully this guide was helpful in understanding how queues can be applied to doubly linked lists. Thanks for reading!