In priority queue using a singly linked list problem, we need to implement a priority queue by using a singly linked list. A priority queue contains the following operations,
- push(x, p): Add an element x with priority p at an appropriate position in the priority queue.
- pop(): Remove and return the element with the highest priority
- peek(): Return the element with the highest priority
Table of Contents
Example
Input:
push(5, 2)
push(1, 3)
peek()
push(7, 5)
push(9, 1)
pop()
pop()
peek()
Output:
1
7
1
5
Algorithm for Priority Queue Using Singly Linked List
The idea is to maintain the linked list in descending order of priority so that the highest priority element is at the front.
push(x, p)
As the elements are arranged in descending order of priorities, so an element with priority p is inserted before the first element with a priority less than p, so that the order of priorities is not disturbed. Three cases arise,
- No element with priority less than p, add the new element at the end of the linked list.
- All the elements have priority less than p, add the new element at the start of the linked list.
- Some elements have priority less than p while others have priority more than p, add the new element before the first element having priority less than p.
Time Complexity = O(n)
Pseudo Code for Priority Queue Using Singly Linked List
- Make a new node with data = x and priority = p, let it be newNode
- If the head is null, this is the first node to be inserted, so make head = newNode and return.
- Create a node temp equals head and a node prev equals null.
- Find the first node with a priority less than p by running a loop while temp is not null and temp’s priority is greater than p. At every iteration, update prev as temp and temp as temp.next.
- After the end of the loop, if the temp is null, it means there is no node with a priority less than p, insert the newNode at the end of the linked list, that is, do prev.next = newNode.
- Else if prev is null, this implies that all the nodes are having priority greater than p. Do newNode.next = head and head = newNode.
- Else, insert the new node before temp, that is, do newNode.next = temp and prev.next = newNode.
pop()
The front of the linked list contains the highest priority element, remove it, and return.
Time Complexity = O(1)
peek()
The front of the linked list contains the highest priority element, return it.
Time Complexity = O(1)
JAVA Code for Priority Queue Using Singly Linked List
public class PriorityQueueUsingSinglyLinkedList {
// class representing node of a linked list
static class Node {
int data;
int priority;
Node next;
public Node(int data, int priority) {
this.data = data;
this.priority = priority;
}
}
// Variable representing the head of linked list
private static Node head = null;
private static void push(int x, int p) {
// Create a new node
Node newNode = new Node(x, p);
// If head is null, this is the first node to be added
// so make head = newNode
if (head == null) {
head = newNode;
return;
}
Node temp = head;
Node prev = null;
// search for first node having priority less than p
while (temp != null && temp.priority > p) {
prev = temp;
temp = temp.next;
}
if (temp == null) {
// no node with priority less than this node (Case 1)
prev.next = newNode;
} else {
if (prev == null) {
// all the nodes have priority less than p (Case 2)
// add this node at the starting
newNode.next = head;
head = newNode;
} else {
// Case 3
// add this node before the node with priority less than p
newNode.next = temp;
prev.next = newNode;
}
}
}
private static int peek() {
// head of the linked list contains the maximum priority element
if (head != null) {
return head.data;
}
return -1;
}
private static int pop() {
// head of the linked list contains the maximum priority element
if (head != null) {
int data = head.data;
// removing the highest priority element
head = head.next;
return data;
}
return -1;
}
public static void main(String[] args) {
// Example
push(5, 2);
push(1, 3);
System.out.println(peek());
push(7, 5);
push(9, 1);
System.out.println(pop());
System.out.println(pop());
System.out.println(peek());
}
}1 7 1 5
C++ Code for Priority Queue Using Singly Linked List
#include<bits/stdc++.h>
using namespace std;
// class representing a tree node
class Node {
public:
int data;
int priority;
Node *next;
Node(int d, int p) {
data = d;
priority = p;
next = NULL;
}
};
// function to create a new node
Node* newNode(int x, int p) {
Node *node = new Node(x, p);
return node;
}
// Variable representing the head of linked list
Node *head = NULL;
void push(int x, int p) {
// Create a new node
Node *node = newNode(x, p);
// If head is null, this is the first node to be added
// so make head = newNode
if (head == NULL) {
head = node;
return;
}
Node *temp = head;
Node *prev = NULL;
// search for first node having priority less than p
while (temp != NULL && temp->priority > p) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
// no node with priority less than this node (Case 1)
prev->next = node;
} else {
if (prev == NULL) {
// all the nodes have priority less than p (Case 2)
// add this node at the starting
node->next = head;
head = node;
} else {
// Case 3
// add this node before the node with priority less than p
node->next = temp;
prev->next = node;
}
}
}
int pop() {
// head of the linked list contains the maximum priority element
if (head != NULL) {
int data = head->data;
// removing the highest priority element
head = head->next;
return data;
}
return -1;
}
int peek() {
// head of the linked list contains the maximum priority element
if (head != NULL) {
return head->data;
}
return -1;
}
int main() {
// Example
push(5, 2);
push(1, 3);
cout<<peek()<<endl;
push(7, 5);
push(9, 1);
cout<<pop()<<endl;
cout<<pop()<<endl;
cout<<peek()<<endl;
return 0;
}1 7 1 5