Lab 3, CSC 202
1 List Abstract Data Type
2 Linked List
3 Array List
4 Exceptions and Testing
4.1 Raising Exceptions
4.2 Testing Functions that Raise Exceptions
5 Tuples
6 Lab Credit
6.9.0.6

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" list.

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

1 List Abstract Data Type

The operations supported by a list can be discussed independent of the implementation. As such, a given list implementation can be used through the set of operations without programmatic concern for the details of the implementation. This allows one to vary the implementation based on the characteristics of the problem being solved.

Details of each operation are given below; you will implement these operations for a linked list implementation and for an "array" list implementation. You must verify, via test cases, that your implementations behave as expected (i.e., that they "work"). In a separate project, you will perform an empirical study of the performance characteristics of these two implementations.

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 Python list as the backing array for your array list implementation (Python lists, at least in the standard implementation, are backed by arrays).

Note: since this lab (and related project) is a study of data structure implementation, you are prohibited from using any of the operations of Python’s list type in your array list implementation aside from initializing with a specified size (through the * operator, e.g., [None] * 100, which will act as "allocating a new array") and indexing. This means that any copying required in your implementation must be done via loops to make the steps explicit (e.g., no slices allowed). This restriction only applies within this course when stated; when you use Python in the future and want an array-list like data structure, you should certainly use the provided type and its operations.

4 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.

4.1 Raising Exceptions

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

raise IndexError()

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.

4.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:

self.assertRaises(IndexError, my_fun, 3, 3)

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

You might be able to see why this is the case: in Python, as you know, arguments to function calls are evaluated before the call is made. This means that if we tried to use

my_fun(3,3)

as an argument to assertRaises, we would trigger the exception—and halt the program—before the assertRaises function can set up a fence to handle this exception.

5 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

(3, "apple")

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.

6 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).

Recall that the file names are as follows.
  • linked_list.py – linked list implementation

  • linked_list_tests.py – linked list tests

  • array_list.py – array list implementation

  • array_list_tests.py – array list tests