Priority Queue using Doubly Linked List

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a set of nodes with their respective priority and our task is to implement a priority queue using a doubly linked list, which supports the following operations:

Operations

push(x, p): This function inserts an element x with priority p in the priority queue at the appropriate position.
pop(): This function removes and returns the element with the highest priority in the priority queue.
peek(): This function returns the element with the highest priority in the priority queue without removing it.

Now what we are going to do is, create a doubly linked list, but with a few tweaks such that the highest priority element will always be the head of the linked list. That means the list will be sorted in the descending order of the elements based on their priority. By doing this, we can do the peek() operation in O(1) time.

For the push() operation, we have to find a suitable position based upon the priority to insert the current node in the linked list so that the overall order of the priority queue is maintained. This will take O(n) time. Let us have a look at the approaches.

Now, let's implement these functions one by one.

push(x, p)

In push(x,p) operation to push an elemet x with priority p, we will have to first search for an appropriate position in the priority queue and then insert the element at that position.

The appropriate place to insert is just before the first element whose priority is less than p i.e. the priority of element we are inserting currently in push operation.

For example
If the priorityQueue:

Note: The first element inside brackets represents the data, and the second element represents priority.

  • If we want to push(6, 3), the appropriate place for (6,3) is just before (2,2).

Therefore, the priorityQueue after insertion is:

Algorithm

  • We will traverse the priority queue starting from the head node and find the first node whose priority is less than p.
  • One of the 3 cases is possible.
    1) There is no element whose priority is less than p. In this case, the new node will be inserted at the end of the priority queue.
    2) All the nodes have priority queue less than p. In this case, the new node will be inserted at the beginning of the priority queue.
    3) There are some nodes which have priority greater than p and some which have priority less than p. In this case, the new node will be inserted before the first node with priority less than p. This case is explained in the above example.

Dry Run

Code Implementation

//Implementing push function
void push(int data, int priority) {
    if (head == NULL) {
        Node *newNode = new Node(data, priority);
        head = newNode;
        return;
    }
    
    Node *node = new Node(data, priority);
   
    Node *temp = head;
    Node *parent = NULL;
    while (temp != NULL && temp->priority >= priority) {
        parent = temp;
        temp = temp->next;
    }
    
    // Case 1     
if (parent == NULL) {
        node->next = head;
        head->prev = node;
        head = node;
    }
    // Case 2 
    else if (temp == NULL) {
        parent->next = node;
        node -> prev = parent;
    }
    else {
        parent->next = node;
        node->prev = parent;
        node->next = temp;
        temp->prev = node;
    }
}

Time Complexity: O(n), as we need to make traversal to find the first node having priority less than the priority of the node which we are pushing.

pop()

The element with the highest priority will always be present at the beginning of the priority queue.

  • If the priority queue is not empty, we will delete the first element and return it, else it is impossible to pop.
  • Else do nothing and return -1.

Dry Run

Code Implementation

int pop() {
    
    if (head != NULL) {
        int curr = head->data;
        head = head->next;
        if (head != NULL) {
            head->prev = NULL;
        }
        return curr;
    }
    return -1;
}

Time Complexity: O(1), as the element which we are seeking is at the head of the priority queue, and we have a pointer to head.

peek()

The element with the highest priority will always be present at the beginning of the priority queue.

  • If the priority queue is not empty, we will have to return the first element of the priority queue as it is the element with the highest priority.
  • Else return -1.

Dry Run

Code Implementation

int peek() {
    
    if (head != NULL) {
        return head->data;
    }
    return -1;
}

Time Complexity: O(1), as the element which we are seeking is at the head of the priority queue, and we have a pointer to head.

Code Implementation:

#include 
using namespace std;

class Node {
    public:
    int data, priority;
    Node *next;
    Node *prev;
    
    Node(int d, int p) {
        data = d;
        priority = p;
        next = prev = NULL;
    }
};

Node *head = NULL;
void push(int data, int priority) {
    if (head == NULL) {
        Node *newNode = new Node(data, priority);
        head = newNode;
        return;
    }
    
    Node *node = new Node(data, priority);
   
    Node *temp = head;
    Node *parent = NULL;
    while (temp != NULL && temp->priority >= priority) {
        parent = temp;
        temp = temp->next;
    }
    
    // Case 1     
if (parent == NULL) {
        node->next = head;
        head->prev = node;
        head = node;
    }
    // Case 2 
    else if (temp == NULL) {
        parent->next = node;
        node -> prev = parent;
    }
    else {
        parent->next = node;
        node->prev = parent;
        node->next = temp;
        temp->prev = node;
    }
}
int peek() {
    
    if (head != NULL) {
        return head->data;
    }
    return -1;
}

int pop() {
    
    if (head != NULL) {
        int curr = head->data;
        head = head->next;
        if (head != NULL) {
            head->prev = NULL;
        }
        return curr;
    }
    return -1;
}
int main() {
    push(5, 2);
    push(1, 3);
    cout<

						 

Output

1
7
1
5

Time Complexity: O(N) for push operation, O(1) for pop operation, and O(1) for peek operation.
Space Complexity: O(N), where N is the total number of nodes.

So, in this article, you have learnt how to implement a priority queue using a doubly linked list. This is an important coding interview question. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Move all occurrences of an element to end in a linked list
Next post Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?

Leave a Reply

Your email address will not be published. Required fields are marked *