CS21: Lab 12

This lab is OPTIONAL. However, you may want to write these methods as practice for the final exam.

Implementing a linked list class

For this lab, run update21 to get a clean copy of the code we wrote in class for the Node and LinkedList classes. In your cs21/labs/12 directory should be the linkedList.py which contains the Node class in it's entirety and the start of the implementation for the LinkedList class. Read through these files and make sure you understand how the code works.

Your job for this lab is to write a linked list class that behaves similarly to Python lists. In particular, your class must support the following methods:

__init__() -- constructor for the linked list class
__str__() -- print out the list like a Python list
__len__() -- gets the length of the list
__contains__(item) -- is item in list
__getitem__(index) -- gets the item at index
__setitem__(index, item) -- sets the item at index
append(item) -- Add a new node with item added to the end of the list.
prepend(item) -- Add new node with item added to the start of the list.
removeFromHead() -- Delete the head node, return item stored in deleted node
removeFromTail() -- Delete the tail node, return item stored in deleted node
count(item) -- count and return the number of nodes with item stored in the data of the node
index(item) -- return the index of the first item in the list.
insert(index, item) -- insert item before index
remove(item) -- Remove the first occurrence of item in the list
pop(index) -- remove and return item at index; if the list is empty or index is out of range, return None

More detailed documentation is provided in the documentation for the starter code. To get you started, we have completed the __init__() and __str__() methods for you. You may also use any code that we have given to you or that we have worked on in class together. The first part of the lab is to understand exactly what the methods we went over in class are doing. Remember, there are three attributes that the linked list must always keep up to date: head, tail, and size. At the end of every method call all three of these attributes must be correct. Watch out for special cases, such as deleting a node when there's only one node left in the list.

You'll want to make sure you have valid input for some of the methods above. For example, for the __getitem__ method, you'll want to make sure the index is an integer and within the range of the list (greater than or equal to zero and less than the length of the list). To see if a variable is an integer you can use the following test: type(var) == int will be True when the variable var is an integer and False otherwise. For any of the methods that have index parameters, you do not have to support negative indexes. You can treat a negative index as invalid.

Note: If you need to insert or remove an item from the beginning or end of the list in one of your methods (for example, a call of pop(0) will remove the first item in the list), your method should call the methods you specifically wrote to handle these situations (e.g., removeFromHead()) as a helper methods.

Testing your code

You should have good test cases for your code in the main() function. Part of the evaluation for this lab will be on how good your test cases are. We have put some simple test cases in the starter code, but you will need to expand on these test cases. Your results should match what is printed at the end of each line. You do not need to keep this test code to test your class, you can come up with your own tests and testing scheme, but try to test the special cases of each of the methods. The correct output from the tests in the starter code is shown below:

test01 [0, 1, 2] [0, 1, 2]
test02 False False
test03 True True
test04 0 0
test05 None None
test06 [100, 1, 2] [100, 1, 2]
test07 [100, 1, 2] [100, 1, 2]
test08 1 1
test09 0 0
test10 2 2
test11 None None
test12 True True
test13 False False
test14 1 1
test15 [2] [2]
test16 2 2
test17 [] []
test18 [0, 1, 2, 3] [0, 1, 2, 3]
test19 True True
test20 [0, 1, 3] [0, 1, 3]
test21 False False
test22 [0, 1, 3] [0, 1, 3]
test23 0 0
test24 [1, 3] [1, 3]
test25 None None
test26 [1, 3] [1, 3]

Hacker's Challenge

When you have finished and tested your linked list class, try to run some timing tests on your linked list and compare them to the speed of Python lists. Try adding, removing, and inserting at the beginning, middle, and end of your linked list and the built-in Python lists. To get timing information, you can use the time() function from the time module. To get good timing information, you will want to try on large lists and run each test multiple times.

Submit

Once you are satisfied with your programs, hand them in by typing handin21 at the Linux prompt.

You may run handin21 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize, after handing in some programs, that you'd like to make a few more changes to them.

CS21 Lab 12: LinkedLists