One way to maintain a priority queue in memory is by means of a one-way list, as follows:
- Each node in the list will contain three items of information: an information field INFO, a priority number PRN and a link number LINK.
- A node X precedes a node Y in the list
a. When X has higher priority than Y.
b. When both have the same priority but X was added to the list before Y. This means that the order in the one-way list corresponds to the order of the priority queue.
Example:
Below Figure shows the way the priority queue may appear in memory using linear arrays INFO, PRN and LINK with 7 elements.
The diagram does not tell us whether BBB was added to the list before or after DDD. On the other hand, the diagram does tell us that BBB was inserted before CCC, because BBB and CCC have the same priority number and BBB appears before CCC in the list.
The main property of the one-way list representation of a priority queue is that the element in the queue that should be processed first always appears at the beginning of the one-way list.
Accordingly, it is a very simple matter to delete and process an element from our priority queue.