# Priority Queue using doubly linked list

Given Nodes with their priority, implement a priority queue using doubly linked list.

Prerequisite : Priority Queue

Operations on Priority Queue :

• push(): This function is used to insert a new data into the queue.
• pop(): This function removes the element with the lowest priority value form the queue.
• peek() / top(): This function is used to get the lowest priority element in the queue without removing it from the queue.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach :
1. Create a doubly linked list having fields info(hold the information of the Node), priority(hold the priority of the Node), prev(point to previous Node), next(point to next Node).
2. Insert the element and priority in the Node.
3. Arrange the Nodes in the increasing order of the priority.

Below is the implementation of above steps :

## C++

 `// CPP code to implement priority ` `// queue using doubly linked list ` `#include ` `using` `namespace` `std; ` ` `  `// Linked List Node ` `struct` `Node { ` `    ``int` `info; ` `    ``int` `priority; ` `    ``struct` `Node *prev, *next; ` `}; ` ` `  `// Function to insert a new Node ` `void` `push(Node** fr, Node** rr, ``int` `n, ``int` `p) ` `{ ` `    ``Node* news = (Node*)``malloc``(``sizeof``(Node)); ` `    ``news->info = n; ` `    ``news->priority = p; ` ` `  `    ``// If linked list is empty ` `    ``if` `(*fr == NULL) { ` `        ``*fr = news; ` `        ``*rr = news; ` `        ``news->next = NULL; ` `    ``} ` `    ``else` `{ ` `        ``// If p is less than or equal front ` `        ``// node's priority, then insert at ` `        ``// the front. ` `        ``if` `(p <= (*fr)->priority) { ` `            ``news->next = *fr; ` `            ``(*fr)->prev = news->next; ` `            ``*fr = news; ` `        ``} ` ` `  `        ``// If p is more rear node's priority,  ` `        ``// then insert after the rear. ` `        ``else` `if` `(p > (*rr)->priority) { ` `            ``news->next = NULL; ` `            ``(*rr)->next = news; ` `            ``news->prev = (*rr)->next; ` `            ``*rr = news; ` `        ``} ` ` `  `        ``// Handle other cases ` `        ``else` `{ ` ` `  `            ``// Find position where we need to ` `            ``// insert. ` `            ``Node* start = (*fr)->next; ` `            ``while` `(start->priority > p)  ` `                ``start = start->next;             ` `            ``(start->prev)->next = news; ` `            ``news->next = start->prev; ` `            ``news->prev = (start->prev)->next; ` `            ``start->prev = news->next; ` `        ``} ` `    ``} ` `} ` ` `  `// Return the value at rear ` `int` `peek(Node *fr) ` `{ ` `    ``return` `fr->info; ` `} ` ` `  `bool` `isEmpty(Node *fr) ` `{ ` `    ``return` `(fr == NULL); ` `} ` ` `  `// Removes the element with the ` `// least priority value form the list ` `int` `pop(Node** fr, Node** rr) ` `{ ` `    ``Node* temp = *fr; ` `    ``int` `res = temp->info; ` `    ``(*fr) = (*fr)->next; ` `    ``free``(temp); ` `    ``if` `(*fr == NULL)  ` `       ``*rr = NULL; ` `    ``return` `res; ` `} ` ` `  `// Diver code ` `int` `main() ` `{ ` `    ``Node *front = NULL, *rear = NULL; ` `    ``push(&front, &rear, 2, 3); ` `    ``push(&front, &rear, 3, 4); ` `    ``push(&front, &rear, 4, 5); ` `    ``push(&front, &rear, 5, 6); ` `    ``push(&front, &rear, 6, 7); ` `    ``push(&front, &rear, 1, 2); ` ` `  `    ``cout << pop(&front, &rear) << endl; ` `    ``cout << peek(front); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java code to implement priority  ` `// queue using doubly linked list  ` ` `  `import` `java.util.* ; ` ` `  `class` `Solution ` `{ ` `   `  `static` `Node front , rear; ` `     `  `// Linked List Node  ` `static` `class` `Node {  ` `    ``int` `info;  ` `    ``int` `priority;  ` `     ``Node prev, next;  ` `} ` `   `  `// Function to insert a new Node  ` `static` `void` `push(Node fr, Node rr, ``int` `n, ``int` `p)  ` `{  ` `    ``Node news = ``new` `Node();  ` `    ``news.info = n;  ` `    ``news.priority = p;  ` `   `  `    ``// If linked list is empty  ` `    ``if` `(fr == ``null``) {  ` `        ``fr = news;  ` `        ``rr = news;  ` `        ``news.next = ``null``;  ` `    ``}  ` `    ``else` `{  ` `        ``// If p is less than or equal front  ` `        ``// node's priority, then insert at  ` `        ``// the front.  ` `        ``if` `(p <= (fr).priority) {  ` `            ``news.next = fr;  ` `            ``(fr).prev = news.next;  ` `            ``fr = news;  ` `        ``}  ` `   `  `        ``// If p is more rear node's priority,   ` `        ``// then insert after the rear.  ` `        ``else` `if` `(p > (rr).priority) {  ` `            ``news.next = ``null``;  ` `            ``(rr).next = news;  ` `            ``news.prev = (rr).next;  ` `            ``rr = news;  ` `        ``}  ` `   `  `        ``// Handle other cases  ` `        ``else` `{  ` `   `  `            ``// Find position where we need to  ` `            ``// insert.  ` `            ``Node start = (fr).next;  ` `            ``while` `(start.priority > p)   ` `                ``start = start.next;              ` `            ``(start.prev).next = news;  ` `            ``news.next = start.prev;  ` `            ``news.prev = (start.prev).next;  ` `            ``start.prev = news.next;  ` `        ``}  ` `    ``}  ` `    ``front =fr; ` `    ``rear=rr; ` `}  ` `   `  `// Return the value at rear  ` `static` `int` `peek(Node fr)  ` `{  ` `    ``return` `fr.info;  ` `}  ` `   `  `static` `boolean` `isEmpty(Node fr)  ` `{  ` `    ``return` `(fr == ``null``);  ` `}  ` `   `  `// Removes the element with the  ` `// least priority value form the list  ` `static` `int` `pop(Node fr, Node rr)  ` `{  ` `    ``Node temp = fr;  ` `    ``int` `res = temp.info;  ` `    ``(fr) = (fr).next;  ` `    ``if` `(fr == ``null``)   ` `       ``rr = ``null``;  ` `     `  `    ``front =fr; ` `    ``rear=rr; ` `       ``return` `res;  ` `     `  `}  ` `   `  `// Diver code  ` `public` `static` `void` `main(String args[])  ` `{  ` `     `  `    ``push(front, rear, ``2``, ``3``);  ` `    ``push(front, rear, ``3``, ``4``);  ` `    ``push(front, rear, ``4``, ``5``);  ` `    ``push(front, rear, ``5``, ``6``);  ` `    ``push(front, rear, ``6``, ``7``);  ` `    ``push(front, rear, ``1``, ``2``);  ` `   `  `    ``System.out.println( pop(front, rear));  ` `    ``System.out.println( peek(front));  ` `   `  `}  ` `} ` ` `  `// This code is contributed ` `// by Arnab Kundu `

