CP164 Lab 6 : Lists (Cont'd)

Week of

The Complete Linked Stack ADT (Abstract Data Type)

Stack_linked.py contains the complete linked implementation of the Stack ADT. The Lab Instructor will walk you through the library and discuss its inner workings.

The List ADT (Abstract Data Type)

The List ADT is the same as the Lists lab. The difference this week is that we will be working with a linked implementation rather than an array-based implementation. Thus the testing programs you wrote previously should work with this week's implementation with only one change: instead of importing the List_array library, you must import the List_linked library. Thus:

from List_array import List

is replaced by:

from List_linked import List

If (after correctly completing the linked code in today's tasks) your testing program does not work properly, then you must have violated the ADT somewhere in your code by referring to the underlying array implementation of the previous version. To emphasize again: using an ADT means that the programs that you write only use the available ADT functions and do not concern themselves with the underlying implementation. Thus you should be able to switch from one implementation to another with only the single line change already mentioned.

Linked Lists

The file List_linked.py contains the linked implementation of the List ADT. The Lab Instructor will walk you through the library and discuss its inner workings.

For the List_linked library complete the implementation of and test the following methods with both integer and Food data. Use the same tests you used for the earlier Lists lab:

  1. prepend, append, and insert

    Hint: prepend and append are much simpler than insert, and you are allowed to call prepend and append from within insert if you wish.

    Test List_linked.py:

  2. _linear_search

    Note that this linear search returns more results than the array-based linear search, which returns only an integer index. First, we can do this because the linear search is a private helper method. Because it is never supposed to be used outside the List class definition, we can tailor it to suit an array-based or a linked implementation as required. Second, it returns three values because when we find a particular node in the linked list, we may need to know what comes before this node and how many nodes we visited. We can ignore the results we don't need. (See the definition of the remove method.)

    Hint: the linked linear search is used in many other methods, just as it was in the array-based implementation

  3. count , max , and min

    Test List_linked.py:

  4. find , index , and __contains__

    Test List_linked.py:

  5. peek and remove

    Test List_linked.py:

  6. __getitem__ and __setitem__

    Test List_linked.py: