![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644922320273-93.Prority%20using%20lined%20list_Artboard%206.png\")
<\/p>\n<\/p>\n
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.<\/p>\n<\/p>\n
Here in this problem we will be implementing a priority queue using a linked list.<\/p>\n
There are 3 main operations in a priority queue:<\/p>\n
What we are going to do is, create a linked list, but with a few tweaks, the list will be created in such a way, 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.<\/p>\n
For the push() operation, we have to find a suitable position to insert the current node 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
In the push function, we have to first find the suitable position for the value to be inserted. We have to traverse through the list and find the node which has a lower priority than the current node. This is going to maintain the decreasing order of the priority queue. <\/p>\n
In the pop function, we will increment the head as head -> next. This will delete the head.<\/p>\n
The work of the peek function is to retrieve the highest priority element, without removing it from the queue. <\/p>\n
So, we will simply return the head -> data , as the head will always contain the highest priority element. <\/p>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/48_1-01.png\")
<\/p>\n