CP164 Study Guide - Final Guide: Linked List
Interlude - Writing Methods
We have required that data structure methods be written at the lowest possible level, i.e.
that an method should not call other public methods to complete their word. (They may,
however, call private helper methods such as _linear_search or _binary_search, which
are specially designed to simplify other methods.) Why is this important? What are the
benefits of writing slightly longer chunks of code when shortcuts are available?
There are two major reasons that we require you to code at the lowest level possible:
• to demonstrate to us that you truly understand the data structures you are implementing
• that these shortcuts may be shortcuts in coding only, and be grossly inefficient in actual
execution.
Understanding the second point reinforces the first.
A Bad Example
Here is an example of a simple linked list:
A Simple Linked List
The method is_identical compares two linked lists to determine if their contents are the
same and in the same order. The array-based version of the list could use code like the
following to accomplish this:
def is_identical(self, rs):
"""
---------------------------------------------------------
Determines whether two lists are identical.
Use: b = l.is_identical(rs)
-------------------------------------------------------
Preconditions:
rs - another list (List)
Postconditions:
returns
identical - True if this list contains the same values as rs
in the same order, otherwise returns False (boolean)
find more resources at oneclass.com
find more resources at oneclass.com
