Priority Queue using Linked List

Implement Priority Queue using Linked Lists. The Linked List should be so created so that the highest priority ( priority is assigned from 0 to n-1 where n is the number of elements, where 0 means the highest priority and n-1 being the least ) element is always at the head of the list. The list is arranged in descending order of elements based on their priority. The Priority Queue should have the below functions

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

Examples:

Input: Values = 4 (priority = 1), 5 (priority = 2), 6 (priority = 3), 7 (priority = 0)
Output: 7 4 5 6
Explanation: Values get peeked and popped according to their priority in descending order.

This approach manages a priority queue using a linked list. The PUSH operation inserts nodes in order of priority, ensuring the highest priority node is always at the head. The POP operation removes the highest priority node, while PEEK returns the data of the highest priority node without removing it.

Follow these steps to solve the problem

PUSH(HEAD, DATA, PRIORITY):

• Step 1: Create new node with DATA and PRIORITY 
• Step 2: Check if HEAD has lower priority. If true follow Steps 3-4 and end. Else goto Step 5. 
• Step 3: NEW -> NEXT = HEAD 
• Step 4: HEAD = NEW 
• Step 5: Set TEMP to head of the list 
• Step 6: While TEMP -> NEXT != NULL and TEMP -> NEXT -> PRIORITY > PRIORITY 
• Step 7: TEMP = TEMP -> NEXT 
  [END OF LOOP] 
• Step 8: NEW -> NEXT = TEMP -> NEXT 
• Step 9: TEMP -> NEXT = NEW 
• Step 10: End

POP(HEAD):

• Step 1: Set the head of the list to the next node in the list. HEAD = HEAD -> NEXT. 
• Step 2: Free the node at the head of the list 
• Step 3: End

PEEK(HEAD): 

• Step 1: Return HEAD -> DATA 
• Step 2: End

// C++ code to implement Priority Queue  // using Linked List #include <bits/stdc++.h> using namespace std; struct Node {  int data;  int priority;  Node* next;    Node(int x, int p) {  data = x;  priority = p;  next = NULL;  } }; // Return the value at head int peek(Node* head) {  // Return the data of the node at the head of the list  return head->data; } // Removes the element with the highest priority from the list Node* pop(Node* head) {  // Store the current head node in a temporary variable  Node* temp = head;  // Move the head to the next node in the list  head = head->next;  // Free the memory of the removed head node  delete temp;  // Return the new head of the list  return head; } // Function to push according to priority Node* push(Node* head, int d, int p) {  Node* start = head;  // Create new Node with the given data and priority  Node* temp = new Node(d, p);  // Special Case: Insert the new node before the head  // if the list is empty or the head has lower priority  if (head == NULL || head->priority > p) {  // Insert the new node before the head  temp->next = head;  head = temp;  }  else {  // Traverse the list to find the correct position  // to insert the new node based on priority  while (start->next != NULL &&  start->next->priority < p) {  start = start->next;  }  // Insert the new node at the found position  temp->next = start->next;  start->next = temp;  }  return head; } // Function to check if the list is empty int isEmpty(Node* head) {  return (head == NULL); } // Driver code int main() {  Node* pq = new Node(4, 1);  pq = push(pq, 5, 2);  pq = push(pq, 6, 3);  pq = push(pq, 7, 0);  while (!isEmpty(pq)) {  cout << " " << peek(pq);  pq = pop(pq);  }  return 0; } 

// C code to implement Priority Queue  // using Linked List  #include <stdio.h>  #include <stdlib.h>  typedef struct node {   int data;   int priority;   struct node* next;  } Node;  Node* newNode(int d, int p) {     Node* temp = (Node*)malloc(sizeof(Node));   temp->data = d;   temp->priority = p;   temp->next = NULL;   return temp;  }  // Return the value at head  int peek(Node* head) {  // Return the data of the node at the head of the list  return head->data;  }  // Removes the element with the highest priority from the list  Node* pop(Node* head) {  // Store the current head node in a temporary variable  Node* temp = head;     // Move the head to the next node in the list  head = head->next;     // Free the memory of the removed head node  free(temp);     // Return the new head of the list  return head;  }  // Function to push according to priority  Node* push(Node* head, int d, int p) {   Node* start = head;   // Create new Node with the given data and priority  Node* temp = newNode(d, p);   // Special Case: Insert the new node before the head  // if the list is empty or the head has lower priority  if (head->priority > p) {   // Insert the new node before the head  temp->next = head;   head = temp;   }   else {   // Traverse the list to find the correct position  // to insert the new node based on priority  while (start->next != NULL &&   start->next->priority < p) {   start = start->next;   }   // Insert the new node at the found position  temp->next = start->next;   start->next = temp;   }   return head;  }  // Function to check if the list is empty  int isEmpty(Node* head) {   return (head == NULL);  }  // Driver code  int main() {     Node* pq = newNode(4, 1);   pq = push(pq, 5, 2);   pq = push(pq, 6, 3);   pq = push(pq, 7, 0);   while (!isEmpty(pq)) {   printf("%d ", peek(pq));   pq = pop(pq);   }   return 0;  }  

