CP164 Lab 4 : Lists

Week of

The List ADT (Abstract Data Type)

A List is a data structure that stores data in no particular order. Data is added to some arbitrary position in the list and removed from the list by providing the remove function with a key and searching and removing the first value in the list that has a matching key. The List ADT is discussed in The List ADT.

The file List_array.py contains the array implementation of the List ADT. The Lab Instructor will walk you through the library and discuss its inner workings. Add the contents of this file to your data structures project in Eclipse.

In order to deal with a key version of a Movie object, the Movie constructor must be able to accept None s or other values appropriate for non-key fields of an object. For example, the constructor call:

from Movie import Movie

key = Movie('Juno', 2007, None, None, None)
print(key)

should produce:

Title:    Juno
Year:     2007
Director: None
Rating:   None
Genres:

Thus both the constructor (the __init__ method) and the string representation (the __str__ method) may have to be updated to deal with None for director, rating, and genres.

Hint: it is not required, but feel free to implement the functions array_to_list and list_to_array for ease of testing. These should be similar to the functions you wrote for the Stacks lab.

  1. Verify that your Movie class code handles keys - i.e. accepts None appropriately.


  2. In the List class, complete the _linear_search method. (Note that this is a private helper method for the List class. Do not test it directly - it can be used in some of the methods that follow.)


  3. In the List class, complete the insert , append , and remove methods.

    Test List_array.py:


  4. In the List class, complete the index , find , __contains__ , count , max , and min methods.

    Test List_array.py:


  5. In the List class, complete the __getitem__ and __setitem__ methods.

    Test List_array.py:


  6. Add the following functions to the PyDev module named utilities in your login_data_structures project.

    def array_to_list(llist, source):
        """
        -------------------------------------------------------
        Appends contests of source to llist. At finish, source is empty.
        Last element in source is at rear of llist,
        first element in source is at front of llist.
        Use: array_to_list(llist, source)
        -------------------------------------------------------
        Parameters:
            llist - a List object (List)
            source - a Python list (list)
        Returns:
            None
        -------------------------------------------------------
        """
    
    def list_to_array(llist, target):
        """
        -------------------------------------------------------
        Removes contents of llist into target. At finish, llist is empty.
        Front element of llist is at front of target,
        rear element of llist is at rear of target.
        Use: list_to_array(llist, target)
        -------------------------------------------------------
        Parameters:
            llist - a List object (List)
            target - a Python list (list)
        Returns:
            None
        -------------------------------------------------------
        """
    

    Test utilities.py:


  7. Add the following function to the PyDev module utilities.py in your login_data_structures project.

    def list_test(a):
        """
        -------------------------------------------------------
        Tests list implementation.
        The methods of List are tested for both empty and
        non-empty lists using the data in a:
        is_empty, insert, remove, append, index, __contains__,
        find, count, max, min, __getitem__, __setitem__
        Use: list_test(a)
        -------------------------------------------------------
        Parameters:
            a - list of data (list of ?)
        Returns:
            None
        -------------------------------------------------------
        """
        lst = List()
    
        # tests for the List methods go here
        # print the results of the method calls and verify by hand
    
        return
    

    Use Movie data from movies.txt to test your List code.

    Test utilities.py: