CP164 Study Guide - Final Guide: Linked Data Structure
Linked Thinking
We also know that we need to stop when we reach the correct position in the list. We reach
that position when our new value is less than the current value in the list. i.e. we keep
looping as long as our new value is greater than or equal to the value in the current node.
(We put the 'or equal to' in so that we have a stable insert.) The loop with the comparison
now looks like:
current = self._front
while value >= current._data:
Now we have to put these two looping conditions together. Does the order matter?
Sometimes, no. Here, the order is very important. If current is Nonethen it cannot have
a _value element, and any attempt to reference that element would cause the program to
die. Thus it is key to check whether currentactually points to a node before we attempt to
compare a value in that node. Our loop becomes:
current = self._front
while current is not None and value >= current._data:
To complete the loop we must update the value of current within the body of the loop or
the loop never moves past the first node (if there is one). current must be updated to point
to the next node in the linked data structure. The next node is pointed to
by current's _next attribute:
current = self._front
while current is not None and value >= current._data:
current = current._next
This loop now gets us to the point that our current pointer references the node containing
the value that should follow our new value. We can now create our new node:
node = _PQNode(value, current)
So far, so good, but now we have a problem - we cannot connect the node that contains the
value 5 to the new node because we have lost track of where that previous node is. We
need an extra variable in our loop to keep track of this previous node - a good (and
obvious!) name for this previous node is previous. It must be initialized before the loop
start. We initialize it to None because there is no node previous to the front of the linked
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
We also know that we need to stop when we reach the correct position in the list. The loop with the comparison now looks like: current = self. _front while value >= current. _data: Now we have to put these two looping conditions together. If current is nonethen it cannot have a _value element, and any attempt to reference that element would cause the program to die. Thus it is key to check whether currentactually points to a node before we attempt to compare a value in that node. Our loop becomes: current = self. _front while current is not none and value >= current. _data: The next node is pointed to by current"s _next attribute: current = self. _front while current is not none and value >= current. _data: current = current. _next. This loop now gets us to the point that our current pointer references the node containing the value that should follow our new value.
