PriorityQueue vs LinkedList in Java

1. Introduction

In Java, PriorityQueue and LinkedList are two different implementations of the Queue interface. A PriorityQueue is a special type of queue that orders its elements according to a given comparator or the natural ordering of the elements. On the other hand, a LinkedList is a doubly-linked list that can be used as a list, stack, or queue and maintains the insertion order of its elements.

2. Key Points

1. PriorityQueue orders its elements according to their natural ordering or by a Comparator provided at queue construction time.

2. LinkedList maintains the insertion order of the elements and does not sort them unless explicitly done by the programmer.

3. PriorityQueue does not permit null elements, while LinkedList allows nulls.

4. PriorityQueue offers O(log n) time complexity for enqueuing and dequeuing methods, whereas LinkedList offers constant time performance for these operations at the cost of higher memory consumption.

3. Differences: PriorityQueue vs LinkedList in Java

PriorityQueue	LinkedList
Automatically orders elements according to their priority.	Maintains the insertion order, and does not sort elements.
Does not allow null elements.	Allows null elements.
Provides O(log n) time for enqueuing and dequeuing operations.	Provides constant time for add and remove operations at the ends.

4. Example

// Importing necessary classes
import java.util.PriorityQueue;
import java.util.LinkedList;
import java.util.Queue;

public class QueueComparison {
    public static void main(String[] args) {
        // Step 1: Create a PriorityQueue and a LinkedList
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        Queue<Integer> linkedList = new LinkedList<>();

        // Step 2: Add elements to the PriorityQueue
        priorityQueue.add(10);
        priorityQueue.add(20);
        priorityQueue.add(15);

        // Step 3: Add elements to the LinkedList
        linkedList.add(10);
        linkedList.add(20);
        linkedList.add(15);

        // Step 4: Peek the head of each queue
        System.out.println("Head of PriorityQueue: " + priorityQueue.peek());
        System.out.println("Head of LinkedList: " + linkedList.peek());

        // Step 5: Remove the head of each queue
        priorityQueue.remove();
        linkedList.remove();

        // Step 6: Print the queues after removal
        System.out.println("PriorityQueue after removal: " + priorityQueue);
        System.out.println("LinkedList after removal: " + linkedList);
    }
}

Output:

Head of PriorityQueue: 10
Head of LinkedList: 10
PriorityQueue after removal: [15, 20]
LinkedList after removal: [20, 15]

Explanation:

1. PriorityQueue and LinkedList are instantiated as Queue.

2. Three integers are added to each queue, but PriorityQueue sorts these automatically.

3. The head, or the element at the front of each queue, is observed using peek(). Both show the first element added, 10.

4. Removing the head from each queue affects the two differently; PriorityQueue reorders the elements, while LinkedList does not.

5. After removal, PriorityQueue shows the next smallest element, 15, while LinkedList shows the next element added, 20.

5. When to use?

- Use PriorityQueue when you need elements to be processed based on a priority that you define, for instance, in to-do list applications, pathfinding, or scheduling algorithms.

- Use LinkedList when you need a simple queue that maintains the order in which elements are inserted, and when you might also need list operations, like frequent insertions and deletions in the middle of the list.