// Java code to implement Priority Queue  // using Linked List  import java.util.* ;  class GfG {    static class Node {   int data;     int priority;     Node next;    }  static Node node = new Node();    // Function to Create A New Node  static Node newNode(int d, int p) {   Node temp = new Node();   temp.data = d;   temp.priority = p;   temp.next = null;     return temp;  }    // Return the value at head  static int peek(Node head) {   return (head).data;  }    // Removes the element with the  // highest priority from the list  static Node pop(Node head) {   (head) = (head).next;   return head;  }    // Function to push according to priority  static Node push(Node head, int d, int p) {     Node start = (head);     // Create new Node   Node temp = newNode(d, p);     // Special Case: The head of list has lesser   // priority than new node. So insert new   // node before head node and change head node.   if ((head).priority > p) {     // Insert New Node before head   temp.next = head;   (head) = temp;   }   else {     // Traverse the list and find a   // position to insert new node   while (start.next != null &&   start.next.priority <= p) {   start = start.next;   }     // Either at the ends of the list   // or at required position   temp.next = start.next;   start.next = temp;   }   return head;  }    // Function to check is list is empty  static int isEmpty(Node head) {   return ((head) == null)?1:0;  }    // Driver code  public static void main(String args[]) {   Node pq = newNode(4, 1);   pq =push(pq, 5, 2);   pq =push(pq, 6, 3);   pq =push(pq, 7, 0);     while (isEmpty(pq)==0) {   System.out.printf("%d ", peek(pq));   pq=pop(pq);   }    }  }  

# Python3 code to implement Priority Queue  # using Singly Linked List class PriorityQueueNode: def __init__(self, value, pr): self.data = value self.priority = pr self.next = None # Global variable for the front of the queue front = None # Method to check Priority Queue is Empty  def isEmpty(): return front is None # Method to add items in Priority Queue  # According to their priority value def push(value, priority): global front # Condition check for checking Priority # Queue is empty or not if isEmpty(): front = PriorityQueueNode(value, priority) return 1 else: # Special condition check to see that # first node priority value if front.priority > priority: newNode = PriorityQueueNode(value, priority) newNode.next = front front = newNode return 1 else: temp = front while temp.next: if priority <= temp.next.priority: break temp = temp.next newNode = PriorityQueueNode(value, priority) newNode.next = temp.next temp.next = newNode return 1 # Method to remove high priority item # from the Priority Queue def pop(): global front if isEmpty(): return else: front = front.next return 1 # Method to return high priority node  # value without removing it def peek(): if isEmpty(): return else: return front.data # Method to traverse the Priority Queue def traverse(): if isEmpty(): return "Queue is Empty!" else: temp = front while temp: print(temp.data, end=" ") temp = temp.next # Driver code if __name__ == "__main__": push(4, 1) push(5, 2) push(6, 3) push(7, 0) traverse() pop() 

// C# code to implement Priority Queue  // using Linked List  using System;  public class GfG {  public class Node {   public int data;   public int priority;   public Node next;  }  public static Node node = new Node();  static Node newNode(int d, int p) {   Node temp = new Node();   temp.data = d;   temp.priority = p;   temp.next = null;   return temp;  }  // Return the value at head  static int peek(Node head) {   return (head).data;  }  // Removes the element with the  // highest priority from the list  static Node pop(Node head) {   (head) = (head).next;   return head;  }  // Function to push according to priority  static Node push(Node head,   int d, int p) {   Node start = (head);   // Create new Node   Node temp = newNode(d, p);   // Special Case: The head of list   // has lesser priority than new node.   // So insert new node before head node   // and change head node.   if ((head).priority > p) {   // Insert New Node before head   temp.next = head;   (head) = temp;   }   else {   // Traverse the list and find a   // position to insert new node   while (start.next != null &&   start.next.priority <= p)   {   start = start.next;   }   // Either at the ends of the list   // or at required position   temp.next = start.next;   start.next = temp;   }     return head;  }  // Function to check is list is empty  static int isEmpty(Node head) {   return ((head) == null) ? 1 : 0;  }  // Driver code  public static void Main(string[] args) {   Node pq = newNode(4, 1);   pq = push(pq, 5, 2);   pq = push(pq, 6, 3);   pq = push(pq, 7, 0);   while (isEmpty(pq) == 0) {   Console.Write("{0:D} ", peek(pq));   pq = pop(pq);   }  }  }  

// JavaScript code to implement Priority Queue // using Linked List class Node {    constructor() {  this.data = 0;  this.priority = 0;  this.next = null;  } } var node = new Node(); function newNode(d, p) {  var temp = new Node();  temp.data = d;  temp.priority = p;  temp.next = null;  return temp; } // Return the value at head function peek(head) {  // Return the data of the node at the head of the list  return head.data; } // Removes the element with the highest priority from the list function pop(head) {  // Store the current head node in a temporary variable  var temp = head;  // Move the head to the next node in the list  head = head.next;  // Return the new head of the list  return head; } // Function to push according to priority function push(head, d, p) {  var start = head;  // Create new Node with the given data and priority  var temp = newNode(d, p);  // Special Case: Insert the new node before the head  // if the list is empty or the head has lower priority  if (head.priority > p) {    // Insert New Node before head  temp.next = head;  head = temp;  }   else {    // Traverse the list to find the correct position  // to insert the new node based on priority  while (start.next != null && start.next.priority <= p) {  start = start.next;  }  // Insert the new node at the found position  temp.next = start.next;  start.next = temp;  }  return head; } // Function to check if the list is empty function isEmpty(head) {  return head == null ? 1 : 0; } // Driver code var pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); while (isEmpty(pq) == 0) {  console.log(peek(pq) + " ");  pq = pop(pq); }     

7 4 5 6

Time Complexity: push() -> O(n) , To insert an element we must traverse the list and find the proper position to insert the node . This makes the push() operation takes O(n) time.

pop -> O(1), as it is performed in constant time.

peek -> O(1), as it is performed in constant time.

Space Complexity: O(n), as we are making a List of size n