Implementation of Priority Queue using Linked List in Java
Implementation of Priority Queue using Linked List
Implementation of Priority Queue using Linked List in Java demonstrates how a priority queue can be built using a linked list data structure. In a priority queue, elements are processed based on priority rather than insertion order. The element with the highest priority is removed first.
Unlike array based priority queues, a linked list implementation allows dynamic memory allocation, meaning the queue can grow as needed without a fixed capacity.
Implementation of Priority Queue using Linked List in Java
Every element in the priority queue is associated with a priority. It does not matter in which order we insert the items in the queue, the item with higher priority must be removed before the item with the lower priority.
If the two items have same priorities, the order of removal is not defined and depends on implementation.
Suppose we insert the following elements with priorities:
Value Priority
A 3
B 1
C 2
Removal order will be:
B → C → A
Because smaller priority number means higher priority.
Priority Queue using Linked List in Java
In a linked list implementation:
- Each node contains data and priority
- Nodes are arranged in sorted order based on priority
- The highest priority node remains at the front
OPERATIONS IN PRIORITY QUEUE :
- insert(): This function is used to insert a new data into the queue.
- delete(): This function removes the element with the highest priority form the queue.
- peek() : This function is used to get the highest priority element in the queue without removing it from the queue.
Algorithm for Priority Queue using Linked List in Java
Algorithm: Insert Element
1. Create new node with value and priority
2. If queue is empty OR new node has higher priority than front
Insert at beginning
3. Else
Traverse list until correct position found
4. Insert node in sorted position
Algorithm: Delete Element
1. If queue is empty
Print underflow
2. Remove node at front
3. Move front pointer to next node
4. Return removed element
Algorithm: Peek
1. If queue empty
Return -1
2. Return front.data
Algorithm: isEmpty
Return front == null
Circular Queue using Linked Lists
Priority Queue using Linked List
Priority Queue Insertion and Deletion
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Java Code for Priority Queue using Linked List
class Node {
int data;
int priority;
Node next;
Node(int data, int priority) {
this.data = data;
this.priority = priority;
this.next = null;
}
}
public class PriorityQueueLinkedList {
private Node front;
public PriorityQueueLinkedList() {
front = null;
}
// Check if queue is empty
public boolean isEmpty() {
return front == null;
}
// Insert element
public void insert(int value, int priority) {
Node newNode = new Node(value, priority);
// Insert at beginning
if (isEmpty() || priority < front.priority) {
newNode.next = front;
front = newNode;
} else {
Node temp = front;
while (temp.next != null &&
temp.next.priority <= priority) {
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
}
System.out.println(value + " inserted with priority " + priority);
}
// Delete highest priority element
public int delete() {
if (isEmpty()) {
System.out.println("Queue is empty (Underflow)");
return -1;
}
int value = front.data;
front = front.next;
return value;
}
// Peek front element
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
return front.data;
}
// Display queue
public void display() {
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
Node temp = front;
System.out.print("Priority Queue: ");
while (temp != null) {
System.out.print("(" + temp.data + ", p=" +
temp.priority + ") ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
PriorityQueueLinkedList pq =
new PriorityQueueLinkedList();
pq.insert(30, 3);
pq.insert(10, 1);
pq.insert(20, 2);
pq.insert(40, 4);
pq.display();
System.out.println("Removed: " + pq.delete());
System.out.println("Removed: " + pq.delete());
pq.display();
System.out.println("Front element: " + pq.peek());
}
}
Input:
insert(30,3) insert(10,1) insert(20,2) insert(40,4) delete() delete()
Output:
30 inserted with priority 3 10 inserted with priority 1 20 inserted with priority 2 40 inserted with priority 4 Priority Queue: (10,p=1) (20,p=2) (30,p=3) (40,p=4) Removed: 10 Removed: 20 Priority Queue: (30,p=3) (40,p=4) Front element: 30
Space Complexity: O(n)
Space Complexity: O(n)
Time and Space Complexity Comparison
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insert | O(n) | O(n) |
| Delete | O(1) | O(n) |
| Peek | O(1) | O(n) |
| Display | O(n) | O(n) |
Before performing operations:
- Check if queue is empty before deletion
- Ensure priorities are compared correctly
- Avoid null pointer errors
- Handle insertion at beginning properly
Example:
if (front == null) {
System.out.println("Queue is empty");
} 
Frequently Asked Questions
Answer:
It is a priority queue implemented using a linked list where nodes are sorted based on priority.
Answer:
Insertion takes O(n) time because the list must be traversed.
Answer:
Because the highest priority element is always at the front.
Answer:
Linked lists allow dynamic size, while arrays have fixed capacity.
Answer:
Heap based priority queues provide O(log n) insertion and deletion.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment