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.
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

Rhythm Jain
0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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.

## 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.
• 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.

### 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;
}
{
}
{
free(temp);
}
void push(Node** head, int d, int p)
{
Node* temp = newNode(d, p);
{
}
else
{
while (start->next != NULL &&
start->next->priority < p)
{
start = start->next;
}
temp->next = start->next;
start->next = temp;
}
}
{
}
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;
}``````

### 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.

### 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.

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!

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems