CP164 Study Guide - Final Guide: Priority Queue
Priority Queue Insert
The linked priority queue stores its values in priority order. Thus, inserting a value into a
linked priority queue requires that we create a new node for the value at the correct
position in the linked structure. To insert a new node, then, we must connect that new node
with two other nodes - the preceding node, and the node that follows.
In traversing the priority queue we will be looking for a node containing a value that has a
lower priority than the value we wish to insert. (Higher priority values are to the front of
the priority queue, lower priority values towards the end.) The print traversal example
above can probably help us find the node with a lower priority value, but it won't help us
keep track of the previous node - once current has visited a node and printed its contents,
it moves on and forgets about where it has been. Clearly we need a second temporary node
to keep track of the node immediately preceding current.
Finding the New Value Location
Once the proper location has been found, you can then create the new node (you can't
create it before you know what its _next should be), and adjust the pointer on the previous
node to point to it, and the new node is now inserted into the proper place in the sorted
list:
Inserting the New Node
The key to understanding this process is to understand that without keeping track of the
node before the location of the new node (i.e. previous), you will lose the connections
between the nodes.
Array vs Linked Comparisons
find more resources at oneclass.com
find more resources at oneclass.com
