Week of
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 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.
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:
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.
_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
count
, max
, and min
find
, index
, and __contains__
peek
and remove
__getitem__
and __setitem__