Table of contents
1.
Introduction
2.
Problem Statement
3.
Understanding The Question
4.
Approach
4.1.
Push() Operation
4.1.1.
Algorithm
4.2.
Pop() Operation
4.2.1.
Algorithm
4.3.
Top() Operation
4.3.1.
Algorithm
4.4.
Code
4.5.
Complexity Analysis
4.5.1.
Push() : O(N) 
4.5.2.
Pop() : O(1)
4.5.3.
Top() : O(1)
5.
Frequently Asked Questions
5.1.
Why the Time Complexity of Push() operation is O(N)?
5.2.
Which is more efficient, Linked List-based Priority Queue or Binary Heap-based Priority Queue?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Priority Queue Using a Linked List

Author Rhythm Jain
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Heap and Priority Queue

Introduction

While preparing for interviews, one of the most significant concepts and data structures to grasp is the linked list. A solid understanding of Linked Lists may be a great asset in a coding interview.

So Today, we will discuss a problem based on the Linked List and its implementation.

Check out A brief Introduction to Linked Lists

Problem Statement

We have to implement a Priority Queue using a Linked List data structure.

Understanding The Question

We know that in a Priority Queue (either min or max) we have three basic functions that are:

  1. push(): to insert a new value into the priority queue.
  2. pop(): to remove the element with the highest priority from the priority queue.
  3. top(): to get the highest priority element in the priority queue without removing it from the queue.

So our main area of focus is to implement these three functions using a linked List.

Also Read, Prefix Sum Array

Approach

So we will create a linked list with minor tweaks and changes such that we will be able to create a priority queue while maintaining the efficiency of the push(), pop(), and top() operations.

The List is constructed in such a manner that the element with the greatest priority is always at the head/front of the List. The components in the List are listed in descending order of priority. This allows us to delete the element with the greatest priority in O(1) time.

For the push() action, we must identify an appropriate location to insert the current node in order to maintain the overall order of the priority queue. This will take O(n) time to complete.

Push() Operation

In the push function, we must first determine the appropriate place for the value to be inserted. We must go down the list and identify the node with a lower priority than the present node. This will preserve the priority queue's declining order.

Algorithm

  • Make a new node.
  • If the current node's priority is higher than the priority of the head, insert at the beginning and make the current node point to the top of the List. Otherwise, in the decreasing order of their priority, identify the proper spot to insert the current node. We may accomplish this by iterating through the List.
  • After locating the right node, i.e. the node whose priority is lower than the new node's priority, make it ‘temp’ for the purpose of simplicity.
  • Insert the new node right before ‘temp’, as its priority is higher than ‘temp’.

Pop() Operation

We will just increment the head pointer such that the element at the top i.e.with topmost priority is deleted. We further need to free memory for that popped element.

Algorithm

  • Create a new node temp with the value head as its value.
  • Increment head as head=head->next.
  • To minimize memory leaks, we will now use free to release the memory allocated to temp (temp).
  • The free function deletes the node that was supplied to it from memory.

Top() Operation

We will simply return the head (The element with the highest priority).

Algorithm

As the head is the element with the highest priority, we will just return head->data.

See, Priority Queue Implementation Using Linked Lists

Code

#include <iostream>
#include <bits/stdc++.h>
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 top(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(1, 1);
   push(&pq, 2, 2);
   push(&pq, 3, 3);
   push(&pq, 4, 4);

   while (!isEmpty(&pq))
   {
       cout << " " << top(&pq);
       pop(&pq);
   }
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Complexity Analysis

Time Complexity

Push() : O(N) 

As List Traversal is Required.

Pop() : O(1)

Constant Operation

Top() : O(1)

Constant Operation

Space Complexity: O(N)

Linear Space is required to store elements in a List.

Must Read Python List Operations

Frequently Asked Questions

Why the Time Complexity of Push() operation is O(N)?

Time Complexity of Push() Operation is O(N) because in order to find an appropriate place for the new value to be inserted, we need to traverse the whole linked List which is O(N).

Which is more efficient, Linked List-based Priority Queue or Binary Heap-based Priority Queue?

It only really matters when the input is very large. For small size input, the difference is insignificant and we can use either of the Priority Queue. But if we're doing a large number of each operation, 𝑂(log𝑛)+𝑂(log𝑛)=𝑂(log𝑛) is asymptotically faster than 𝑂(𝑛)+𝑂(1)=𝑂(𝑛). So For a large number of operations, Heap-based Priority is more efficient than Linked List-based Priority Queue.

Conclusion

This is a very innovative technique to design a priority queue, and it is this aspect of the problem that makes it relevant for coding interviews.

If you wish to learn more about Linked List and solve additional Linked List problems curated by our professional mentors, click this link Linked List.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass