{"id":4237,"date":"2021-08-24T12:24:38","date_gmt":"2021-08-24T12:24:38","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4237"},"modified":"2022-12-13T11:59:54","modified_gmt":"2022-12-13T11:59:54","slug":"priority-queue-using-doubly-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/priority-queue-using-doubly-linked-list\/","title":{"rendered":"Priority Queue using Doubly Linked List"},"content":{"rendered":"

\"\"<\/p>\n

Introduction<\/h3>\n

We have seen so many data types but in the below article we are going to learn about the abstract data type similar to a regular queue or stack in which each element is included with a priority of its own. Now, lets just look into the program for priority queue using doubly linked list<\/p>\n

Problem Statement for priority queue using doubly linked list<\/h3>\n

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:<\/p>\n

Operations<\/h4>\n

push(x, p):<\/strong> This function inserts an element x with priority p in the priority queue at the appropriate position.
\npop():<\/strong> This function removes and returns the element with the highest priority in the priority queue.
\npeek():<\/strong> This function returns the element with the highest priority in the priority queue without removing it.<\/p>\n

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()<\/strong> operation in O(1) time.<\/p>\n

For the push()<\/strong> 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.<\/p>\n

Now, let’s implement these functions one by one.<\/p>\n

push(x, p)<\/h3>\n

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.<\/p>\n

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.<\/p>\n

For example<\/strong>
\nIf the priorityQueue:<\/p>\n

\"\"<\/p>\n

Note:<\/strong> The first element inside brackets represents the data, and the second element represents priority.<\/p>\n

    \n
  • If we want to push(6, 3), the appropriate place for (6,3) is just before (2,2).<\/li>\n<\/ul>\n

    Therefore, the priorityQueue after insertion is:<\/p>\n

    \"\"<\/p>\n

    Algorithm for priority queue using doubly linked list<\/h3>\n
      \n
    • We will traverse the priority queue starting from the head node and find the first node whose priority is less than p. <\/li>\n
    • One of the 3 cases is possible.\n
        \n
      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.<\/li>\n
      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.<\/li>\n
      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.<\/li>\n<\/ol>\n<\/ul>\n

        Dry Run for priority queue using doubly linked list<\/h3>\n

        \"\"<\/p>\n

        Code Implementation for priority queue using doubly linked list<\/h3>\n\t\t\t\t\t\t