Last Updated on May 26, 2023 by Prepbytes
A priority queue is a data structure that stores elements with associated priorities. It allows efficient insertion and removal of elements based on their priority values. One way to implement a priority queue is by using a linked list.
In a linked list-based implementation of a priority queue, each element is represented by a node that contains the actual data and a priority value. The nodes are linked together to form a linked list structure.
A priority queue using linked list offers flexibility in terms of efficient insertion and deletion operations. However, it may require linear time complexity for operations like insertion and deletion since finding the appropriate position or the element with the highest priority may involve traversing the linked list.
Priority Queue
Priority queue is an abstract data type, It is a type of queue in which each element has a priority assigned to it. The priority of the element determines the order in which elements are removed from the priority queue. In the priority queue, all the elements are arranged either in ascending order or descending order.
Priority Queue Properties:
- In the priority queue, every element has priority assigned to it.
- The element with highest priority first.
- If two elements are having the same priority then they are served according to their order in the queue.
Linked List
Linked list is a linear data structure just like arrays. In the linked list the elements are not stored in contiguous locations, the elements are connected or linked using pointers. Each node stores the data and the address of the next node.
- Data: The Data which is stored at the particular address.
- Reference: The address of the next node of the linked list.
Linked List Representation
Implementation using Linked List
The highest priority element will always be the head of the linked list. The list will be arranged in the descending order based on the priority of the elements due to which we can remove the highest priority element in O(1) time.
For inserting an element we have to traverse the list and find the proper position to insert the element so that the sequence of the priority queue will be maintained.
Algorithm
- Create a new node with data and priority.
- Check the priority with the head Node.
- If the head has lower priority, then connect the new node with the head and move the head pointer to the new node.
- Else traverse the priority queue and find the proper position of the new node.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
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()
{
// Create a Priority Queue
// 70->40->50->60
Node* pq = newNode(40, 1);
push(&pq, 50, 2);
push(&pq, 60, 3);
push(&pq, 70, 0);
while (!isEmpty(&pq)) {
printf("%d ", peek(&pq));
pop(&pq);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
// Node
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);
// Create new Node
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()
{
// Create a Priority Queue
// 70->40->50->60
Node* pq = newNode(40, 1);
push(&pq, 50, 2);
push(&pq, 60, 3);
push(&pq, 70, 0);
while (!isEmpty(&pq))
{
cout << " " << peek(&pq);
pop(&pq);
}
return 0;
}
import java.util.* ;
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[])
{
// Create a Priority Queue
// 70.40.50.60
Node pq = newNode(4, 1);
pq =push(pq, 5, 2);
pq =push(pq, 6, 3);
pq =push(pq, 7, 0);
while (isEmpty(pq)==0) {
System.out.printf("%d ", peek(pq));
pq=pop(pq);
}
}
}
class PriorityQueueNode:
def __init__(self, value, pr):
self.data = value
self.priority = pr
self.next = None
class PriorityQueue:
def __init__(self):
self.front = None
def isEmpty(self):
return True if self.front == None else False
def push(self, value, priority):
if self.isEmpty() == True:
self.front = PriorityQueueNode(value, priority)
return 1
else:
if self.front.priority > priority:
newNode = PriorityQueueNode(value, priority)
newNode.next = self.front
self.front = newNode
return 1
else:
temp = self.front
while temp.next:
if priority <= temp.next.priority:
break
temp = temp.next
newNode = PriorityQueueNode(value, priority)
newNode.next = temp.next
temp.next = newNode
return 1
def pop(self):
if self.isEmpty() == True:
return
else:
self.front = self.front.next
return 1
def peek(self):
if self.isEmpty() == True:
return
else:
return self.front.data
def traverse(self):
if self.isEmpty() == True:
return "Queue is Empty!"
else:
temp = self.front
while temp:
print(temp.data, end = " ")
temp = temp.next
if __name__ == "__main__":
pq = PriorityQueue()
pq.push(4, 1)
pq.push(5, 2)
pq.push(6, 3)
pq.push(7, 0)
pq.traverse()
pq.pop()
Conclusion for priority queue with linked list
In conclusion, a linked list-based implementation of a priority queue provides a flexible approach to managing elements with associated priorities. It allows efficient insertion and removal operations based on the priority values. However, it may have linear time complexity for certain operations due to the need for traversing the linked list to find the appropriate position or the element with the highest priority.
While there are more efficient data structures for larger priority queues, a linked list-based implementation can be suitable for smaller priority queues or situations that require dynamic resizing. It offers simplicity in terms of implementation and provides the ability to easily insert and remove elements in sorted order based on their priorities.
Ultimately, the choice of a data structure for implementing a priority queue depends on the specific requirements of the application, such as the expected size of the priority queue, the frequency of operations, and the desired time complexity.
Frequently Asked Questions related to priority queue with linked list
Q1. Can a linked list-based priority queue efficiently handle large priority queues?
Ans. A linked list-based priority queue may not be the most efficient choice for large priority queues. The time complexity of operations like insertion and deletion in a linked list can be linear, requiring traversing the list to find the appropriate position or the element with the highest priority. Other data structures like binary heaps or binary search trees are more efficient for larger priority queues.
Q2. What is the advantage of using a linked list-based priority queue over other data structures?
Ans. One advantage of a linked list-based priority queue is its flexibility. It allows for dynamic resizing and easy insertion and removal of elements. It can be a suitable choice for smaller priority queues or situations where elements need to be kept in a sorted order based on their priorities.
Q3. Does a linked list-based priority queue preserve the order of equal priority elements?
Ans. In a linked list-based implementation, the order of equal priority elements is typically preserved. When inserting elements with the same priority, they are placed in the order of their arrival. The first element to be inserted among elements with the same priority will be positioned closer to the head of the linked list.
Q4. How can the efficiency of a linked list-based priority queue be improved?
Ans. To improve the efficiency of a linked list-based priority queue, one approach is to use a doubly linked list. This allows for the efficient removal of elements by maintaining references to both the previous and next nodes. Another improvement can be achieved by keeping the linked list sorted based on priorities, which can speed up the insertion process. However, for significant efficiency gains, other data structures like binary heaps or binary search trees are generally preferred.
Q5. Can a linked list-based priority queue handle elements with dynamically changing priorities?
Ans. Yes, a linked list-based priority queue can handle elements with dynamically changing priorities. If the priority of an element changes, it can be removed from its current position in the linked list and reinserted at the appropriate position based on the updated priority value.
Q6. Does a linked list-based priority queue support efficient searching for a specific element?
Ans. A linked list-based implementation does not offer efficient searching for a specific element. To find a specific element, you would need to traverse the linked list and compare the element values. Other data structures like hash-based structures or binary search trees provide better search performance.