Tutorialspoint.dev

Priority Queue using doubly linked list

Given Nodes with their priority, implement a priority queue using doubly linked list.

Prerequisite : Priority Queue

    Operations on Priority Queue :

  • push(): This function is used to insert a new data into the queue.
  • pop(): This function removes the element with the lowest priority value form the queue.
  • peek() / top(): This function is used to get the lowest priority element in the queue without removing it from the queue.



Approach :
1. Create a doubly linked list having fields info(hold the information of the Node), priority(hold the priority of the Node), prev(point to previous Node), next(point to next Node).
2. Insert the element and priority in the Node.
3. Arrange the Nodes in the increasing order of the priority.

Below is the implementation of above steps :

C++

// CPP code to implement priority
// queue using doubly linked list
#include <bits/stdc++.h>
using namespace std;
  
// Linked List Node
struct Node {
    int info;
    int priority;
    struct Node *prev, *next;
};
  
// Function to insert a new Node
void push(Node** fr, Node** rr, int n, int p)
{
    Node* news = (Node*)malloc(sizeof(Node));
    news->info = n;
    news->priority = p;
  
    // If linked list is empty
    if (*fr == NULL) {
        *fr = news;
        *rr = news;
        news->next = NULL;
    }
    else {
        // If p is less than or equal front
        // node's priority, then insert at
        // the front.
        if (p <= (*fr)->priority) {
            news->next = *fr;
            (*fr)->prev = news->next;
            *fr = news;
        }
  
        // If p is more rear node's priority, 
        // then insert after the rear.
        else if (p > (*rr)->priority) {
            news->next = NULL;
            (*rr)->next = news;
            news->prev = (*rr)->next;
            *rr = news;
        }
  
        // Handle other cases
        else {
  
            // Find position where we need to
            // insert.
            Node* start = (*fr)->next;
            while (start->priority > p) 
                start = start->next;            
            (start->prev)->next = news;
            news->next = start->prev;
            news->prev = (start->prev)->next;
            start->prev = news->next;
        }
    }
}
  
// Return the value at rear
int peek(Node *fr)
{
    return fr->info;
}
  
bool isEmpty(Node *fr)
{
    return (fr == NULL);
}
  
// Removes the element with the
// least priority value form the list
int pop(Node** fr, Node** rr)
{
    Node* temp = *fr;
    int res = temp->info;
    (*fr) = (*fr)->next;
    free(temp);
    if (*fr == NULL) 
       *rr = NULL;
    return res;
}
  
// Diver code
int main()
{
    Node *front = NULL, *rear = NULL;
    push(&front, &rear, 2, 3);
    push(&front, &rear, 3, 4);
    push(&front, &rear, 4, 5);
    push(&front, &rear, 5, 6);
    push(&front, &rear, 6, 7);
    push(&front, &rear, 1, 2);
  
    cout << pop(&front, &rear) << endl;
    cout << peek(front);
  
    return 0;
}

Java

// Java code to implement priority 
// queue using doubly linked list 
  
import java.util.* ;
  
class Solution
{
    
static Node front , rear;
      
// Linked List Node 
static class Node { 
    int info; 
    int priority; 
     Node prev, next; 
}
    
// Function to insert a new Node 
static void push(Node fr, Node rr, int n, int p) 
    Node news = new Node(); 
    news.info = n; 
    news.priority = p; 
    
    // If linked list is empty 
    if (fr == null) { 
        fr = news; 
        rr = news; 
        news.next = null
    
    else
        // If p is less than or equal front 
        // node's priority, then insert at 
        // the front. 
        if (p <= (fr).priority) { 
            news.next = fr; 
            (fr).prev = news.next; 
            fr = news; 
        
    
        // If p is more rear node's priority,  
        // then insert after the rear. 
        else if (p > (rr).priority) { 
            news.next = null
            (rr).next = news; 
            news.prev = (rr).next; 
            rr = news; 
        
    
        // Handle other cases 
        else
    
            // Find position where we need to 
            // insert. 
            Node start = (fr).next; 
            while (start.priority > p)  
                start = start.next;             
            (start.prev).next = news; 
            news.next = start.prev; 
            news.prev = (start.prev).next; 
            start.prev = news.next; 
        
    
    front =fr;
    rear=rr;
    
// Return the value at rear 
static int peek(Node fr) 
    return fr.info; 
    
static boolean isEmpty(Node fr) 
    return (fr == null); 
    
// Removes the element with the 
// least priority value form the list 
static int pop(Node fr, Node rr) 
    Node temp = fr; 
    int res = temp.info; 
    (fr) = (fr).next; 
    if (fr == null)  
       rr = null
      
    front =fr;
    rear=rr;
       return res; 
      
    
// Diver code 
public static void main(String args[]) 
      
    push(front, rear, 2, 3); 
    push(front, rear, 3, 4); 
    push(front, rear, 4, 5); 
    push(front, rear, 5, 6); 
    push(front, rear, 6, 7); 
    push(front, rear, 1, 2); 
    
    System.out.println( pop(front, rear)); 
    System.out.println( peek(front)); 
    
}
  
// This code is contributed
// by Arnab Kundu

C#

// C# code to implement priority 
// queue using doubly linked list 
using System;
  
class GFG
{
public static Node front, rear;
  
// Linked List Node 
public class Node
{
    public int info;
    public int priority;
    public Node prev, next;
}
  
// Function to insert a new Node 
public static void push(Node fr, Node rr, 
                        int n, int p)
{
    Node news = new Node();
    news.info = n;
    news.priority = p;
  
    // If linked list is empty 
    if (fr == null)
    {
        fr = news;
        rr = news;
        news.next = null;
    }
    else
    {
        // If p is less than or equal front 
        // node's priority, then insert at 
        // the front. 
        if (p <= (fr).priority)
        {
            news.next = fr;
            (fr).prev = news.next;
            fr = news;
        }
  
        // If p is more rear node's priority, 
        // then insert after the rear. 
        else if (p > (rr).priority)
        {
            news.next = null;
            (rr).next = news;
            news.prev = (rr).next;
            rr = news;
        }
  
        // Handle other cases 
        else
        {
  
            // Find position where we 
            // need to insert. 
            Node start = (fr).next;
            while (start.priority > p)
            {
                start = start.next;
            }
            (start.prev).next = news;
            news.next = start.prev;
            news.prev = (start.prev).next;
            start.prev = news.next;
        }
    }
    front = fr;
    rear = rr;
}
  
// Return the value at rear 
public static int peek(Node fr)
{
    return fr.info;
}
  
public static bool isEmpty(Node fr)
{
    return (fr == null);
}
  
// Removes the element with the 
// least priority value form the list 
public static int pop(Node fr, Node rr)
{
    Node temp = fr;
    int res = temp.info;
    (fr) = (fr).next;
    if (fr == null)
    {
        rr = null;
    }
  
    front = fr;
    rear = rr;
    return res;
}
  
// Diver code 
public static void Main(string[] args)
{
    push(front, rear, 2, 3);
    push(front, rear, 3, 4);
    push(front, rear, 4, 5);
    push(front, rear, 5, 6);
    push(front, rear, 6, 7);
    push(front, rear, 1, 2);
  
    Console.WriteLine(pop(front, rear));
    Console.WriteLine(peek(front));
}
}
  
// This code is contributed by Shrikant13

Output:

1
2

Related Article :
Priority Queue using Singly Linked List

Time Complexities and Comparison with Binary Heap:

               peek()    push()    pop()
-----------------------------------------
Linked List |   O(1)      O(n)      O(1)
            |
Binary Heap |   O(1)    O(Log n)   O(Log n)


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter