Priority Queue Implementation in Java Using Linked List

Priority queues are an essential data structure, especially when tasks have differing levels of urgency. They enable us to manage data in such a way that the most "urgent" or "priority" elements can be dequeued before the less urgent ones. 

While there are many ways to implement a priority queue, such as using arrays, heaps, or binary trees, one of the simplest methods is using a linked list. In this article, we'll explore how to implement a priority queue using a linked list in Java. 

The Concept Behind Priority Queue Implementation 

A linked list, by its nature, allows for easy insertion and deletion of elements at any position. For our priority queue, we'll keep the list sorted based on priority so that dequeuing always results in removing the element at the head of the list (highest priority). 

Java Implementation

Let's jump into the code:

class Node {
    int data;
    int priority;
    Node next;

    public Node(int data, int priority) {
        this.data = data;
        this.priority = priority;
        next = null;
    }
}

public class PriorityQueue {
    Node head;

    // Enqueue according to priority
    public void enqueue(int data, int priority) {
        Node newNode = new Node(data, priority);
        if (head == null || head.priority > priority) {
            newNode.next = head;
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null && temp.next.priority <= priority) {
                temp = temp.next;
            }
            newNode.next = temp.next;
            temp.next = newNode;
        }
    }

    // Dequeue highest priority element
    public int dequeue() {
        if (head == null) throw new IllegalStateException("Queue is empty");
        int value = head.data;
        head = head.next;
        return value;
    }
}

Testing the Priority Queue Implementation:

public class Main {
    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue();

        queue.enqueue(10, 2);
        queue.enqueue(20, 1);
        queue.enqueue(30, 3);

        System.out.println(queue.dequeue() + " dequeued from priority queue"); // 20
        System.out.println(queue.dequeue() + " dequeued from priority queue"); // 10
    }
}

Output:

20 dequeued from priority queue
10 dequeued from priority queue

Implementing a priority queue using a linked list in Java provides an intuitive way to manage priority data. Although there are more efficient ways to implement priority queues, especially for large datasets, this method serves as a foundational understanding of how priority-based data structures work. Through such implementations, we get a glimpse of how abstract data structures can be concretely visualized and executed.