Lab 3, CSC 202

This lab provides an introduction to list implementations. In particular, you are asked to implement both a linked list and an array-backed list.

Here’s the invitation link to create a repository for this lab.

1 List Abstract Data Type

There are different ways to represent the abstraction notion of a sequence of values; a linked list is one of these. Another is an array.

A wrapper, such as the Abstract Data Type (or ADT) described here, provides a way to access a set of common operations on a list, without knowing what kind of list it is.

Details of each operation are given below; you will implement these operations for a linked list implementation and for a NumPy Array implementation. You must verify, via test cases, that your implementations behave as expected (i.e., that they "work").

• empty_list This function takes no arguments and returns an empty list.

• add_to_front This function takes a list and an element and returns a list where the new element is first and the remaining elements follow it.

• add This function takes a list, an integer index, and another value as arguments and places the value at index position in the list (zero-based indexing; any element at the given index before this operation will now immediately follow the new element). If the index is invalid (i.e., less than 0 or greater than the current length), then this operation should raise an IndexError exception. (Note that an index equal to the length is allowed and results in the new value being added to the end of the list. Also, note that if the given value does not match the underlying type of the list, it’s fine for an error to occur.)

  This function must return the resulting list.

• length This function takes a list as an argument and returns the number of elements currently in the list.

• get This function takes a list and an integer index as arguments and returns the value at the index position in the list (zero-based indexing). If the index is invalid (i.e., it falls outside the bounds of the list), then this operation should raise an IndexError exception.

• set This function takes a list, an integer index, and another value (of any type) as arguments and replaces the element at index position in the list with the given value. If the index is invalid, then this operation should raise an IndexError exception.

  This function must return the resulting list.

• remove This function takes a list and an integer index as arguments and removes the element at the index position from the list. If the index is invalid (i.e., it falls outside the bounds of the list), then this operation should raise an IndexError exception.

  This function must return a 2-tuple of, in this order, the element previously at the specified index (i.e., the removed element) and the resulting list.

2 Linked List

In a file named linked_list.py, provide a data definition for an AnyList, whose Pair class’s first field can be any value. Amend our earlier definition to use None to represent the empty list. Be sure to call your pair class Pair, so that our tests can create objects correctly.

Implement the functions listed above.

Place your test cases in a file named linked_list_tests.py.

As before, follow the design recipe (data definitions if necessary, signature, purpose statement, header, test cases, fill in body) to design the each of these functions.

As always, write test cases as step three, before the template step.

3 Array List

In a file named array_list.py, define the List class(es) for an array list implementation and implement the aforementioned list operations. For this implementation, each element of the array represents one element of the list. This implementation must allow for the list to grow dynamically (i.e., you cannot assume a maximum size). Place your test cases in a file named array_list_tests.py.

As before, follow the design recipe (data definitions if necessary, signature, purpose statement, header, test cases, fill in body) to design the each of these functions.

You will use a NumPy array as the backing array for your array list implementation.

4 Using NumPy

In order to use NumPy, you are very likely to need to install it. The best way to do this in PyCharm is to configure your project with a virtual environment, and to install NumPy in the context of this virtual environment. If you have any trouble with this, ask your lab neighbors or your instructor to help you out!

5 Exceptions and Testing

This lab requires you to signal an IndexError exception in several places. This means that you need to be able to raise exceptions, and to write tests for methods that raise them.

5.1 Raising Exceptions

In Python, you can raise an IndexError exception with the statement

This will cause Python to discard evaluation context outward until it reaches a try statement. Since we’re not using try statements yet, this means that it will discard all of the program’s evaluation context, and simply halt.

5.2 Testing Functions that Raise Exceptions

So, if raising an exception halts the program, how are we supposed to write tests for functions that raise exceptions?

Python provides an assertRaises method as part of its unittest framework that addresses this. However, there is one "gotcha." Let’s say your my_fun function is supposed to signal an IndexError when called with two equal numbers. We can test this using this expression:

There’s something strange about this: we didn’t actually call the my_fun function, we just passed it to assertRaises.

6 Tuples

For the remove method, you’re asked to return a tuple. What’s a tuple?

Tuples are a way of representing a sequence of values of a known length. They’re easy to write. If you want to put the number 3 and the string "apple" in a 2-tuple, you’d write

This form can also be used to create tuples containing 3 elements, or zero elements. Unfortunately, you can’t use this form to create tuples with one element. Too bad.

How is a tuple different from an Array? In a typed language, they’d be completely different animals—for instance, you can associate different types with different elements of a tuple—but in Python, the differences are limited. For instance, you can’t call append on a tuple.

Let’s just say that if you want to write a function that returns two values, the idiomatic way to express that would be with a 2-tuple.

7 Lab Credit

You must submit your files for grading to receive credit for this lab. This requires that you use the specified file names (listed below) and the specified function names for the required operations (review the lab description to verify that these match).