## C#

 `// C# code to implement priority  ` `// queue using doubly linked list  ` `using` `System; ` ` `  `class` `GFG ` `{ ` `public` `static` `Node front, rear; ` ` `  `// Linked List Node  ` `public` `class` `Node ` `{ ` `    ``public` `int` `info; ` `    ``public` `int` `priority; ` `    ``public` `Node prev, next; ` `} ` ` `  `// Function to insert a new Node  ` `public` `static` `void` `push(Node fr, Node rr,  ` `                        ``int` `n, ``int` `p) ` `{ ` `    ``Node news = ``new` `Node(); ` `    ``news.info = n; ` `    ``news.priority = p; ` ` `  `    ``// If linked list is empty  ` `    ``if` `(fr == ``null``) ` `    ``{ ` `        ``fr = news; ` `        ``rr = news; ` `        ``news.next = ``null``; ` `    ``} ` `    ``else` `    ``{ ` `        ``// If p is less than or equal front  ` `        ``// node's priority, then insert at  ` `        ``// the front.  ` `        ``if` `(p <= (fr).priority) ` `        ``{ ` `            ``news.next = fr; ` `            ``(fr).prev = news.next; ` `            ``fr = news; ` `        ``} ` ` `  `        ``// If p is more rear node's priority,  ` `        ``// then insert after the rear.  ` `        ``else` `if` `(p > (rr).priority) ` `        ``{ ` `            ``news.next = ``null``; ` `            ``(rr).next = news; ` `            ``news.prev = (rr).next; ` `            ``rr = news; ` `        ``} ` ` `  `        ``// Handle other cases  ` `        ``else` `        ``{ ` ` `  `            ``// Find position where we  ` `            ``// need to insert.  ` `            ``Node start = (fr).next; ` `            ``while` `(start.priority > p) ` `            ``{ ` `                ``start = start.next; ` `            ``} ` `            ``(start.prev).next = news; ` `            ``news.next = start.prev; ` `            ``news.prev = (start.prev).next; ` `            ``start.prev = news.next; ` `        ``} ` `    ``} ` `    ``front = fr; ` `    ``rear = rr; ` `} ` ` `  `// Return the value at rear  ` `public` `static` `int` `peek(Node fr) ` `{ ` `    ``return` `fr.info; ` `} ` ` `  `public` `static` `bool` `isEmpty(Node fr) ` `{ ` `    ``return` `(fr == ``null``); ` `} ` ` `  `// Removes the element with the  ` `// least priority value form the list  ` `public` `static` `int` `pop(Node fr, Node rr) ` `{ ` `    ``Node temp = fr; ` `    ``int` `res = temp.info; ` `    ``(fr) = (fr).next; ` `    ``if` `(fr == ``null``) ` `    ``{ ` `        ``rr = ``null``; ` `    ``} ` ` `  `    ``front = fr; ` `    ``rear = rr; ` `    ``return` `res; ` `} ` ` `  `// Diver code  ` `public` `static` `void` `Main(``string``[] args) ` `{ ` `    ``push(front, rear, 2, 3); ` `    ``push(front, rear, 3, 4); ` `    ``push(front, rear, 4, 5); ` `    ``push(front, rear, 5, 6); ` `    ``push(front, rear, 6, 7); ` `    ``push(front, rear, 1, 2); ` ` `  `    ``Console.WriteLine(pop(front, rear)); ` `    ``Console.WriteLine(peek(front)); ` `} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output:

```1
2
```

Related Article :
Priority Queue using Singly Linked List

Time Complexities and Comparison with Binary Heap:

```               peek()    push()    pop()
-----------------------------------------
Linked List |   O(1)      O(n)      O(1)
|
Binary Heap |   O(1)    O(Log n)   O(Log n)```