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

To start this lab, run update21 to create your cs21/labs/12 directory. This should also create a file linkedList.py which contains definitions for Node and LinkedList classes.

Your job for this lab is to write/finish the linked list class so that it behaves like a Python list. In particular, your class must support the following methods:

• __init__() -- constructor for the linked list class
• __str__() -- return a string that looks like a Python list (e.g., [0, 1, 2])
• __len__() -- return the length of the linked list
• append(item) -- add a new node to the end of the list
• prepend(item) -- add a new node to the beginning 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 that contain item
• index(item) -- return the index of the first node that contains item
• insert(index, item) -- insert node containing item at given index
• pop(index) -- remove and return item at index
• remove(item) -- remove the first occurrence of item in the list

More detailed documentation is provided in the linkedlist.py file. To get you started, we have already written the __init__() and __str__() methods. You may also use any code that we have given 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.

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()).

You should always test your code! We have provided various print statements. Each line is of the form

• [testNumber] [your output] [expected output]

Use these tests by implementing the LinkedList functions in the order they get tested. If the outputs don't match, think about what this print statement was testing and what your implementation is doing for this particular method.

Here are a few examples:

    # Test the constructor __init__, __str__ method                                        
    print("****Testing Constructor****")
    lst = LinkedList()
    print("Test01 %s []" % str(lst))
    assert(str(lst) == "[]")
    print("Constructor test passed!!")

    # Test append                                                                          
    print("\n****Testing append method****")
    lst.append(2)
    print("Test02 %s [2]" % str(lst))
    lst.append(3)
    print("Test03 %s [2,3]"  % str(lst))

    # Test04 uses public data members, but just for testing purposes                       
    print("Test04 lst.size = %d 2" % lst.size)


    # Test prepend                                                                         
    print("\n****Testing prepend method****")
    lst = LinkedList()
    lst.prepend(0)
    print("Test05 %s [0]" % str(lst))
    lst.prepend(1)
    print("Test06 %s [1, 0]" % str(lst))
    print("Test07 lst.size = %d 2" % lst.size)
    lst.append(2)
    print("Test08 %s [1, 0, 2]" % str(lst))

...and here is the resulting output, assuming your implementation is correct:

****Testing Constructor****
Test01 [] []
Constructor test passed!!

****Testing append method****
Test02 [2] [2]
Test03 [2, 3] [2,3]
Test04 lst.size = 2 2

****Testing prepend method****
Test05 [0] [0]
Test06 [1, 0] [1, 0]
Test07 lst.size = 2 2
Test08 [1, 0, 2] [1, 0, 2]

The following methods allow linked list objects to use square-bracket indexing and the membership (in) operator. If you have time, see if you can implement these extra methods:

• __contains__(item) -- return True if item is in the linked list
• __getitem__(index) -- returns the item at the given index
• __setitem__(index, item) -- sets the item at the given index