Priority Queue Implementation using unordered Linked List

Linked List implementation can be the preferred choice for Priority Queue when the application uses dynamic data. The unordered form is especially required for Applications that require faster insertion. However, the deletion will be slower since it requires a search to find the priority data.

• See Priority Queue Implementation using ordered Linked List to perform deletions faster.
• Alternatively, see Priority Queue Implementation using Array to work with static data.

1. Representation

The elements are enqueued in the order of 10, 20, and 30 and they are stored as per their arriving order.

/**
 * Queue Node Representation
 */
 struct Node {
     int element;
     int priority; // Lowest number indicates high priority
     Node* next;
 };

// Queue front pointer
Node* front = NULL;

2. Priority Queue Implementation using unordered Linked List

/**
 * C++ example to demonstrate the Priority Queue implementation using unordered Linked List
 */
#include <iostream>
using namespace std;

/**
 * Queue Node Representation
 */
 struct Node {
     int element;
     int priority; // Lowest number indicates high priority
     Node* next;
 };

/**
 * Priority Queue implementation using unordered Linked List
 */
class PriorityQueue
{
private:
    // Queue front pointer
    Node* front;
    
public:
    // Constructor
    PriorityQueue() : front(NULL) {}

    // Enqueue new element to Queue
    void enqueue(int element, int priority);

    // Dequeue an element from Queue
    int dequeue();

    // Returns the top element without deleting
    int peek();

    // Print the Queue
    void display(string msg);

    // Check if the Queue is empty
    bool isEmpty();
};

// Enqueue new element to Queue
void PriorityQueue::enqueue(int element, int priority) {
    // Step 1: Create the new node with priority
    Node* node = new Node();
    if (node == NULL) {
        cout << "System out of memory" << endl;
        return;
    }
    node->element = element;
    node->priority = priority;
	
    // Step 2: Connect the new node at Front
    
    // Link the new node to point the Front
    node->next = front;
	
	// Set the Front to point the new node
    front = node;
}

// Dequeue an element from Queue
int PriorityQueue::dequeue() {
    // Step 1. Check if the Queue is empty
    if (front == NULL) {
        return -1;
    }
    
    // Step 2. Iterate the list and find the element with highest
    // priority. Store the reference to its previous node required
    // for deletion
    Node* highNode = front;
    Node* prevNode = NULL;
    for (Node *prev = front, *it = front->next; it != NULL; prev = it, it = it->next) {
        if (it->priority <= highNode->priority) {
            highNode = it;
            prevNode = prev;
        }
    }
    
    // Step 3. Retrieve the high priority element
    int element = highNode->element;
    
    // Step 4. Check if the highest priority element is at Front
    if (highNode == front) {
        // Step 5. If true, change the Front and delete the node
        front = highNode->next;
        delete highNode;
        
    } else {
        // Step 6. Else, delink the high priority node by directly
        // connecting its previous and next node and delete it.
        prevNode->next = highNode->next;
        delete highNode;
    }
    
    return element;
}

// Returns the top element without deleting
int PriorityQueue::peek() {
    if (isEmpty()) {
        return -1;
    }
    Node* highNode = front;
    for (Node *it = front->next; it != NULL; it = it->next) {
        if (it->priority < highNode->priority) {
            highNode = it;
        }
    }
    return highNode->element;
}

// Print the Queue
void PriorityQueue::display(string msg) {
    cout << msg << endl;
    if (isEmpty()) {
        return;
    }
    
    cout << front->element << " (" << front->priority << ")" << " <-- front" << endl;
    for (Node* node=front->next; node != NULL; node = node->next) {
        cout << node->element << " (" << node->priority << ")" << endl;
    }
    cout << endl;
}

// Check if the Queue is empty
bool PriorityQueue::isEmpty() {
    if (front == NULL) {
        cout << "Queue is Empty" << endl;
        return true;
    }
    return false;
}

// The main function to begin the execution
int main()
{
    // Create a Queue
    PriorityQueue queue;
    
    // Push the elements 10 (3), 20 (1), and 30 (2)
    queue.enqueue(10, 3);
    queue.display("Queue after enqueue(10, 3)");
    queue.enqueue(20, 1);
    queue.display("Queue after enqueue(20, 1)");
    queue.enqueue(30, 2);
    queue.display("Queue after enqueue(30, 2)");

    // Get the peek element
    int element = queue.peek();
    cout << "Peek element returned " << element << endl;
    
    // Pop the elements from Queue one by one
    for (int i=0; i < 3; i++) {
        element = queue.dequeue();
        cout << "Dequeue element returned " << element << endl;
        queue.display("Queue after dequeue()");
    }
}

Output

Queue after enqueue(10, 3)
10 (3) <-- front

Queue after enqueue(20, 1)
20 (1) <-- front
10 (3)

Queue after enqueue(30, 2)
30 (2) <-- front
20 (1)
10 (3)

Peek element returned 20
Dequeue element returned 20
Queue after dequeue()
30 (2) <-- front
10 (3)

Dequeue element returned 30
Queue after dequeue()
10 (3) <-- front

Dequeue element returned 10
Queue after dequeue()
Queue is Empty

3. Operations of Priority Queue

Here, we discuss the operations of a Priority Queue with an unsorted Linked List.

3.1. Enqueue with unordered Linked List

The enqueue always inserts the element at the Front side. So the list is not sorted by the priority values.

Algorithm

1. Create the new Node with Priority
2. Connect the new node at the Front by linking the new node before the Front.
3. Finally, Change the Front to point to the new node

Examples

Let’s start with the following queue and proceed with the enqueue operations. The initial queue is empty so the Front is NULL.

Enqueue Element (10) with Priority (3). Create a new node and make it Front since the queue is empty.

Enqueue Element (20) with Priority (1). The subsequent elements are also enqueued at Front by following the same steps.

Enqueue Element (30) with Priority (2)

3.2. Dequeue with unordered Linked List

The dequeue operation search and remove the highest priority element. Since the queue is not sorted, it requires a full search to locate the next element.

Algorithm

1. Check if the Queue is empty. If true, Exit.
2. Iterate the list and find the element with the highest priority. Store the reference to its previous node since this is required for deletion.
3. Retrieve the element from the identified node.
4. Check if the highest priority element is at the Front.
5. If true, change the Front to the next and delete the node.
6. Otherwise, delink the node by directly connecting its previous and next node and delete it.

Examples

Let’s Dequeue an element from the following Priority Queue.

Dequeue the element (20) which is the next priority. Search the entire list to identify this next element. Then, remove the node (20) by directly linking its previous node (30) and the next node (10).

Dequeue the next element which is node (30) with priority P2. Since the node is located at the Front, we need to update the Front pointer to the next node.

Finally, dequeue element (10) with the priority P3. The Front pointer becomes NULL since there are no other nodes.