Priority Queue Using Singly Linked List

Difficulty Level Medium
Frequently asked in BrowserStack Hulu Mahindra Comviva Pocket Gems Soroco
Linked-List QueueViews 3589

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,

  1. push(x, p): Add an element x with priority p at an appropriate position in the priority queue.
  2. pop(): Remove and return the element with the highest priority
  3. peek(): Return the element with the highest priority

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,

  1. No element with priority less than p, add the new element at the end of the linked list.
  2. All the elements have priority less than p, add the new element at the start of the linked list.
  3. 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.

Priority Queue Using Singly Linked List

Time Complexity = O(n)

Pseudo Code for Priority Queue Using Singly Linked List

  1. Make a new node with data = x and priority = p, let it be newNode
  2. If the head is null, this is the first node to be inserted, so make head = newNode and return.
  3. Create a node temp equals head and a node prev equals null.
  4. 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.
  5. 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.
  6. Else if prev is null, this implies that all the nodes are having priority greater than p. Do newNode.next = head and head = newNode.
  7. 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

Reference1    reference2

Translate »