# Priority Queue Using 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 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.

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

{
}

{
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()
{
// 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;
}

{
}

{
free(temp);
}

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

// Create new Node
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()
{

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

{
}

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()
```

This article tried to discuss the Implementation of Priority Queue Using Linked List. Hope this blog helps you understand the concept. To practice more problems feel free to check MYCODE | Competitive Programming at Prepbytes.