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
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.
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:
append are much simpler
insert, and you are allowed to call
append from within
insert if you wish.
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
Hint: the linked linear search is used in many other methods, just as it was in the array-based implementation
max , and
index , and