1.
Introduction
2.
Solution Approach
2.1.
Algorithm
2.2.
C++ Code
2.3.
Algorithm Complexity
3.
3.1.
3.2.
What is the key difference between a singly linked list and a doubly-linked list?
3.3.
How the elements are being pushed and popped into the implemented priority queue using a doubly linked list?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Priority Queue Using Doubly Linked List

Riya
0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## 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.

## 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.

### 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;
}``````

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

### 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### What is a linked list?

A linked list is a linear data structure that is formed by connected nodes. Each node has a value associated with it and the pointer(s) to its directly connected node(s).

### What is the key difference between a singly linked list and a doubly-linked list?

A singly-linked list is unidirectional, which means that the node of a singly-linked list contains the pointer to its next node only. In contrast, a doubly-linked list is bidirectional, and its node contains the pointer to its next and previous nodes.

### How the elements are being pushed and popped into the implemented priority queue using a doubly linked list?

In the priority queue, the element at the top should be having the least priority, so in the doubly linked list when we are inserting the element, we have to take care of that. That’s why when we are inserting the element in the doubly linked list, we are maintaining the elements in the increasing order of priority so that the first element of the linked list will be having the least priority. When the “pop()” function is called, then we are simply removing the first element of the linked list as it is having the least priority.

## Conclusion

This article discussed the implementation of a priority queue using a doubly-linked list, its C++ implementation, and its time and space complexities. If you want to practice problems on a linked list, then you can visit Coding Ninjas Studio - Library.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, All the best for your future endeavors, and Keep Coding.

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems