Linked Priority Queue

A linked list implementation of the priority queue ADT using Comparable. LinkedPriorityQueue orders its elements according to their natural ordering. Highest priority being the first in the chain.

Documentation

The official documentation (javadoc) can be found here, while informal visual representations of the implementation are included below.

LinkedPriorityQueue

Node

push()

When pushing elements to the linked priority queue, we have two special cases. If newElement is the first in the chain (Figure 2.0) and if newElement has a higher priority than the first element in the chain, firstNode.getElement() (Figure 2.1).

 

 

 

If this is not a special case, instantiate a Node called currentNode referenced to firstNode. If newElement has a lesser priority than the next element in the chain, move newNode and currentNode down the chain. This continues in a while loop until either...

1. newNode is prioritized
2. newNode.getNextNode() == null

 

pop()

Since the elements are prioritized when they're pushed into the queue, the highest priority element is the first Node in the chain. As shown in Figure 3.0, when we call pop(), the method returns the element stored in firstNode, firstNode is then referenced to the next Node, and the empty Node is deallocated by Java's garbage collector.