Priority Queue Using Doubly Linked List

Riya
Last Updated: May 13, 2022

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 do 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 pointer to the previous and next nodes.

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

  1. first_ref: Pointer to the linked list first node’ 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 remain sorted according to their 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 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 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: 

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 remain sorted. So, 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, time complexity is O(1).
  3. peek(): In this function, we are just returning data value of the first node of the doubly linked list in constant time. So, time complexity is O(1).

Space Complexity: O(N) 

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

 

Frequently asked questions-

  1. 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).   


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


3. How the elements are being pushed and popped in the implemented priority queue using 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.

 

Key takeaways-

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

 

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

 

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

Was this article helpful ?
0 upvotes