Priority Queue using a Linked List

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

Here in this problem we will be implementing a priority queue using a linked list.

Problem Statement Understanding

There are 3 main operations in a priority queue:

  • push() - to insert a new element into the queue.
  • pop() - to remove the highest priority element from the queue.
  • peep() - to retrieve the highest priority element, without removing it from the queue.

What we are going to do is, create a linked list, but with a few tweaks, the list will be created in such a way, that the highest priority element will always be the head of the linked list. That means the list will be sorted in the descending order of the elements based on their priority. By doing this, we can do the peek() operation in O(1) time.

For the push() operation, we have to find a suitable position to insert the current node so that the overall order of the priority queue is maintained. This will take O(n) time. Let us have a look at the approaches.

Approach(push)

In the push function, we have to first find the suitable position for the value to be inserted. We have to traverse through the list and find the node which has a lower priority than the current node. This is going to maintain the decreasing order of the priority queue.

Algorithm

  • Create a new node.
  • If the priority of the current node is greater than the head's priority, then insert at the beginning and make the current node the head of the list.
  • Else, find the appropriate position to insert the current node according to the descending order of their priorities. We can do this by traversing through the list.
  • After the appropriate node is found i.e. the node whose priority is lesser than the new node’s priority, store it in X, just for the sake of simplicity.
  • Now, insert the new node just before X, as the new node’s priority is greater than X.

Approach(pop)

In the pop function, we will increment the head as head -> next. This will delete the head.

Algorithm

  • Create a new node temp and its value will be the head.
  • Now, increment the head as head = head - > next. This will delete the current node.
  • Now, there is a memory leak. A memory leak happens when we remove the links of a node, but do not free it from the memory. Although the node is remove from the linked list, it still says in the memory.
  • To remove the memory leak, we can use the free method free(temp)
  • The free method remove the passed node from the memory.

Approach(peek)

The work of the peek function is to retrieve the highest priority element, without removing it from the queue.

So, we will simply return the head -> data , as the head will always contain the highest priority element.

Algorithm

  • Return head - > data, as the head will always contain the highest priority element.

Dry Run

Code Implementation

#include 
using namespace std;

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;
}

int peek(Node** head)
{
    return (*head)->data;
}

void pop(Node** head)
{
    Node* temp = *head;
    (*head) = (*head)->next;
    free(temp);
}

void push(Node** head, int d, int p)
{
    Node* start = (*head);

    Node* temp = newNode(d, p);

    if ((*head)->priority > p)
    {

        temp->next = *head;
        (*head) = temp;
    }
    else
    {

        while (start->next != NULL &&
            start->next->priority < p)
        {
            start = start->next;
        }

        temp->next = start->next;
        start->next = temp;
    }
}

int isEmpty(Node** head)
{
    return (*head) == NULL;
}

int main()
{

    Node* pq = newNode(3, 1);
    push(&pq, 2, 2);
    push(&pq, 1, 5);
    push(&pq, 4, 4);
 
    while (!isEmpty(&pq))
    {
        cout << " " << peek(&pq);
        pop(&pq);
    }
    return 0;
}
import java.util.* ;

public class Solution
{
    
static class Node {
    int data;
    

    int priority;
    
    Node next;
    
}

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;
}

static int peek(Node head)
{
    return (head).data;
}

static Node pop(Node head)
{
    Node temp = head;
    (head) = (head).next;
    return head;
}

static Node push(Node head, int d, int p)
{
    Node start = (head);
    

    Node temp = newNode(d, p);

    if ((head).priority > p) {
    

        temp.next = head;
        (head) = temp;
    }
    else {

        while (start.next != null &&
            start.next.priority < p) {
            start = start.next;
        }

        temp.next = start.next;
        start.next = temp;
    }
    return head;
}
    

static int isEmpty(Node head)
{
    return ((head) == null)?1:0;
}
    

public static void main(String args[])
{
    Node pq = newNode(3, 1);
    pq =push(pq, 2, 2);
    pq =push(pq, 1, 5);
    pq =push(pq, 4, 4);
    while (isEmpty(pq)==0) {
        System.out.printf("%d ", peek(pq));
        pq=pop(pq);
    }
}
}

Output

3 2 4 1

Time Complexity

peek() - O(1)
push() - O(n), as list traversal is needed.
pop() - O(1)

So, in this article, we have tried to explain the most efficient approach to implement a priority queue using a linked list. This is a very interesting way to implement a priority queue, and that is what makes this problem an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Find the largest node in a Doubly Linked List
Next post Recursively reversing a Linked List – A simple implementation

Leave a Reply

Your email address will not be published. Required fields are marked *