Priority Queue Using Doubly Linked List

Introduction

This article will discuss the implementation of a priority queue using a Doubly Linked List. Before jumping into the details of the implementation and its C++ code you need to know about the linked list and priority queue data structure.

Now, let’s understand what we have to do for the implementation of a priority queue using a doubly-linked list.

We will be given nodes with the following information:

1. data - value of the node
2. priority - priority of that node
3. next - pointer to the next node
4. prev - pointer to the previous node

Using these nodes, form a doubly-linked list and implement the following functions for the implementation of a priority queue using a doubly-linked list.:

1. push() - The function to insert a new element in the priority queue
2. pop() - The function to remove the element with the lowest priority value from the priority queue
3. peek() - The function to get the lowest priority element from the priority queue without removing the element from the priority queue.

Now we have understood what we need to do for the implementation of a priority queue using a doubly-linked list., we will discuss the approach and C++ code in the further sections.

Also see, Priority Queue Implementation using Linked Lists

Solution Approach

We have to write three different functions for the implementation of a priority queue using a doubly-linked list. As we can see that in functions “pop()” and “peek()”, we need to get the lowest priority element. In the “pop()” function, we have to remove the lowest priority element from the priority queue and in the “peek()” function, we have to return the lowest priority element without removing it from the priority queue. So, if we will arrange the nodes of the doubly linked list in ascending order of their priority value, the first node will be the one with the lowest priority, then we can implement the functions “pop()” and “peek()” in O(1) time complexity. For the “pop()” function, we will remove the first node and for peek(), we will return the data of the first node. 

Thus, we have to implement the “push()” function such that the nodes of the linked list will be in ascending order of their priority values. In the “push()” function, insert a node by finding its position in the linked list such that the nodes in the linked list will be in ascending order after insertion.

Also Read, Prefix Sum Array                                                                                

Algorithm 

Step 1. Create a class ‘Node’ for creating the doubly linked lists which will have variables to store the value of the node, priority value of the node, and a pointer to the previous and next nodes.

Step 2. Then create a function push() for inserting elements in the implementation of a priority queue using a doubly-linked list, which will take the following parameters:

1. first_ref: Pointer to the linked list first node’s pointer
2. last_ref: Pointer to the linked list last node’ pointer
3. data: The value which is to be inserted
4. priority_value: The priority value of the element which is to be inserted

It will insert the node in the linked list such that the linked list remains sorted according to its priority values. Create a while loop for finding the correct position and then insert the node at that position.

Step 3.  Create a function pop() for removing the element with the lowest priority value in the implementation of a priority queue using a doubly-linked list. As in push() function, we are maintaining the elements in ascending order of their priority values, so the first element will be having the lowest priority.

Step 4. Create a function peek() for getting the element with the lowest priority value in the implementation of a priority queue using a doubly-linked list. As in push() function, we are maintaining the elements in ascending order of their priority values, so the first element will be having the lowest priority.

C++ Code

// C++ code to implement priority queue using a doubly linked list
#include <bits/stdc++.h>
using namespace std;


// Node for creating doubly linked list
class Node {
public:
	int data;
	int priority;
	Node *prev;
	Node *next;
};


// Function for inserting a new node
void push(Node** first_ref, Node** last_ref, int data, int priority_value)
{
// Create the new node with given data and priority value
	Node* new_node = new Node();
	new_node->data = data;
	new_node->priority = priority_value;


// If linked list is empty, create a new doubly linked list with the new node as the first and last node
	if (*first_ref == NULL) {
		*first_ref = new_node;
		*last_ref = new_node;
		new_node->next = NULL;
	}
	else {
		/*
		                If priority_value is less than or equal first node's priority,
		                then insert at the beginning.
		 */
		if (priority_value <= (*first_ref)->priority) {
			new_node->next = *first_ref;
			(*first_ref)->prev = new_node->next;
			*first_ref = new_node;
		}
		/*
		                If priority_value is more last node's priority,
		                then insert at the end of the doubly linked list.
		  */
		else if (priority_value > (*last_ref)->priority) {
			new_node->next = NULL;
			(*last_ref)->next = new_node;
			new_node->prev = (*last_ref)->next;
			*last_ref = new_node;
		}
		else {
			/*
			    Finding position where we need to insert so that the
			     nodes in the linked list remain in ascending order of their priority values
			 */
			Node* temp = (*first_ref)->next;
			while (temp->priority > priority_value)
			{
				temp = temp->next;
			}

//Now after finding the suitable position, insert the new node
			(temp->prev)->next = new_node;
			new_node->next = temp->prev;
			new_node->prev = (temp->prev)->next;
			temp->prev = new_node->next;
		}
	}
}


// Function to return the data of the node with lowest priority value
int peek(Node* first)
{
	int lowestPriorityElement = first->data;
	return lowestPriorityElement;
}


// Function to check if the linked list is empty
bool isEmpty(Node* first)
{
	if (first == NULL)
	{
		return true;
	}
	return false;
}


// Function to remove the element with the lowest priority value
int pop(Node** first_ref, Node** last_ref)
{
	Node* temp = *first_ref;
	int lowestPriorityElement = temp->data;

	(*first_ref) = (*first_ref)->next;
	free(temp);

	if (*first_ref == NULL)
		*last_ref = NULL;
	return lowestPriorityElement;
}


int main()
{
// Pointer to the first node of the doubly linked list
	Node *first = NULL;

// Pointer to the last node of the doubly linked list
	Node *last = NULL;

// Call push() to insert nodes
	push(&first, &last, 4, 6);
	push(&first, &last, 7, 5);
	push(&first, &last, 9, 4);
	push(&first, &last, 5, 3);
	push(&first, &last, 8, 2);
	push(&first, &last, 3, 1);


	   // Call pop() to remove the element with lowest priority
	cout << "The element with the lowest priority which is removed is " << pop(&first, &last) << endl;

// Call peek() to get the element with lowest priority
	cout << "The element with the lowest priority is " << peek(first);


	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:
The element with the lowest priority which is removed is 3
The element with the lowest priority is 8

You can also try this code with Online C++ Compiler

Run Code

Algorithm Complexity

Time Complexity: 

The time complexity of the functions created for implementing priority queue using a doubly linked list.

1. push(): In this function for inserting an element, we have to traverse the linked list and find its correct position such that it remains sorted. So, the time complexity is O(N), where ‘N’ is the number of nodes in the doubly linked list.
2. pop(): In this function, we are just removing the first node of the linked list and returning its data value in constant time. So, the time complexity is O(1).
3. peek(): In this function, we are just returning the data value of the first node of the doubly linked list in constant time. So, the time complexity is O(1).

Space Complexity: O(N) 

As we are creating one node for each element we are inserting, So, the overall space complexity will be O(N) where ‘N’ is the number of elements inserted in the doubly linked list.