CP164 Study Guide - Final Guide: Linked Data Structure, Priority Queue, Linked Data
We've already seen diagrams of the insertion process: see the Priority Queue Insert section
of the Traversing a Singly Linked List notes. We would like to see how to write the code
based on this.
The first step is writing insert is to clearly understand its purpose and parameters. The
method comments and skeleton are:
def insert(self, value):
"""
-------------------------------------------------------
Inserts a copy of value into a priority queue.
Use: pq.insert(value)
-------------------------------------------------------
Preconditions:
value - a data value (?)
Postconditions:
value is added to the priority queue in sorted order.
Insertion is stable.
-------------------------------------------------------
"""
...
return
We now know: we have to work with a priority queue; a single piece of data; and the
method does not have to return anything. Thus all changes to the priority queue are done
internally.
We don't have to detail the insertion process in order to understand what a typical priority
queue linked data structure looks like. We know that in the linked version the priority
queue stores its data in priority order. In a simple example, we have the integer values, 1, 3,
5, and 7, stored in the priority queue. The smaller the value the higher the priority. The
resulting linked data structure can be shown like this:
A Simple Linked Priority Queue
Given a new piece of data we have to insert it into its proper place in the linked data
structure. Depending on the priority of the data its new node could be at the front, rear, or
interior of the linked data structure. Rather than worry about each of these special cases
now, we will attempt to write a generic algorithm and then see if it handles these special
cases without alteration. If it does not, then we will add the appropriate code. If it does,
then we don't have to worry about these special cases. Thus we will attempt to write code
to insert the new node somewhere inside an arbitrary linked list.
Assume for a moment then that we wish to insert the value 6 into the typical list above.
This new node must go in between and be linked to the nodes containing 5 and 7.
To insert this new node, then, we must do the following:
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
We"ve already seen diagrams of the insertion process: see the priority queue insert section of the traversing a singly linked list notes. We would like to see how to write the code based on this. The first step is writing insert is to clearly understand its purpose and parameters. The method comments and skeleton are: def insert(self, value): Inserts a copy of value into a priority queue. Postconditions: value is added to the priority queue in sorted order. We now know: we have to work with a priority queue; a single piece of data; and the method does not have to return anything. Thus all changes to the priority queue are done internally. We don"t have to detail the insertion process in order to understand what a typical priority queue linked data structure looks like. We know that in the linked version the priority queue stores its data in priority order.
